How much longer by the streets
A delivery service estimates the length of a trip before building a route: it multiplies the straight-line distance by a factor k, since going by the streets is always longer than in a straight line. What should k be? There is a log of n trips: for each, the straight-line distance ai and the length of the real route along the streets bi are known. Choose the k for which the sum of squared misses
$$\sum_{i=1}^{n} \bigl(b_i - k\,a_i\bigr)^2$$is smallest, and compute the typical miss of such an estimate, the root mean square: √(Σ(bi − kai)² / n).
The model has no intercept: a trip of zero length is zero both in a straight line and along the streets. Such trips do occur in the log: an order picked up and handed over at the same crossroads.
Two tests are the real Almaty from OpenStreetMap: pairs of crossroads in the city centre, the straight-line distance between them and the shortest path along the streets.
Input
The first line holds the number n (1 ≤ n ≤ 200,000). Each of the next n lines holds two integers ai and bi, the straight-line and street distances in metres (0 ≤ ai, bi ≤ 10⁶). At least one ai is greater than zero.
Output
Two numbers separated by a space: the factor k and the typical miss in metres. An answer is accepted if each number differs from the correct one by at most 10⁻⁶ (for numbers greater than one, by at most 10⁻⁶ of their size).
Examples
Example 1
3 100 130 200 250 400 560
1.366666667 15.986105
Example 2
3 0 0 1000 1500 10 50
1.500349965 20.206249
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 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 slope formula in the article is derived for a line with an intercept: such a line passes through the centre of mass of the points. Here the line must pass through the origin. Repeat the derivation for the model b ≈ ka: what is differentiated here, and what is set to zero?
2Hint 2
The derivative of the sum Σ(bi − kai)² with respect to k is −2Σai(bi − kai). For which k does it vanish?
3The idea
This is the normal equation for a table of one column a, without the column of ones: (Σai²)·k = Σaibi, whence k = Σaibi / Σai². Geometrically it is the projection of the vector of street lengths onto the vector of straight-line lengths. The second derivative 2Σai² is positive (at least one ai is not zero), so this is a minimum.
Note that each trip enters the answer with weight ai²: a long trip weighs much more than a short one. This is a property of squares, not a coincidence: a long trip’s miss in metres is larger, and the method tries hardest to reduce it.
4Walkthrough
One pass, two sums, Σab and Σa². Both are integers: in Python they are exact, in Go they fit in int64 (at most 2·10⁵ · 10¹² = 2·10¹⁷). Divide and you have k. Trips of zero length add nothing to either sum and take care of themselves.
A second pass computes the sum of squared residuals bi − kai, and the typical miss is the root of its mean.
On the two tests from Almaty k comes out at about 1.27–1.28: a path along the streets of the city centre is on average a little over a quarter longer than the straight line, and the typical miss of such an estimate is seven or eight hundred metres.
4+Solution
5Complexity
O(n) time. Memory can be made O(1) by reading the stream twice, but keeping 2·10⁵ pairs is no problem either.
6Common mistakes
- The mean of ratios. Computing bi/ai for each trip and averaging is a natural thought, but it is a different answer: a fifty-metre trip weighs as much in it as a five-kilometre one, and short trips are exactly the ones that wind most. In the first example the mean of ratios is 1.3167 instead of 1.3667, and in the tenth test the difference is severalfold. Besides, the ratio is undefined for trips of zero length.
- The formula with an intercept. The line a + bx from the article fits the points better, but it is not this model: at zero distance it gives a non-zero route length.
- The sum of squared residuals as Σb² − kΣab. At the minimum this is a true identity, and in the article it saves a second pass. But in test 9 both sums are about 10¹⁷, and their difference about a half: in floating point not a single correct digit of it survives, and it may even come out negative under the root. When the model is almost perfect, the residuals have to be added directly.
- Overflow. Σab does not fit in a 32-bit integer already on the tests with real trips across Almaty.