Problems Base course RU

The most frequent words

frequencies heap hash table sorting interviews

A compiler of a frequency dictionary needs the k most frequent words of a text, each once, together with its number of uses. The order is strict: more frequent first; words with the same number of uses in alphabetical order. The alphabet here is the order of Unicode code points, the one in which Python and Go compare strings: the letters from а to я go as usual, and ё comes after я.

The text is already split into words: runs of lowercase Cyrillic letters separated by spaces and line breaks. The second example is the beginning of the epilogue of War and Peace (the Russian original), and among the hidden tests are the whole epilogue and the first part of the first volume.

Input

The first line holds k (1 ≤ k ≤ 1000). Then the text: at most 100,000 words of lowercase Cyrillic letters, separated by spaces and line breaks.

Output

k lines (or fewer if the text has fewer than k distinct words): a word and, after a space, how many times it occurred, in the order described above.

Examples

Example 1

Input

3
кот пёс кот ёж пёс кот ёж ель ель

Output

кот 3
ель 2
пёс 2

Example 2

Input

5
эпилог часть первая прошло семь лет после го года взволнованное историческое море европы улеглось в свои
берега оно казалось затихшим но таинственные силы двигающие человечество таинственные потому что законы определяющие их движение
неизвестны нам продолжали свое действие несмотря на то что поверхность исторического моря казалась неподвижною так же
непрерывно как движение времени двигалось человечество слагались разлагались различные группы людских сцеплений подготовлялись причины образования и
разложения государств перемещений народов историческое море не как прежде направлялось порывами от одного берега к другому
оно бурлило в глубине исторические лица не как прежде носились волнами от одного берега к другому
теперь они казалось кружились на одном месте исторические лица прежде во главе войск отражавшие приказаниями войн
походов сражений движение масс теперь отражали бурлившее движение политическими и дипломатическими соображениями законами трактатами эту деятельность
исторических лиц историки называют реакцией описывая деятельность этих исторических лиц бывших по их мнению причиною того
что они называют реакцией историки строго осуждают их все известные люди того времени от александра и
наполеона до фотия шеллинга фихте шатобриана и проч проходят перед их строгим судом и оправдываются или
осуждаются смотря по тому содействовали ли они прогрессу или реакции в россии по их описанию в
этот период времени тоже происходила реакция и главным виновником этой реакции был александр тот самый александр
который по их же описаниям был главным виновником либеральных начинаний своего царствования и спасения россии в
настоящей русской литературе от гимназиста до ученого историка нет человека который не бросил бы своего камушка
в александра за неправильные поступки его в этот период царствования он должен был поступить так то
и так то в таком случае он поступил хорошо в таком дурно он прекрасно вел себя
в начале царствования и во время го года но он поступил дурно дав конституцию польше сделав
священный союз дав власть аракчееву поощряя голицына и мистицизм потом поощряя шишкова и фотия он сделал
дурно занимаясь фронтовой частью армии он поступил дурно раскассировав семеновский полк и т д надо бы
исписать десять листов для того чтобы перечислить все те упреки которые делают ему историки на основании
того знания блага человечества которым они обладают что значат эти упреки те самые поступки за которые
историки одобряют александра как то либеральные начинания царствования борьба с наполеоном твердость выказанная им в м
году и поход го года не вытекают ли из одних и тех же источников условий крови
воспитания жизни сделавших личность александра тем чем она была из которых вытекают и те поступки за

Output

и 15
в 11
их 6
он 6
александра 4

Limits

Time · Python: 2000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 10 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

Counting words is a dictionary. The most interesting part is the order of ties. Check the first example: «ель», «пёс» and «ёж» have equal counts, two each, but only two of them make it into the answer.

2Hint 2

If you used Counter.most_common(k), look at the order in which it returns words with equal counts. The clue is in its source code: it calls heapq.nlargest with the count as the key.

3The idea

One key is needed that takes both rules into account: the pair (−count, word). A smaller pair is a more frequent word, and at equal counts a word earlier in the alphabet. Then the k best are the k smallest pairs, and a heap of k gives them: heapq.nsmallest(k, …, key=…), or sorting all the pairs if there are few distinct words.

4Walkthrough

Count the words with a dictionary (Counter in Python, map in Go) and pick the k smallest by the key (−count, word). The reference solution in Python uses heapq.nsmallest, a heap of k; the reference in Go simply sorts all the pairs: the tests have at most a few thousand distinct words.

Why most_common goes wrong. It works as heapq.nlargest(k, items, key=count), and nlargest keeps equal keys in the order the elements arrived, which for a Counter is the order of each word’s first appearance in the text. In the first example «пёс» appeared before «ель», and most_common(3) returns кот, пёс, ёж instead of кот, ель, пёс. The error is easy to miss: among large counts there are almost no ties, and the top of the list is usually right. What breaks is the edge of the top, where many words have the same small counts.

The second trap is the letter ё itself. In Russian dictionaries «ёж» stands between «ерш» and «жук», but in Unicode code point order ё (U+0451) comes after я (U+044F). The statement asks for exactly code point order: the standard string comparisons in Python and Go give it, and no locale is needed.

4+Solution

5Complexity

Counting is O(N) for N words, selection with a heap O(D log k) for D distinct words, with sorting O(D log D). Memory is a dictionary of D words.

6Common mistakes

Counter.most_common(k): ties come in order of appearance, not alphabetically.
A heap with the key (count, word) that pushes out the minimum. If you keep a heap of k with the smallest pair (count, word) on top, at equal counts the word that comes earlier in the alphabet is pushed out, and that is exactly the one that should stay. Ties need the reverse order of words, so it is simpler to work with the key (−count, word) and nsmallest.
Locale-aware sorting. A comparison that takes the locale into account puts ё next to е, while the statement requires code point order.

Algorithms behind it

SRT Algorithm Top-k: the k best A heap of k with the worst on top: the stream is read once, and almost every element is sifted out with one comparison. O(n log k) 2 problems DS Data structure Hash table Search, insert and delete by key in O(1) on average: the key turns into the number of an array cell. O(1) on average 2 problems