Editorial for COI '11 #3 Setnja
Submitting an official solution before solving the problem yourself is a bannable offence.
Each of Mirko's friends is described by numbers . Notice that possible meeting points with a given friend form a square centered at – more precisely, a square with opposing vertices at and .
Now the task has been reduced to finding the shortest possible path that touches all squares in order from first to last.
For each from to , we consider all possible shortest paths that visit squares , in that order. Let 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 friends in an optimal manner. Let be the length of these shortest paths.
Notice that is precisely the square corresponding to the first friend, since we could have started (and ended) a path with length by visiting the first friend in any point of that square.
The solution should proceed to find . As we will show, all the sets will be rectangles. Now we have to determine how to find if we are given .
Let be the minimum distance (number of steps) from any point of to the square belonging to the friend (whom we need to visit next). Notice that .
If we expand the rectangle by units in all four directions, we will obtain all points reachable after optimally visiting the first friends and then moving steps in any direction. The intersection of the expanded rectangle and the square corresponding to the friend is therefore the set of points where we can meet friend after making steps (from the definition of , the intersection is guaranteed to be nonempty) – therefore, this intersection is exactly , 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 values obtained while finding – this is precisely .
Comments