A new server on the ring
A cache cluster is built as a hash ring: the numbers from 0 to 2⁶⁴ − 1, with zero coming again after the largest. Server points stand on the ring (a server may have several, virtual nodes). A key belongs to the server of the first point strictly greater than the key's hash; if there is none, the circle closes, and the key belongs to the server of the very first point of the ring.
New points (a new server) are added to the cluster. How many keys change server, and how many keys does the busiest server hold after the addition? Two tests are built from the real page addresses of legost.in, the same way as in the article.
Input
The number of points n (1 ≤ n ≤ 100,000), then n lines “hash server”. The number of new points m (1 ≤ m ≤ 10,000) and m lines in the same format. The number of keys q (1 ≤ q ≤ 200,000) and a line of q key hashes. Hashes are integers from 0 to 2⁶⁴ − 1, server numbers integers from 1 to 10⁹. The hashes of the points are distinct.
Output
Two lines: how many keys changed server, and how many keys the busiest server has after the addition.
Examples
Example 1
3 100 1 200 2 300 3 1 250 4 7 50 150 220 260 299 300 350
1 3
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 7 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
Sort the points by hash. Which algorithm finds the first point strictly greater than a given number?
2Hint 2
What do you do with a key whose hash is greater than the hashes of all points? Look at the second sample.
3The idea
The owner of a key is the upper bound of the key's hash in the sorted array of points, taken modulo the number of points: an index equal to the length of the array turns into zero, which is how the circle closes. Compute the owners before and after the addition and compare.
4Walkthrough
Sort the original points, and for each key find bisect_right(hashes, key) % n, the number of the point, then its server. The same for the union of old and new points. The number of mismatches answers the first question; a dictionary “server → number of keys” after the addition answers the second.
Hashes go up to 2⁶⁴ − 1: in Go that is uint64, not int64, otherwise large hashes become negative and the order breaks. In Python integers are unbounded.
4+Solution
5Complexity
Sorting is O((n + m) log(n + m)), the search O(q log(n + m)).
6Common mistakes
- No wrap-around. A key to the right of the last point is given to the last server, while it should go to the first. The first sample catches this.
- “Greater or equal” instead of “strictly greater”. By the statement a key whose hash equals a point's hash goes to the next point. The last test checks exactly this.
- int64 in Go. Hashes above 2⁶³ become negative.