Hints from the novel
A keyboard suggests a word while you are typing it. It needs a dictionary: words and how many times each occurred. For each beginning of a word typed, answer how many dictionary words begin with it, how many times they all occur together, and which of them is the most frequent: that is the one the keyboard will show first.
The second test is the dictionary of War and Peace (the Russian original): all 47,585 distinct words of the novel with their frequencies. The third is the dictionary of the English translation by Louise and Aylmer Maude.
Input
The first line holds n (1 ≤ n ≤ 10⁵). The next n lines hold a word and a number: how many times it occurred (from 1 to 10⁶). The words are distinct, made of lowercase Cyrillic or Latin letters, up to 30 long, at most 10⁶ letters in total. Then q (1 ≤ q ≤ 10⁵) and q lines with beginnings of words: non-empty, of the same letters, up to 30 long.
Output
For each beginning, three values separated by spaces: the number of dictionary words that begin with it, the sum of their frequencies, and the most frequent of them (on a tie, the first alphabetically). If there are no such words, 0 0 -.
Examples
Example 1
5 наполеон 584 наташи 149 наташа 827 народ 77 мир 47 4 нат на мирный м
2 976 наташа 4 1637 наташа 0 0 - 1 47 мир
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 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
Scanning the whole dictionary for each beginning is 10⁵ queries over 10⁵ words, ten billion checks. The answer to a query needs to cost as many steps as it has letters.
2Hint 2
All the words that begin with a given string lie in one subtree of a trie. What do you need to know about a subtree in advance to answer without traversing it?
3The idea
Build a trie, and when inserting each word walk its path from the root: at each node of the path add one to the word count, the frequency to the sum, and compare the word with the best already stored in the node. Each node of the path is one of the beginnings of the word being inserted, so the node accumulates the answer for exactly “its” beginning. A query is a descent by its letters and reading three fields.
4Walkthrough
Building costs the total length of the words, a query its own length. If at some letter there is no branch, there are no words with that beginning, and the answer is 0 0 -. “Better” means a higher frequency, and at equal frequency an alphabetically smaller word; in Python that is one comparison of the pairs (−frequency, word).
The same can be done without a trie: sort the words, find by binary search the range of words with the given beginning (from p to p with a letter greater than every letter of the alphabet appended), take the sum of frequencies from prefix sums, and the most frequent from a sparse table of maximums. That gives O(q · |p| · log n) and more code. The trie is good in that it accumulates the answer for each beginning right where the descent will lead, which is also how the suggestions in the article’s scene work.
4+Solution
5Complexity
O(L + Q) time, where L is the total length of the dictionary’s words and Q the total length of the queries. Memory is O(L) nodes.
6Common mistakes
- Scanning the dictionary for each query. The second test is 47,585 words and 50,000 queries, more than two billion
startswithchecks. - The most frequent without handling ties. In the seventh test all words have the same frequency, and the first alphabetically is needed.
- Comparing strings in Go. String comparison with
<is byte-wise, but for UTF-8 it agrees with the order of letters; a character index and a byte index in a string are different things, though, so walk a word withfor _, ch := range w.