Two estimates
A stream of numbers passes through a server: words, queries, addresses. Keeping a counter per number is expensive, so they are counted with a Count-Min sketch: d rows of w counters. In row i the number x goes into cell ((ai·x + bi) mod P) mod w, where P = 231 − 1. The estimate of the number of occurrences of x is the minimum over the rows of x's cells.
An engineer wants to compare two ways of updating the sketch on the same stream. Plain: when x occurs, add 1 to its cell in each row. Conservative: first find the current estimate of x, m, and raise each cell of x that is less than m + 1 to m + 1; cells that are already larger are not touched. For each query print both estimates.
In the third test the stream is 200,000 words of “War and Peace”, each replaced by its number by frequency: «и» (“and”) is 1, «в» (“in”) 2, and so on.
Input
The first line holds d, w and the length of the stream n (1 ≤ d ≤ 8, 1 ≤ w ≤ 104, 1 ≤ n ≤ 2·105). The second holds a1, …, ad, the third b1, …, bd (0 ≤ ai, bi < P). The fourth is the stream: n numbers from 1 to 109. Then the number of queries q (1 ≤ q ≤ 2000) and q numbers, one per line.
Output
For each query, two estimates separated by a space: the plain sketch's and the conservative one's.
Examples
Example 1
2 4 8 967164356 29153372 164071949 1045161374 1 2 1 3 1 4 5 2 4 1 2 3 6
5 5 5 5 2 2 1 1
Example 2
3 8 12 449815270 997595895 1392220162 928730935 208356165 507535111 7 7 7 1 2 3 4 5 6 8 9 7 4 7 1 9 10
5 4 1 1 1 1 0 0
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
The plain sketch is a direct repetition of the statement. In the conservative one the order matters: first the estimate from the old cell values, then the raising.
2The idea
Keep two d × w tables. For each number compute its d cells (they are worth remembering for repeats). In the plain table add 1 to all of them. In the conservative one find the minimum m over the number's cells and raise each to max(cell, m + 1). For a query, the minimum over the cells in each table.
3Walkthrough
Why conservative update does not break the guarantee “no less than the truth”. Suppose that before x occurs each of its cells is no less than the true number of its occurrences c. Then the minimum m ≥ c too, and after raising each cell is ≥ m + 1 ≥ c + 1: the truth is below all cells again. Other numbers only raise cells. So the conservative estimate is still an upper bound, and by construction it is no greater than the plain one: the plain sketch always raises each cell by 1, the conservative one by at most 1 and only when necessary.
On “War and Peace” with 512 cells per row the difference shows at once: for «и» the plain estimate is 9849, the conservative 9736. For rare words the gain is larger in percent: they get less noise from frequent neighbours. Conservative update was devised by Cristian Estan and George Varghese for counting network traffic. It has a price: it cannot be applied to negative increments, and two sketches cannot be added cell by cell, as the result depends on the order of the stream.
3+Solution
4Complexity
O(d) per stream item and per query, O(d·w) memory.
5Common mistakes
- Raising only one cell, the smallest. The other rows fall behind, the minimum ends up below the truth, and the sketch stops being an upper bound: the first sample.
- Updating cells one at a time, recomputing the minimum. After the first cell is raised the minimum changes; the cells must be raised to m + 1, with m computed before the update.
- Overflow. ai·x reaches 231·109, which fits in 64 bits but not in 32.