An index of straight lines
An earthquake catalogue stores the moments of the shocks in increasing order, in nanoseconds since the start of 1970. To find a moment in it faster than by binary search, the “moment → place” curve is replaced with straight pieces, as in the learned indexes of databases. The line of a piece guesses the place of a key with an error of at most ε, and the key then has to be found among the 2ε + 1 places around the guess. The index stores only the starts of the pieces and the slopes of their lines: the fewer the pieces, the smaller it is.
The keys k0 < k1 < … < kn−1 stand at places 0, 1, …, n − 1. The pieces are built greedily, from left to right. A piece starts with the first key not yet in any piece, say ks. Its line passes through the point (ks, s), that is, the first key is guessed exactly, while the slope σ may be chosen. The piece takes the following keys one at a time while there is a σ such that for each key kp of the piece
|s + σ · (kp − ks) − p| ≤ ε.
A key with which there is no longer such a σ starts a new piece. For each of m values of ε, print how many pieces there will be.
Three tests are real data: the moments of all earthquakes of magnitude 5 and above in 2015–2025 (the USGS ComCat catalogue), and the populations and latitudes of the world’s cities of 10,000 people and more (GeoNames).
In the first example with ε = 1 the first piece takes the keys 0, 10, 20, 31 and 40: σ = 0.1, for example, fits. Key 100 at place 5 needs σ from 0.04 to 0.06, while key 40 requires σ ≥ 3/40 = 0.075, so key 100 starts the second piece. With ε = 0 the pieces come out like this: 0, 10, 20, then 31, 40, then 100.
In the second example the first three keys lie on a line with slope 1/333,333,333,333,333,333, and the slope to the last key is 3/1018. These numbers differ in the eighteenth digit, and with ε = 0 the last key starts a new piece.
Input
The first line holds n and m (1 ≤ n ≤ 150,000, 1 ≤ m ≤ 5). The second holds n distinct integer keys in increasing order, |k| ≤ 2·1018. The third holds m integers ε (0 ≤ ε ≤ 109).
Output
m numbers separated by spaces: how many pieces there will be for each ε.
Examples
Example 1
6 2 0 10 20 31 40 100 0 1
3 2
Example 2
4 1 0 333333333333333333 666666666666666666 1000000000000000000 0
2
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 13 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 line passes through the first point of the piece, so it has one parameter left, the slope σ. Which σ does one key kp allow? Write the condition |s + σ·(kp − ks) − p| ≤ ε as a constraint on σ.
2Hint 2
Each key allows an interval of slopes, and the whole piece allows their intersection. An intersection of intervals is again an interval, and only its ends need to be kept. How should the ends be compared so as not to go wrong on keys up to 2·1018?
3The idea
Write Δ = kp − ks > 0 and d = p − s. The key’s condition is equivalent to (d − ε)/Δ ≤ σ ≤ (d + ε)/Δ. A piece keeps the interval of allowed slopes [lo, hi]: each next key narrows it to the intersection with its own interval. If the intersection is empty, no line through the first point suits all the keys at once: the key starts a new piece, and the interval becomes the whole line again. This is the “shrinking cone”: the lines through the first point with slopes from lo to hi sweep an angle, and each key narrows it.
4Walkthrough
The ends of the interval are fractions a/b with a positive denominator Δ, and they must be compared exactly: a/b ≤ c/d exactly when a·d ≤ c·b. The numerators are at most n + ε, the denominators up to 4·1018, and the products go up to 1027. Python integers cope with this by themselves. In Go a 128-bit product is needed: bits.Mul64 multiplies the absolute values, and the sign of the numerator is handled separately.
Here is what comes out on real data. The moments of 19 thousand earthquakes with ε = 64 fit into 16 pieces: the shocks come almost evenly, and the “moment → place” curve is almost straight. City populations fit into 18 pieces, although as a whole this curve is as bad as it gets for interpolation. Bookmarks every 2ε + 1 = 129 keys with the same error would need 148 and 238.
4+Solution
5Complexity
O(n·m) time: each key for each ε is compared with the ends of the interval in O(1). Memory is O(n) for the keys themselves.
6Common mistakes
- Slopes in floating point. Two different fractions with huge denominators round to one and the same number: in the second example 1/333,333,333,333,333,333 and 3/1018 are equal as
float. This iswrong.py. - Products in int64. 109 · 4·1018 does not fit in 64 bits, and the comparison is silently wrong. This is
wrong.go. - Checking only the key itself. You could accept a key only if its own slope d/Δ lies inside the cone; one of the papers on learned indexes splits this way. But the problem requires something else: a key may be guessed with an error of up to ε, not exactly. Such a rule cuts pieces more often: for city populations with ε = 16 it gives 77 pieces instead of 45.
- Forgetting to reset the interval. A new piece starts from a clean slate: the old constraints referred to a line through a different point.