Подсказки по роману
Клавиатура подсказывает слово, пока вы его печатаете. Ей нужен словарь: слова и сколько раз каждое встречалось. На каждое набранное начало слова ответьте, сколько слов словаря с него начинается, сколько раз все они встречаются вместе и какое из них самое частое — его клавиатура и покажет первым.
Второй тест — словарь «Войны и мира»: все 47 585 разных слов романа с частотами. Третий — словарь английского перевода Луизы и Эйлмера Мод.
Вход
В первой строке n (1 ≤ n ≤ 10⁵). В следующих n строках — слово и число: сколько раз оно встретилось (от 1 до 10⁶). Слова разные, из строчных русских или латинских букв, длиной до 30, суммарно не больше 10⁶ букв. Дальше q (1 ≤ q ≤ 10⁵) и q строк с началами слов — непустыми, из тех же букв, длиной до 30.
Выход
Для каждого начала — три значения через пробел: число слов словаря, которые с него начинаются, сумма их частот и самое частое из них (при равенстве — первое по алфавиту). Если таких слов нет — 0 0 -.
Примеры
Пример 1
5 наполеон 584 наташи 149 наташа 827 народ 77 мир 47 4 нат на мирный м
2 976 наташа 4 1637 наташа 0 0 - 1 47 мир
Ограничения
- Время · Python
- 6000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 8 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Просмотреть весь словарь на каждое начало — 10⁵ запросов на 10⁵ слов, десять миллиардов проверок. Нужно, чтобы ответ на запрос стоил столько шагов, сколько в нём букв.
2Подсказка 2
Все слова, которые начинаются с данной строки, в боре лежат в одном поддереве. Что нужно знать о поддереве заранее, чтобы ответить, не обходя его?
3Идея
Строим бор и при вставке каждого слова идём по его пути от корня: в каждом узле пути прибавляем единицу к числу слов, частоту — к сумме и сравниваем слово с лучшим, что уже лежит в узле. Каждый узел пути — одно из начал вставляемого слова, поэтому в узле накапливается ответ ровно на «своё» начало. Запрос — спуск по буквам и чтение трёх полей.
4Разбор
Построение стоит суммарную длину слов, запрос — свою длину. Если на какой-то букве ветки нет, слов с таким началом нет, и ответ 0 0 -. «Лучше» значит: больше частота, а при равной частоте — меньше по алфавиту; в Python это одно сравнение пар (−частота, слово).
То же можно сделать без бора: отсортировать слова, найти двоичным поиском отрезок слов с данным началом (от p до p, к которому приписана буква больше всех букв алфавита), сумму частот взять из префиксных сумм, а самое частое — разреженной таблицей максимумов. Получится O(q · |p| · log n), и кода больше. Бор хорош тем, что ответ на каждое начало он копит прямо там, куда приведёт спуск, — так же устроены подсказки в сцене статьи.
4+Решение
5Сложность
O(L + Q) времени, где L — суммарная длина слов словаря, Q — суммарная длина запросов. Память — O(L) узлов.
6Типичные ошибки
- Перебор словаря на каждый запрос. Второй тест — 47 585 слов и 50 000 запросов, больше двух миллиардов проверок
startswith. - Самое частое без учёта равенства. В седьмом тесте у всех слов одна частота, и нужно первое по алфавиту.
- Сравнение строк в Go. Сравнение строк
<побайтовое, но для UTF-8 оно совпадает с порядком букв; а вот номер символа в строке и номер байта — разные вещи, поэтому идти по слову нужноfor _, ch := range w.