The whole breakaway in one frame
A photographer on a motorbike rides alongside the breakaway of a bike race and wants to capture all the riders of the breakaway in one frame. The tighter the group, the better the picture. The riders ride along a straight road, each at their own constant speed; some catch up with others, and the leader and the last rider of the group may change more than once during the shoot. Shooting is possible from time 0 to time T. Find how stretched out the group is at its tightest: the smallest distance over [0, T] from the first rider to the last.
Rider i at time t is at point xi + vi·t. Overtaking hinders no one: the road is wide, and everyone keeps their speed.
Input
The first line holds the number of riders n and the length of the shoot T in seconds (1 ≤ n ≤ 105, 1 ≤ T ≤ 104, T an integer). Then n lines xi vi: the rider’s position at time 0 in metres, an integer from 0 to 105, and their speed in m/s from 5 to 25, with at most two decimal places.
Output
The smallest length of the group in metres. An answer is accepted if its error is at most 10−6, absolute for answers under one and relative for the rest.
Examples
Example 1
3 100 0 12.00 100 10.00 40 11.00
10.000000
Example 2
2 30 0 13.00 400 8.00
250.000000
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The length of the group at time t is L(t) = maxi(xi + vit) − mini(xi + vit). The leader and the last rider change, and it seems such a function could have any number of pits. Draw it for the first example. What can be said about the function “the largest of several lines”?
2Hint 2
The largest of several lines is a convex polyline: each line is convex, and a maximum of convex functions is convex. The smallest of several lines is concave. And their difference?
3The idea
L(t) = maxi(xi + vit) + maxi(−xi − vit) is a sum of two convex functions, hence convex. A convex function on an interval has no false pits: it decreases to the minimum, may stay on a plateau, and then increases. So the minimum is found by the search from the article on ternary search, and evaluating L(t) at one point is one pass over the riders.
4Walkthrough
Why the difference is convex. A function is convex if the segment between two points of its graph lies no lower than the graph. For a line this is an equality. If each of the functions fi is convex, then max fi(λa + (1 − λ)b) ≤ max (λfi(a) + (1 − λ)fi(b)) ≤ λ max fi(a) + (1 − λ) max fi(b), so the maximum is convex too. Minus the smallest of the lines is the largest of the lines −xi − vit, and a sum of two convex functions is convex.
The article’s theorem requires strict unimodality, while L can have plateaus, a full 400 seconds in the last test. For a convex function this is no problem. If L(m₁) > L(m₂) with m₁ < m₂, then on [0, m₁] the values are no less than L(m₁): otherwise the point m₁ would lie above the segment joining two other points of the graph. So the piece left of m₁ can be thrown away without losing the minimum. If the values are equal, at least one point of the minimum lies on [m₁, m₂], by the same argument from both sides, and either of the two pieces will do. A convex function has plateaus only at the very bottom, where they are harmless.
The golden section on [0, T] down to a width of 10−8 seconds. The length of the group changes by at most 20 m per second, the largest difference in speeds, so the error of the answer is at most 2·10−7 m. At the end it is worth comparing the ends of the interval too: the minimum can be at time 0 or at time T, as in the second example.
There is an exact method as well: build the upper envelope of the lines and the lower one, as in the convex hull trick, and check all their breakpoints; the minimum of a convex polyline lies at a breakpoint or at an end. That is O(n log n), but three times as much code.
4+Solution
5Complexity
About 60 evaluations of L at O(n) each, 6·106 simple operations. Ternary search takes twice as many and is also in time.
6Common mistakes
- The extreme riders do not change. Taking the leader and the last rider at time 0 and following only them is
wrong.py. In the first example it answers 0: the leader and the last rider draw level at second 50, but by then the third rider has become the last, and the group is stretched over 10 metres. - All pairs of riders. The minimum lies at a moment when some two riders are level, but there are 5·109 pairs, and each also needs a pass over everyone.
- A grid of whole seconds. The minimum can fall between seconds, and the polyline at the bottom is a sharp angle: an error of half a second costs metres.
- Stopping by relative width. If the search is stopped when the interval has shrunk to 10−9·T, at T = 104 that is 10−5 seconds, and with a speed difference of 20 m/s the error reaches 2·10−4 m, more than the tolerance when the group almost converges to a point, as in the eighth test.