Editorial for COI '11 #3 Setnja


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Each of Mirko's friends is described by numbers X, Y, P. Notice that possible meeting points with a given friend form a square centered at (X, Y) – more precisely, a square with opposing vertices at (X-P, Y-P) and (X+P, Y+P).

Now the task has been reduced to finding the shortest possible path that touches all squares in order from first to last.

For each K from 1 to N, we consider all possible shortest paths that visit squares 1, 2, \dots, K, in that order. Let S(K) be the set of all endpoints of those paths, i.e. the set of all positions where we could have ended up after visiting the first K friends in an optimal manner. Let d(K) be the length of these shortest paths.

Notice that S(1) is precisely the square corresponding to the first friend, since we could have started (and ended) a path with length 0 by visiting the first friend in any point of that square.

The solution should proceed to find S(2), S(3), \dots, S(N). As we will show, all the sets will be rectangles. Now we have to determine how to find S(K+1) if we are given S(K).

Let D be the minimum distance (number of steps) from any point of S(K) to the square belonging to the (K+1)^\text{st} friend (whom we need to visit next). Notice that d(K+1) = d(K)+D.

If we expand the rectangle S(K) by D units in all four directions, we will obtain all points reachable after optimally visiting the first K friends and then moving D steps in any direction. The intersection of the expanded rectangle and the square corresponding to the (K+1)^\text{st} friend is therefore the set of points where we can meet friend K+1 after making d(K)+D steps (from the definition of D, the intersection is guaranteed to be nonempty) – therefore, this intersection is exactly S(K+1), furthermore it is a rectangle (as an intersection of a square and a rectangle, both aligned with the same axes).

The final solution is simply the sum of all D values obtained while finding S(2), S(3), \dots, S(N) – this is precisely d(N).


Comments

There are no comments at the moment.