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 <= n <= 5000 points on the line. Each point has different natural coordinate 0 <= d <= 10^6 and (not necessarily different) natural point-time 0 <= t <= 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 -> 1 -> 5 -> 8 -> 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 -> 1 -> 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 -> 1 -> 3 -> 0 -> 4, which takes us 10 seconds.

Can anyone help?

Answer 1

First sort your points based on coordinate.

I would recommend a dynamic programming approach based on solving the following subproblem for each value of near and far between 0 and n-1:

Given that we are at the near^th point and have already visited all points between near and far (inclusive), then what time must it be if we just have enough time to visit all the remaining points?

The answer to your problem is given by the greatest value v(x) of the subproblem for near=far=x as x varies between 0 and n-1. If v(x)<0 for all x then you cannot reach all the points. However, if v(x)>=0 for some x, then you can reach all the points in a time given by "maximum point-time over all points"-v by starting from position x.

The recurrence between cases is based on considering going left or right from the near^th point until you reach the first point that you haven't yet covered. (This will involve going to an immediate neighbour of either point near, or point far so the recurrence only takes O(1) time to compute)

There are n^2 subproblems, so this approach should take time O(n^2) overall.

EDIT

Python code to implement this approach:

A=[(0,7), (1,2), (2,1), (3, 4), (4,11)]
A.sort()
M=max(a[1] for a in A)
cache={}
def go(near,far):
    """Given that we are at near and have visited all points in [near..far], 
    (near can be > or < or = far)
    return the latest time that allows us to visit all points, 
    and visit the point near itself."""
    if abs(far-near)==len(A)-1:
        return A[near][1]-1

    key=near,far
    if key in cache:
        return cache[key]

    v=-1
    d = 1 if near<=far else -1
    n = near-d
    if 0<=n<len(A):
        v=go(n,far)-abs(A[n][0]-A[near][0])
    n = far+d
    if 0<=n<len(A):
        v=max(v,go(n,near)-abs(A[n][0]-A[near][0]))

    v=min(v,A[near][1]-1)
    cache[key]=v
    return v

v=max((go(x,x),x) for x in xrange(len(A)))
if v[0]<0:
    print 'Impossible'
else:
    print 'Takes',M-v[0]-1,'seconds starting from point',v[1]

There is a slight ambiguity as to whether for a point with time 1 you have to reach it at time t<1 or at time t<=1. This solution uses time t<1 as it matches with your example.

(If the requirement was t<=1, then the solution to (0,7), (1,2), (2,1), (3, 4), (4,11) would be the path 1 -> 2 -> 3 -> 0 -> 4 in 9 seconds)