Словарное разнообразие
Текст — последовательность из n слов. Для каждого куска из w подряд идущих слов посчитаем, сколько в нём разных слов. Найдите кусок с наибольшим числом разных слов и кусок с наименьшим; если таких несколько, нужен самый левый.
Второй тест — четвёртый том «Войны и мира», третий — эпилог, четвёртый — начало романа в переводе Луизы и Эйлмера Мод. Во всём романе в окне из тысячи слов бывает от 353 до 683 разных слов; самое однообразное место — рассуждение о свободе и необходимости во второй части эпилога.
Вход
В первой строке n и w (1 ≤ w ≤ n ≤ 2·10⁵), во второй — n слов из строчных букв.
Выход
Две строки: наибольшее число разных слов и номер первого слова этого куска, затем наименьшее и номер первого слова (слова нумеруются с единицы).
Примеры
Пример 1
9 3 the cat sat on the mat the cat ran
3 1 2 5
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Соседние куски отличаются двумя словами: одно вошло справа, одно вышло слева. Что нужно помнить о куске, чтобы по этим двум словам сразу узнать, как изменилось число разных слов?
2Идея
Окно хранит счётчик для каждого слова: сколько раз оно встречается внутри. Когда слово входит, его счётчик растёт; если он был нулём, разных слов стало на одно больше. Когда слово выходит, счётчик уменьшается; если стал нулём — на одно меньше. Каждый сдвиг стоит два обращения к хеш-таблице.
3Разбор
Сначала заполняем окно первыми w словами, потом сдвигаем его n − w раз, следя за наибольшим и наименьшим значением. Чтобы ответ был самым левым, обновляем рекорд только при строгом улучшении.
Удалять слово из таблицы, когда его счётчик стал нулём, не обязательно, но так таблица не разрастается до размера всего словаря текста.
3+Решение
4Сложность
O(n) операций с хеш-таблицей и O(w) памяти, если удалять нулевые счётчики.
5Типичные ошибки
- Пересчитывать каждое окно заново. O(n·w): во втором тесте это почти сто миллионов операций, в шестом — пять миллиардов.
- Окно на одно слово больше или меньше. Выходит слово с номером i − w, а не i − w − 1; проверьте на примере, где w = 3.
- Не самый левый кусок. При равном числе разных слов рекорд не обновляется.