Visiting points, algorithm

Question

I'm learning for the exam from algorithms and data structures (that I have in a month) and I can't manage with finding efficient algorithm for this problem:

We are given $1\le n\le 5000$ points on the line. Each point has different natural coordinate $0\le d \le 10^6$ and (not necessarily different) natural point-time $0\le t \le 10^9$ in seconds. We can start at any point and in each second change our current coordinate by +/-$1$. The problem is to visit all the points in such order that every point is visited before elapsing his point-time. Find the minimum total time (in seconds) of this trip, or say it's impossible.

For example, $5$ points given (coordinate, point-time):

$(1,3), \ (3,1), \ (5,6), \ (8,19), \ (10,15)$, it's possible, when we take a trip visiting coordinates: $3\rightarrow 1\rightarrow 5 \rightarrow 8 \rightarrow 10$, we got minimum total time, which is equal to: $11$.

My first idea was to sort all the points lexicographically by: (point-time, coordinate), and then visit them in this order. Of course, when there are points between $i$-th point and $(i+1)$-th point, we can visit them before visiting $(i+1)$-th point. But unfortunately, there is no argument why such greedy approach should work, despite the fact that it would be difficult to implement. Maybe I'm trying to solve it too quickly? $n$ is small so, $O(n^2)$ should be ok, I suppose.

I found other examples of the input, thinking maybe it will help me finding the solution. But now I only see that I have to find one permutation of all possible $n!$ permutations.

Input examples:

points (also given by coordinate, point time respectively): $(0,4), \ (1,2), \ (4,5)$ -> surprisingly (I think) we have to visit them: $0\rightarrow 1 \rightarrow 4$, because any different order does not satisfy condition in one before last sentence in problem text.

points: $(0,7), \ (1,2), \ (2,1), \ (3, 4), \ (4,11)$, the only funny way is: $2\rightarrow 1\rightarrow 3\rightarrow 0\rightarrow 4$, which takes us $10$ seconds.

Can anyone help?

Answer 1

the only reasonable moves are to move to the closest unvisited point to the left, or to the closest unvisited point to the right. Also, there can't be any unvisited point between 2 points. We will use dynamic programming to solve it. Let dp[S][L][R] be the minimum time required to visit all points in the interval [L, R], and ending at:(L if S==0, R if S==1). There are 2*5000*5000 states, so it has a reasonable time complexity.
The algorithm is this: from state (S, L, R), we can go to state (0, L-1, R) and (1, L, R+1). the time required for a move is easy to calculate. We cant make a move if the time required is greater than the point-time of the point.
Let the degree of a state be defined as R - L. Every moves goes to a state with a higher degree, so the states can be iterated easily without any cycles in the graph.

Implementation:
No, one run is enough. Mark dp = -1 for the states that are not reachable.

Initialization:
In the beginning all are -1. then, set dp 0 for the sarting states. Those are the states where L == R.

Iteration: you need 3 for loops. As explained in the answer with the 'degree' of the states, your first for loop will iterate over all possible values of R - L. Your second for loop will iterate over all posible values of R. You will calculate L, no for loop needed. And then just one for loop for S.

when you imagine the dp array as a matrix, (ignore S), everything is -1, just the main diagonal is 0. Then you start going outwards from the diagonal.

The recurrence relation is clear, just do the 2 steps, if they dont brake the rule about the point-time.

Easier approach: Start from all the states with R == L with DFS. The order does not matter. Just do memoisation in the dp array.