I am kind of stuck, I decided to try this problem https://icpcarchive.ecs.baylor.edu/external/71/7113.pdf

to prevent it 404'ing here's the basic assignment

a hopper only visits arrays with integer entries,
• a hopper always explores a sequence of array elements using the following rules:
– a hopper cannot jump too far, that is, the next element is always at most D indices away
(how far a hopper can jump depends on the length of its legs),
– a hopper doesn't like big changes in values — the next element differs from the current
element by at most M, more precisely the absolute value of the difference is at most M (how
big a change in values a hopper can handle depends on the length of its arms), and
– a hopper never visits the same element twice.
• a hopper will explore the array with the longest exploration sequence.


n is the length of the array (as described above, D is the maximum length of a jump the
hopper can make, and M is the maximum difference in values a hopper can handle). The next line
contains n integers — the entries of the array. We have 1 ≤ D ≤ 7, 1 ≤ M ≤ 10, 000, 1 ≤ n ≤ 10, 000
and the integers in the array are between -1,000,000 and 1,000,000.

EDIT: I am doing this out of pure curiosity this is not a assignment I need to do for any particular reason other than challenging myself

basically its building a sparse graph out of an array, the graph is undirected and due to the symmetry of the -d ... d jumps, its also either a complete graph (all edges are included) or mutually disjoint graph components

As first step I tried to simply exhaustive DFS search the graph, which works but has the infamous O(n!) runtime, the first iteration of this was written in F# which was horrible slow the second in C which still plateaus pretty fast too so I know the longest path problem is NP hard but I thought I would give it a try with dynamic programming

The next approach was to simply use the common DP solution (bitmasked path) to DFS on the graph but at this at this point I already traversed the array and built the entire graph which may contain up to 1000 nodes so its not feasible

My next approach was to build a DFS Tree (tree of all the paths) which is a bit faster but then needs to store all entire path in memory for each iteration already which isn't what I really want, I am thinking I can reduce it to substates while already traversing the array

next I tried to memoize all paths I've already walked by simply using a bitmask and a simple memoization functions as seen here:

let xf = memoizedEdges (fun r i' p mask  -> 
                    let mask' = (addBit i' mask)
                    let nbs =  [-d .. -1] @ [ 1 .. d] 
                                |> Seq.map (fun f -> match f with 
                                                        | x when (i' + x) < 0 -> None
                                                        | x when (i' + x) >= a.Length -> None
                                                        | x when (diff a.[i'+x] a.[i']) > m -> None
                                                        | x when (i' + x) = i -> None 
                                                        | x when (isSet (i'+x) mask') -> None
                                                        | x -> Some (i' + x )
                                                        ) 
                    let ec = nbs 
                                |> Seq.choose id 
                                |> Seq.toList
                                |> List.map (fun  f  ->
                                                r f i' mask'
                                ) 
                    max  (bitcount mask) (ec |> mxOrZero)
                )

So memoized edges works by 3 int parameters the current index (i'), the previous (p) and the path as bitmask, the momizedEdges function itself will check on each recursive call it if has seen i' and p and the mask ... or p and i' and the mask with the i' and p bits flipped to mask the path in the other way (basically if we have seen this path coming from the other side already)

this works as I would expect, but the assignment states its up to 1000 indices which would cause the int32 mask to be too short

so I've been thinking for days now and there must be a way to encode each of the -d ... d steps into a start and end vertice and calculate the path for each step in that window based on the previous steps

I've come up with basically this

  0.) Create a container to hold starting and endvertex as key with the current pathlength as value
  1.) Check neighbors of i
  2.) Have I seen either this combination either as (from -> to) or (to -> from) then I do not add or increase
  3.) Check whatever any other predecessors to this node exist and increase the path of those by 1
  

but this would lead to having all paths stored and I would basically result in tuples and then I am back at my graph with DFS in another form

I am very thankful for any pointers (I just need some new ideas I am really stuck rn) how I could encode each subproblem from -d..d that I can use just intermediate results for calculating the next step (if this is even possible)