Cuckoo nests
A cuckoo table has m nests numbered from 1 to m. Each of n keys has exactly two nests chosen for it by hash functions: the key can live only in one of them. A nest holds at most one key. The keys may be laid out any way you like, not necessarily by the eviction rules. How many keys can be placed at once?
A key's two nests can coincide, and then it has only one nest. Several keys can have the same nests. Three tests are real: the names of the world's towns of 10,000 inhabitants and more (GeoNames), laid out by two hash functions into two tables of different sizes.
In the first sample there are five keys and four nests, and each key is linked to the others through shared nests: more than four cannot be placed, and four can, for example keys 1, 2, 4, 5 in nests 1, 3, 4, 2. In the second sample there are two separate groups: four keys claim nests 1, 2, 3, and two claim nests 5 and 6, and in all 3 + 2 = 5 fit.
Input
The first line holds n and m (1 ≤ n ≤ 200,000, 1 ≤ m ≤ 106). Then n lines, each with the two nest numbers of a key, a and b (1 ≤ a, b ≤ m).
Output
One number: how many keys can be placed at once.
Examples
Example 1
5 4 1 2 2 3 1 3 3 4 2 4
4
Example 2
6 8 1 2 2 3 3 1 1 3 5 6 6 6
5
Limits
- Time · Python
- 5000 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
Draw a graph: nests are vertices, keys are edges between their two nests. To place a key means to give the edge to one of its vertices, with each vertex getting at most one edge.
2Hint 2
Pieces of the graph not connected to each other do not interfere with each other. How many edges fit in a piece of V vertices if it has E edges?
3The idea
A connected piece of V nests and E keys holds exactly min(E, V) keys. More than V is impossible, since each nest holds one key. If E ≤ V, all fit: this is proved in the article, the piece is a tree or a tree with one cycle, and the keys are laid out “from the cycle outwards”. If E > V, choose a spanning tree of the piece, V − 1 keys, and add one more key: such a piece of V edges is laid out completely, and all V nests end up occupied. The answer is the sum of min(E, V) over the pieces.
4Walkthrough
Find the pieces with a disjoint set union: each key unites its two nests. Then for each root count the edges, the keys that have this root, and the vertices, the nests reached by at least one key. Nests nobody claims affect nothing and are not counted. A key with two equal nests is a loop: there is an edge in the piece, but no extra vertex.
On town names you see the same as in the article. Below the threshold, at a load of 0.47, all 42,311 names fit; slightly above, at 0.53, all but eight; when there are as many nests as names, 35,396 fit, 84 %.
4+Solution
5Complexity
O((n + m) · α(m)), almost linear.
6Common mistakes
- Inserting by the cuckoo rules. Evictions with a limit on their number lose keys that actually fit: in the eighth test a chain of evictions a thousand nests long is cut off at the fiftieth. This is
wrong.py. Without a limit, the insertion loops in an overfull piece. - Counting vertices over all nests. min(E, V) must be taken for each piece separately, not min(n, m) for the whole table: the spare nests of one piece do not help another.
- Forgetting loops and repeats. A key with equal nests and ten keys on one pair of nests are ordinary edges; a piece of two nests holds two keys, however many claim them.
Algorithms behind it
lookup at most d probes in the worst case; insertion O(1) on average below the threshold
1 problem
DS
Data structure
Disjoint set union
Merge two sets and tell whether elements are in the same one, in almost O(1): a forest of parent links and two tricks.
O(α(n))
2 problems