Finding the best path (if one exists)

Question

Given the parameter k and the array [a ₀ , ₁ , a ₂ , a ₃ , ..., a _n ], where a _x determines the height of the relief, find the smallest amount of work necessary for the landscape to pass. The terrain is passable if the difference between two neighboring places is less than or equal to k. The height of the terrain at _x can be changed, and the amount of work required is equal to the difference in height that you do. The heights ₀ and _n cannot be changed, and therefore some landscapes may be completely inaccessible.

I struggled with this for a while: this is what I have guessed so far: Of course, finding a solution (not considering the minimum amount of work that needs to be considered) is easy - take the “steps” from ₀ to _n , as in the diagram with k = 2 (red dots are the heights of the old terrain, gray for the new).

(The entrance for this particular locality will be: k = 2, [0, 2, 3, 2, 5, 4, 5, 7])

As you can see, the new landscape does not take into account the old territory and, therefore, the work necessary to convert the old into this one can be huge.

Determining whether a path exists is trivial: k> = | a ₀ -a _n | / n, but I have no idea how I will go about finding the optimal solution.

Answer 1

Use a simple method to solve the following linear program.

minimize sum_i y_i subject to # y_i is notionally |x_i - a_i| # equality holds in every optimal solution y_i >= x_i - a_i for all i y_i >= a_i - x_i for all i # transformed terrain is passable, ie, |x_i - x_{i+1}| <= k x_i - x_{i+1} <= k for all i x_{i+1} - x_i <= k for all i 

Answer 2

One brute force solution looks like this. For each element, consider the following three states: one with h + 1, h + 0, h - 1, where h is the height of the element. Now continue to move around the array and see the following points 1) If the state was received earlier, drop it (so make a dp bitmask for this)

2) If you have reached a state in which a crossed neighboring diff does not drop it.

3) If the total work done so far is more than the minimum, until it is discarded.

Answer 3

Let ht = an-a0 be the total height. Let hAverageStep = ht / n. And k is the maximum step.

Ideally, in step 'i', the height difference should be i * hAverageStep. In this case, the path is simply a constant line. We want to get closer to this line.

For step “i,” you can observe if you need some “work” at this point to move it to a straight line. If this work is greater than k, you must also move other points, for example, some previous ones you did not work enough.

If after moving each point as much as necessary, "an" will not be achieved, there is no solution.