The decoder
An arithmetic coder with an adaptive model has compressed a text by words. The model has a table of words in a fixed order and a count for each word; at the start all the counts are one. Each word occupies an interval of numbers: if the sum of the counts of all the words that come earlier in the table is L and its own count is c, the word’s interval is [L, L + c). For each word the coder sent one number from its interval, and then increased that word’s count by one. The decoder repeats the same: it finds the word whose interval contains the number and increases its count.
Write the decoder. One of the tests is the beginning of War and Peace in the Russian original: the first 30,000 words, the table being their vocabulary in alphabetical order.
Input
The first line holds m and n (1 ≤ m ≤ 100,000, 1 ≤ n ≤ 50,000): the number of words in the table and the length of the text. The second holds m distinct words separated by spaces in table order. The third holds n integers: the k-th of them lies in the interval of the k-th word of the text, with the intervals computed from the counts after the first k − 1 words. All the numbers are less than the sum of the counts, that is, less than m + k − 1.
Output
The text: n words separated by spaces on one line.
Examples
Example 1
4 5 в и мир война 3 1 3 1 0
война и мир и в
Example 2
1 3 ау 0 0 0
ау ау ау
Limits
- Time · Python
- 6000 ms
- Time · Go
- 2000 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
Going through the table, adding up the counts until the sum passes the number, is correct, but with a table of a hundred thousand words each word of the text costs tens of thousands of additions. You need sums of counts that update quickly: a Fenwick tree. But it answers “what is the sum up to a word”, and the question is the other way round.
2Hint 2
Prefix sums grow with the number, so the word can be found by binary search, which is O(log² m) per word. But can you search directly over the cells of the tree without computing prefix sums anew?
3The idea
A descent over the powers of two. The position starts at zero; try steps 2k, 2k−1, …, 1. If the position is a multiple of 2k+1, cell pos + 2k holds exactly the sum of the counts between the old position and the new one. If this sum is not greater than what remains of the number, all these words lie entirely before the point: step and subtract the sum. Otherwise stay. At the end the position is the number of words lying entirely before the point, that is, the zero-based number of the word you want.
4Walkthrough
At the start all the counts are ones, and the tree need not be built by addition: cell i is responsible for a block of length lowbit(i) and holds exactly i & −i. The largest step is a power of two greater than m: 1 << m.bit_length(). A step after which the position would go beyond m is skipped. Once the word is found, its count goes up by one along the ordinary update path: add the lowest one bit of the number.
Why the cell holds the right block: after steps 2K, …, 2k+1 the position is a multiple of 2k+1, so the lowest one bit of pos + 2k is exactly 2k, and its block is the counts numbered pos + 1 … pos + 2k.
4+Solution
5Complexity
The descent is O(log m), the update O(log m), O(m + n log m) in all. A binary search over prefix sums would give O(n log² m) and would also fit within the limits, though several times slower. A pass over the table is O(nm): in the fourth test that is 50,000 words over a table of a hundred thousand.
6Common mistakes
- A pass over the table. Correct, but O(m) per word: even on the beginning of the novel, where the table has 7848 words, it does not make it in time in Python.
- The interval boundary. A word with interval [L, L + c) contains L and does not contain L + c; a step is taken when the block sum is not greater than the remainder. The fifth test sends the last number of each interval, the third the first.
- Forgetting to increase the count. The decoder must change the model just as the coder does, otherwise the intervals diverge from the second word on.
- Starting the steps from the largest power of two not greater than m. That is also correct; what matters is not to start from a smaller one, or the descent will not reach the end of the table.