Two cells
A hash table has n cells, and each key has exactly two cells it can be put in (they may coincide). A cell holds one key. Keys are added one at a time, and keys already placed may be moved to their other cell, as cuckoo hashing does. Print the number of the first key after whose addition the keys added so far can no longer be laid out over the cells, or 0 if all keys fit. The tests include the file paths of this site, laid out by two CRC-32 hashes.
Input
The first line holds n and the number of keys m (1 ≤ n, m ≤ 2·105). Then m lines: the two cells of a key, numbers from 1 to n.
Output
The number of the first key (from one) after which the keys do not fit, or 0.
In the first example the third key asks for the same cells 1 and 2 as the first, and both are taken. But the second key can be moved from cell 2 to cell 3, and everything fits. The fifth key no longer fits at all: five keys on cells 1–4, each asking only for cells among them.
Examples
Example 1
4 6 1 2 2 3 1 2 3 4 4 1 2 4
5
Example 2
3 4 1 1 2 3 3 2 2 2
4
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 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: cells are vertices, a key is an edge between its two cells. What does “lay the keys out one per cell” mean in the language of this graph?
2Hint 2
In a connected piece of the graph with V vertices and E edges each edge must get its own vertex. How many edges can be placed if the piece is a tree? And if it has a cycle?
3The idea
Laying out the keys means assigning each edge one of its ends so that no vertex goes to two edges. In a connected piece this is possible if and only if there are no more edges than vertices. If E > V, there are simply not enough vertices. If the piece is a tree (E = V − 1), hang it from any vertex and give each edge its lower end. If E = V, the piece has exactly one cycle: the edges of the cycle are assigned round the circle, each the next vertex, and the trees growing out of the cycle as before. A loop (both cells the same) is a cycle of one edge.
4Walkthrough
Keys arrive one at a time, so pieces of the graph only merge: a job for a disjoint-set union. In the root of each set keep the number of vertices and edges. An edge inside a set adds one edge; an edge between two sets merges them and adds one edge. As soon as some set has more edges than vertices, the answer is the number of this key.
The most interesting thing is where this happens. In the sixth test there are 200,000 cells and random pairs; it breaks at key 100,020, exactly when the table is half full. This is the well-known threshold of cuckoo hashing with two hashes: a random graph with m edges on n vertices with m < n/2 almost certainly consists of trees and pieces with one cycle, and beyond this threshold a large piece with many cycles appears. The same on the site’s file paths: 4186 keys fit into 8000 cells. And greedy placement without moving, putting a key into a free one of its two cells and giving up when both are taken, breaks on the same random pairs already at key 4506.
4+Solution
5Complexity
O((n + m)·α(n)), almost linear.
6Common mistakes
- Greed without moving. There may be no free cell among the two, yet there is room if the keys already placed are shifted along a chain. The first example: greed gives up on the third key, while only the fifth breaks.
- A loop. A key with two identical cells is an edge too, and it takes its vertex.
- The boundary. A piece with as many edges as vertices still fits: one cycle is fine.
Algorithms behind it
O(d) per decision: learn the load of d servers
2 problems
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