Задачник Базовый курс EN

В одном предложении

поиск пересечения двоичный поиск поисковики классика

В «Войне и мире» 31 252 предложения. Поиск по роману должен отвечать на вопросы вроде «в скольких предложениях вместе встречаются „бал“ и „Наташа“». Для каждого слова уже готов список вхождений — номера предложений, где оно есть, по возрастанию. Хранятся списки, как в настоящих поисковых индексах, разностями: первое число — номер первого предложения, каждое следующее — на сколько номер больше предыдущего. Например, предложения 2, 5 и 10 записаны как «2 3 5».

Для каждого запроса из нескольких слов выведите, в скольких предложениях есть все его слова.

Вход

В первой строке — число слов n (1 ≤ n ≤ 5000). Дальше n строк: слово, длина его списка m (m ≥ 1) и m чисел списка в разностях. Слова различны, состоят из строчных русских или латинских букв и цифр, длиной до 20 символов. Номера предложений — от 1 до 10⁶, сумма всех m не больше 3·10⁵.

Затем число запросов q (1 ≤ q ≤ 6·10⁴) и q строк: число слов запроса k (2 ≤ k ≤ 4) и сами слова — различные, каждое есть среди n. Если в каждом запросе взять длину самого короткого из его списков, сумма этих длин по всем запросам не больше 10⁶.

Выход

q строк: для каждого запроса — число предложений, где есть все его слова.

Второй пример — списки шести слов по первым 60 предложениям романа.

Примеры

Пример 1

Вход

4
бал 3 2 3 5
и 6 1 1 2 2 4 1
наташа 3 2 4 4
не 4 3 1 4 2
3
2 бал и
3 наташа и бал
3 не бал наташа

Выход

2
2
1

Пример 2

Вход

6
и 22 5 1 3 1 1 1 9 2 4 1 1 3 3 2 3 5 1 2 1 1 1 9
не 14 9 1 2 11 5 1 2 1 5 3 5 3 1 1
князь 6 9 11 3 2 1 28
анна 5 6 1 9 11 3
павловна 5 6 1 9 11 3
он 6 10 1 1 11 14 15
4
2 анна павловна
3 князь и он
4 он не и князь
2 павловна не

Выход

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 7 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

«Бал» есть в 18 предложениях, «и» — в 13 480. Сколько из этих 13 480 номеров нужно увидеть, чтобы проверить восемнадцать?

2Идея

Списки один раз переводим из разностей в номера — накопленными суммами. Дальше каждый запрос начинаем с самого короткого списка: его номера — кандидаты, и каждый следующий список может их только отсеять. Кандидата ищем в длинном списке не шагом за шагом, а двоичным поиском. Кандидаты идут по возрастанию, поэтому поиск очередного начинается там, где остановился предыдущий: длинный список так и не читается целиком. На каждую пару списков уходит O(m · log n) вместо m + n, где m — длина короткого, n — длинного.

3Разбор

В Python это bisect_left(b, x, lo) с растущей нижней границей lo. В Go — галоп из статьи: от текущей позиции прыжки на 1, 2, 4, 8… вперёд, пока не перепрыгнем кандидата, потом двоичный поиск внутри последнего прыжка. Если до кандидата d мест, галоп смотрит примерно на 2·log₂ d чисел, и на всю пару уходит O(m · log(n/m)). Когда кандидаты кончились, остальные списки запроса можно не трогать.

Годится и другой путь: заранее, один раз, построить для каждого списка множество и проверять кандидатов в нём — O(m) на запрос, зато памяти на хеш-таблицы уходит в разы больше, чем на сами списки. А вот два пальца, как в главе 48 курса, здесь не успевают, хотя ответ дают верный. Они проходят длинный список почти целиком: в третьем тесте это 196 миллионов шагов, хотя сумма длин самых коротких списков — 688 тысяч, в четвёртом — 433 миллиона. В последнем тесте длинный список — 200 000 предложений подряд, и пальцам пришлось бы сделать около десяти миллиардов шагов.

3+Решение

4Сложность

Перевод из разностей — O(сумма m). Запрос — O(m · k · log n), где m — длина самого короткого его списка; при галопе — O(m · k · log(n/m)).

5Типичные ошибки

Два пальца. O(m + n) на пару: длинный список читается от начала до конца на каждом запросе.
Не с самого короткого. Если кандидаты — длинный список, их тысячи, и каждого ищут в остальных.
Множество на каждый запрос. set(длинный) внутри запроса — тот же проход по длинному списку, только спрятанный.
Забыть про разности. Числа во входе — промежутки между номерами, а не сами номера.

Алгоритмы задачи

SYS Структура данных Инвертированный индекс и BM25 Словарь «слово → документы, где оно есть»: запрос читает несколько коротких списков вместо всех текстов. O(сумма длин списков слов запроса); «И» галопом — O(m·log(n/m)) 2 задачи SRT Алгоритм Двоичный поиск Находит границу «нет → да» в упорядоченных данных за log₂ n проверок. O(log n) 2 задачи