A top from pieces
A text is spread over m servers. Each server counted its words and sent the coordinator part of its list: a few of its most frequent words with their counts and a threshold t, a guarantee that any word not sent occurs on this server at most t times. A word’s total count is the sum over all servers.
Say a word is in the top k if fewer than k words occur strictly more often than it. Words that no server sent also exist, and how many there are is unknown. For each word sent by at least one server, decide whether it is in the top k certainly, for any real counts consistent with what was sent, or only possibly, for at least one such set of counts.
The second example is War and Peace (the Russian original) spread over four volumes and the epilogue: each volume sent its twenty most frequent words, and the threshold is the count of the last of them.
Input
The first line holds m and k (1 ≤ m ≤ 20, 1 ≤ k ≤ 10,000). Then m blocks. A block starts with a line s t, how many words the server sent and its threshold (1 ≤ s, 0 ≤ t); then s lines “word count”. Words are lowercase Cyrillic letters and do not repeat within a block; counts are from 1 to 109, and each count sent is at least its server’s threshold. In all, at most 100,000 lines are sent.
Output
Four lines: the number of words that are certainly in the top k; those words separated by spaces in Unicode code point order (ё after я); the number of words that are possibly but not certainly in it; those words in the same order. An empty list is an empty line.
Examples
Example 1
3 2 2 3 кот 9 пёс 5 3 4 пёс 8 ёж 6 кот 4 2 5 ёж 9 лис 5
0 3 кот пёс ёж
Example 2
5 20 20 488 и 4776 в 2282 не 1877 он 1774 что 1694 на 1568 с 1363 как 1020 к 848 его 824 то 762 я 754 князь 607 все 601 но 572 она 566 сказал 563 это 527 было 491 за 488 20 553 и 5648 в 2900 не 2404 что 2152 он 2009 на 1725 с 1695 его 1079 я 1070 как 1068 она 1013 к 929 то 871 все 746 но 673 было 654 это 646 так 580 сказал 577 ее 553 20 537 и 5756 в 3066 что 2256 не 2236 на 2015 он 1930 с 1554 его 1077 то 991 как 987 к 939 но 747 было 728 все 693 это 629 по 589 из 577 я 558 за 537 она 537 20 310 и 3357 в 1846 что 1381 не 1297 он 1279 на 948 с 909 то 688 как 649 его 628 к 498 но 475 было 460 все 459 это 429 о 367 она 362 от 338 же 312 из 310 20 181 и 1542 в 803 не 702 что 682 он 408 на 405 то 364 с 348 как 311 его 287 она 256 но 238 это 229 о 210 к 206 я 198 все 197 только 191 бы 182 же 181
17 было в все его и к как на не но он она с то что это я 12 бы ее же за из князь о от по сказал так только
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 12 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
Start with a single word. What is known for sure about its total count? A server that sent the word knows its count exactly. And how often can it occur on a server that did not send it?
2Hint 2
Each word has a range [L, U]: L is the sum of the counts sent, U the same sum plus the thresholds of the servers that did not send the word. The counts of different words on different servers are independent of each other. What does the worst set of real counts for a word look like? The best?
3Hint 3
Do not forget the words that nobody sent. Each of them can have a total count of up to the sum of all thresholds, and how many there are is unknown.
4The idea
For a word w the worst case is when it occurs L(w) times and all the others as often as possible: the words sent at U, the words not sent at T, the sum of all thresholds. All these values can be chosen at once, because the count of each word on each server is a separate unknown. A word is certainly in the top if even then fewer than k words occur strictly more often: T ≤ L(w), since otherwise any number of unsent words could overtake w, and fewer than k words v sent have U(v) > L(w).
The best case is when w occurs U(w) times, the words sent at L, and there are no unsent words at all (a count of 0 is allowed). A word can be in the top if fewer than k words v sent have L(v) > U(w).
5Walkthrough
Add up the counts sent into L; for each word add the thresholds of the servers where it is absent, giving U. Sort all the L and all the U separately; the number of values greater than a given one is found by binary search. For “certainly”, subtract w itself from the number of U greater than L(w) if its U is greater than its L.
In the first example nobody is certainly in. «Ёж» counted 15, the most, but «кот» and «пёс» were not sent by the third server, whose threshold is 5, and each of them could have reached 18. So any of the three may turn out third. «Лис», on the other hand, is not in even in the best case: 5 sent plus the thresholds of two servers give 12, while the other three already have 13, 13 and 15 sent.
On War and Peace with twenty words per volume, 17 words are certainly in the top 20 and 12 more possibly are, among them «так» and «из», which the article talks about. That is how a real system works: Elasticsearch asks the shards for more values than needed and returns an estimate of the possible error along with the answer, and if the estimate is large, the query can be repeated with more values per shard.
5+Solution
6Complexity
Building the ranges is O(N · m) for N lines sent (a threshold is added for each server where the word is absent), sorting and binary searches O(N log N).
7Common mistakes
- Trusting what was sent. Adding up the counts and declaring the first k by sum the answer fails on the first example: the real order may be anything within the ranges.
- Forgetting the unsent words. If the sum of thresholds is greater than L(w), any number of words more frequent than w may be hiding somewhere.
- Non-strict inequalities. The top is defined through “strictly more often”: a word with an equal count does not overtake. Mix up > and ≥ and the boundary goes wrong.
Algorithms behind it
O(n log k)
2 problems
SYS
Data structure
Count-Min Sketch
Frequencies of stream items in fixed memory: the minimum of d counters, with an error only upwards.
O(d) per item and per query
2 problems