Words across chapters
For each chapter of War and Peace a HyperLogLog sketch of its words was saved: m = 2p registers, each word a 32-bit MurmurHash3 hash, a register the largest rank of the hashes that landed in it. The texts themselves are not at hand. A literary scholar needs to know how many distinct words there are in chapters a to b, and there are many such questions.
The estimate from registers M0, …, Mm−1 is computed like this: E = αm·m2 / Σ 2−Mj, where α16 = 0.673, α32 = 0.697, α64 = 0.709, and for m ≥ 128 αm = 0.7213/(1 + 1.079/m); if E ≤ 2.5·m and the number of empty registers V > 0, m·ln(m/V) is taken instead of E. The answer to a question is the estimate from the sketch that would result from passing all the words of chapters a to b through one sketch.
Input
The first line holds the number of chapters d and p (1 ≤ d ≤ 400, 4 ≤ p ≤ 10). Then come d lines of m numbers, the registers of the chapters in order (from 0 to 33). Then the number of questions q (1 ≤ q ≤ 5000) and q lines a b (1 ≤ a ≤ b ≤ d).
Output
For each question, the estimate with an absolute or relative error of at most 10−6.
Examples
Example 1
3 3 0 2 0 1 0 0 3 0 1 2 0 0 0 4 0 0 0 0 0 1 0 0 2 0 4 1 1 1 2 1 3 3 3
3.760029 7.846634 7.846634 2.301457
Example 2
10 6 3 6 4 4 6 9 4 7 4 4 4 4 10 6 7 4 4 6 5 4 8 4 2 4 3 3 4 3 2 4 5 4 3 2 5 4 6 4 7 3 3 10 5 6 5 4 2 4 6 5 4 4 4 3 3 3 3 3 5 3 3 5 5 7 3 4 4 6 6 4 3 7 3 4 4 4 3 3 7 6 4 2 3 11 3 3 4 5 3 4 7 2 5 5 5 5 4 4 3 6 5 4 5 3 4 10 4 6 2 3 5 4 5 2 5 5 4 6 4 4 5 3 4 5 3 5 5 4 5 6 4 4 4 9 4 7 3 5 6 6 10 10 5 5 6 3 4 9 2 4 4 5 5 7 4 4 7 5 5 3 3 3 7 3 5 4 9 2 5 3 4 5 4 3 3 4 6 6 7 5 4 3 6 6 5 4 4 4 4 5 3 6 3 6 4 4 6 9 4 5 3 5 3 6 6 4 5 4 4 3 4 4 4 4 4 6 5 3 3 5 5 4 5 3 3 3 5 4 8 5 6 4 5 4 8 5 4 6 5 6 6 5 2 6 4 8 5 5 5 3 4 4 4 5 3 5 3 9 4 7 3 7 4 4 7 3 2 6 6 5 4 6 4 3 5 11 3 4 4 5 5 2 2 3 2 5 5 3 4 2 5 3 5 4 6 3 3 4 2 4 2 4 2 5 5 2 6 6 4 8 4 6 4 3 4 4 2 5 5 5 3 6 4 5 6 9 10 5 6 5 5 6 6 6 6 4 5 4 4 11 4 5 3 5 5 9 6 5 5 4 5 4 7 4 7 6 8 4 6 6 5 10 4 5 4 3 5 5 4 5 7 6 6 8 11 6 8 3 4 6 5 5 6 6 5 2 4 6 6 3 5 6 4 7 4 6 10 6 6 3 4 5 4 4 6 3 5 5 5 1 3 2 2 3 4 5 3 5 4 5 8 7 6 6 8 3 3 6 4 5 2 4 5 5 7 4 6 8 4 2 6 7 4 3 4 5 2 3 5 2 6 4 1 6 3 5 2 2 3 3 10 2 2 2 4 2 4 3 2 9 3 5 4 2 3 5 5 11 2 3 3 1 9 2 4 4 4 1 5 6 6 3 4 3 2 8 7 6 3 3 3 3 4 2 2 7 4 3 2 1 2 5 3 8 4 4 3 9 4 6 2 2 2 3 3 5 2 4 4 2 5 3 5 3 4 3 2 3 3 4 7 9 3 4 3 3 2 8 3 4 2 8 2 10 2 6 5 5 4 3 4 3 3 3 3 3 4 2 6 7 4 2 4 4 3 6 3 3 4 3 3 4 4 1 2 4 3 2 3 3 2 3 4 2 2 4 2 4 3 0 2 1 4 4 2 4 3 5 4 1 2 10 4 5 2 1 3 2 5 1 3 3 3 4 3 3 3 5 2 8 4 0 3 7 4 2 4 3 5 5 3 1 1 1 10 4 7
637.598957 3598.017587 2449.556455
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1500 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
What would be in register j if all the words of chapters a to b had passed through one sketch? Each word lands in the same register with the same rank as in the sketch of its chapter.
2Hint 2
So you need the maximum of a register over a range of chapters, for each of the m registers. There are many ranges and no updates: which structure answers “maximum on a range” in O(1)?
3The idea
The sketch of a union is the elementwise maximum of the sketches: a register remembers the largest rank among everything that landed in it, and the same things landed as in the chapters separately. Build a sparse table: on level k, for each chapter i, keep the elementwise maximum of the sketches of chapters i to i + 2k − 1. Any range is covered by two such blocks, which may overlap; that does not bother a maximum. For a question, the maximum of two rows and the estimate formula, O(m).
4Walkthrough
The sum of the chapters’ estimates is not the answer: the word «и» (“and”) is in almost every chapter and would be counted hundreds of times. Over the whole novel the sum over chapters exceeds the number of distinct words several times over, while the maximum over the registers gives 48,426 against the exact 47,585, exactly the same estimate as the sketch of the whole novel in the article’s listing: the union of the sketches does not differ from the sketch of the union. This is what makes HyperLogLog convenient for distributed systems: sketches from different servers or for different days are combined with no loss of accuracy.
The table: ⌊log2 d⌋ + 1 levels, each with up to d rows of m bytes; for 361 chapters and 1024 registers about three megabytes. A question: k = ⌊log2(b − a + 1)⌋, rows a and b − 2k + 1 of level k, their elementwise maximum and the estimate.
4+Solution
5Complexity
O(m·d log d) for the table and O(m) per question.
6Common mistakes
- Adding up the chapters’ estimates. Shared words are counted many times: already the second example.
- The range maximum by brute force. O(m·(b − a)) per question: on all the chapters of the novel and five thousand questions, hundreds of millions of operations.
- Averaging the estimates or the registers. The average of the registers is the sketch of an “average chapter”, not of their union.
- Forgetting the small-range correction. Short chapters with a large m leave empty registers.