Топ по частям
Текст разложен по m серверам. Каждый сервер посчитал свои слова и прислал координатору часть своего списка: несколько самых частых слов с их счётом и порог t — гарантию, что любое неприсланное слово встречается на этом сервере не больше t раз. Общий счёт слова — сумма по всем серверам.
Назовём слово входящим в топ-k, если слов, которые встречаются строго чаще его, меньше k. Слова, которые ни один сервер не прислал, тоже существуют, и сколько их — неизвестно. Для каждого присланного хоть одним сервером слова решите: входит ли оно в топ-k наверняка — при любых настоящих счётах, совместимых с присланным, — или только может входить — хотя бы при одних таких счётах.
Второй пример — «Война и мир», разложенная по четырём томам и эпилогу: каждый том прислал двадцать своих самых частых слов, порог — счёт последнего из них.
Вход
В первой строке m и k (1 ≤ m ≤ 20, 1 ≤ k ≤ 10 000). Дальше m блоков. Блок начинается строкой s t — сколько слов прислал сервер и его порог (1 ≤ s, 0 ≤ t); дальше s строк «слово счёт». Слова — строчные русские буквы, в одном блоке не повторяются; счёты — от 1 до 109, и каждый присланный счёт не меньше порога своего сервера. Всего присланных строк не больше 100 000.
Выход
Четыре строки: число слов, которые входят в топ-k наверняка; сами эти слова через пробел в порядке кодов Unicode (ё после я); число слов, которые могут входить, но не наверняка; эти слова в том же порядке. Пустой список — пустая строка.
Примеры
Пример 1
3 2 2 3 кот 9 пёс 5 3 4 пёс 8 ёж 6 кот 4 2 5 ёж 9 лис 5
0 3 кот пёс ёж
Пример 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 бы ее же за из князь о от по сказал так только
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 12 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Начните с одного слова. Что точно известно про его общий счёт? Сервер, который прислал слово, знает его счёт точно. А сколько оно может встречаться на сервере, который его не прислал?
2Подсказка 2
У каждого слова есть вилка [L, U]: L — сумма присланных счётов, U — та же сумма плюс пороги серверов, которые слово не прислали. Счёты разных слов на разных серверах друг от друга не зависят. Как выглядит худший для слова набор настоящих счётов? Лучший?
3Подсказка 3
Не забудьте слова, которых никто не прислал. У каждого из них общий счёт может доходить до суммы всех порогов, а сколько их — неизвестно.
4Идея
Для слова w худший случай — когда оно встречается L(w) раз, а все остальные — по максимуму: присланные слова по U, неприсланные — по T, сумме всех порогов. Все эти значения можно выбрать одновременно, потому что счёт каждого слова на каждом сервере — отдельная неизвестная. Слово наверняка в топе, если даже тогда строго чаще его встречается меньше k слов: T ≤ L(w) — иначе неприсланных слов, обгоняющих w, может быть сколько угодно, — и присланных v с U(v) > L(w) меньше k.
Лучший случай — w встречается U(w) раз, присланные слова — по L, неприсланных нет вовсе (счёт 0 допустим). Слово может входить в топ, если присланных v с L(v) > U(w) меньше k.
5Разбор
Складываем присланные счёты в L, для каждого слова прибавляем пороги серверов, где его нет, — получаем U. Сортируем отдельно все L и все U; число значений больше заданного находит двоичный поиск. Для «наверняка» из числа U больше L(w) надо вычесть само w, если его U больше его L.
В первом примере наверняка не входит никто. «Ёж» насчитал 15 — больше всех, — но «кот» и «пёс» не прислал третий сервер с порогом 5, и каждый из них мог набрать 18. Значит, любой из троих может оказаться третьим. Зато «лис» не входит даже в лучшем случае: 5 присланных плюс пороги двух серверов дают 12, а у трёх остальных уже прислано 13, 13 и 15.
На «Войне и мире» с двадцатью словами от тома наверняка в топ-20 входят 17 слов, ещё 12 могут входить, — среди них «так» и «из», о которых рассказывает статья. Так и работает настоящая система: Elasticsearch просит у шардов больше значений, чем нужно, и возвращает вместе с ответом оценку возможной ошибки, а если оценка велика, запрос можно повторить с бо́льшим числом значений от шарда.
5+Решение
6Сложность
Сбор вилок — O(N · m) для N присланных строк (порог прибавляется по каждому серверу, где слова нет), сортировка и двоичные поиски — O(N log N).
7Типичные ошибки
- Верить присланному. Сложить счёты и объявить первые k по сумме ответом — так ошибается первый пример: настоящий порядок может быть любым внутри вилок.
- Забыть неприсланные слова. Если сумма порогов больше L(w), где-то может прятаться сколько угодно слов, которые чаще w.
- Нестрогие неравенства. Топ определён через «строго чаще»: слово с равным счётом не обгоняет. Перепутаете > и ≥ — разойдётся граница.
Алгоритмы задачи
O(n log k)
2 задачи
SYS
Структура данных
Count-Min Sketch
Частоты элементов потока в фиксированной памяти: минимум из d счётчиков, ошибка только вверх.
O(d) на элемент и на запрос
2 задачи