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

Задача

Слова в главах

подсчёт уникальных скетч запросы на отрезке аналитика

Для каждой главы «Войны и мира» сохранили HyperLogLog-набросок её слов: m = 2p регистров, каждое слово — 32-битный хеш MurmurHash3, регистр — наибольший ранг попавших в него хешей. Самих текстов под рукой нет. Литературоведу нужно знать, сколько разных слов в главах с a по b, и таких вопросов много.

Оценка по регистрам M0, …, Mm−1 считается так: E = αm·m2 / Σ 2−Mj, где α16 = 0,673, α32 = 0,697, α64 = 0,709, а для m ≥ 128 αm = 0,7213/(1 + 1,079/m); если E ≤ 2,5·m и пустых регистров V > 0, вместо E берётся m·ln(m/V). Ответ на вопрос — оценка по наброску, который получился бы, если пропустить все слова глав с a по b через один набросок.

Вход

В первой строке число глав d и p (1 ≤ d ≤ 400, 4 ≤ p ≤ 10). Дальше d строк по m чисел — регистры глав по порядку (от 0 до 33). Затем число вопросов q (1 ≤ q ≤ 5000) и q строк a b (1 ≤ a ≤ b ≤ d).

Выход

На каждый вопрос — оценку с абсолютной или относительной погрешностью не больше 10−6.

Примеры

Пример 1

Вход
3 3
0 2 0 1 0 0 3 0
1 2 0 0 0 4 0 0
0 0 0 1 0 0 2 0
4
1 1
1 2
1 3
3 3
Выход
3.760029
7.846634
7.846634
2.301457

Пример 2

Вход
10 6
3 6 4 4 6 9 4 7 4 4 4 4 10 6 7 4 4 6 5 4 8 4 2 4 3 3 4 3 2 4 5 4 3 2 5 4 6 4 7 3 3 10 5 6 5 4 2 4 6 5 4 4 4 3 3 3 3 3 5 3 3 5 5 7
3 4 4 6 6 4 3 7 3 4 4 4 3 3 7 6 4 2 3 11 3 3 4 5 3 4 7 2 5 5 5 5 4 4 3 6 5 4 5 3 4 10 4 6 2 3 5 4 5 2 5 5 4 6 4 4 5 3 4 5 3 5 5 4
5 6 4 4 4 9 4 7 3 5 6 6 10 10 5 5 6 3 4 9 2 4 4 5 5 7 4 4 7 5 5 3 3 3 7 3 5 4 9 2 5 3 4 5 4 3 3 4 6 6 7 5 4 3 6 6 5 4 4 4 4 5 3 6
3 6 4 4 6 9 4 5 3 5 3 6 6 4 5 4 4 3 4 4 4 4 4 6 5 3 3 5 5 4 5 3 3 3 5 4 8 5 6 4 5 4 8 5 4 6 5 6 6 5 2 6 4 8 5 5 5 3 4 4 4 5 3 5
3 9 4 7 3 7 4 4 7 3 2 6 6 5 4 6 4 3 5 11 3 4 4 5 5 2 2 3 2 5 5 3 4 2 5 3 5 4 6 3 3 4 2 4 2 4 2 5 5 2 6 6 4 8 4 6 4 3 4 4 2 5 5 5
3 6 4 5 6 9 10 5 6 5 5 6 6 6 6 4 5 4 4 11 4 5 3 5 5 9 6 5 5 4 5 4 7 4 7 6 8 4 6 6 5 10 4 5 4 3 5 5 4 5 7 6 6 8 11 6 8 3 4 6 5 5 6 6
5 2 4 6 6 3 5 6 4 7 4 6 10 6 6 3 4 5 4 4 6 3 5 5 5 1 3 2 2 3 4 5 3 5 4 5 8 7 6 6 8 3 3 6 4 5 2 4 5 5 7 4 6 8 4 2 6 7 4 3 4 5 2 3
5 2 6 4 1 6 3 5 2 2 3 3 10 2 2 2 4 2 4 3 2 9 3 5 4 2 3 5 5 11 2 3 3 1 9 2 4 4 4 1 5 6 6 3 4 3 2 8 7 6 3 3 3 3 4 2 2 7 4 3 2 1 2 5
3 8 4 4 3 9 4 6 2 2 2 3 3 5 2 4 4 2 5 3 5 3 4 3 2 3 3 4 7 9 3 4 3 3 2 8 3 4 2 8 2 10 2 6 5 5 4 3 4 3 3 3 3 3 4 2 6 7 4 2 4 4 3 6
3 3 4 3 3 4 4 1 2 4 3 2 3 3 2 3 4 2 2 4 2 4 3 0 2 1 4 4 2 4 3 5 4 1 2 10 4 5 2 1 3 2 5 1 3 3 3 4 3 3 3 5 2 8 4 0 3 7 4 2 4 3 5 5
3
1 1
1 10
4 7
Выход
637.598957
3598.017587
2449.556455

Ограничения

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

Разбор

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

1Подсказка 1

Что было бы в регистре j, если бы все слова глав с a по b прошли через один набросок? Каждое слово попадает в тот же регистр с тем же рангом, что и в наброске своей главы.

2Подсказка 2

Значит, нужен максимум регистра по отрезку глав — для каждого из m регистров. Отрезков много, а изменений нет: какая структура отвечает на «максимум на отрезке» за O(1)?

3Идея

Набросок объединения — поэлементный максимум набросков: регистр помнит наибольший ранг среди всего, что в него попадало, а попадало то же, что в главы по отдельности. Строим разреженную таблицу: на уровне k для каждой главы i храним поэлементный максимум наброс­ков глав с i по i + 2k − 1. Любой отрезок покрывается двумя такими блоками, которые могут перекрываться, — максимуму это не мешает. На вопрос — максимум двух строк и формула оценки, O(m).

4Разбор

Сумма оценок глав — не ответ: слово «и» есть почти в каждой главе и было бы посчитано сотни раз. На всём романе сумма по главам превышает число разных слов в несколько раз, а максимум по регистрам даёт 48 426 при точных 47 585 — ровно ту же оценку, что набросок всего романа целиком в листинге статьи: объединение наброска не отличается от наброска объединения. Это и делает HyperLogLog удобным для распределённых систем — наброски с разных серверов или за разные дни складываются без потерь точности.

Таблица: уровней ⌊log2 d⌋ + 1, на каждом до d строк по m байт — для 361 главы и 1024 регистров около трёх мегабайт. Вопрос: k = ⌊log2(b − a + 1)⌋, строки a и b − 2k + 1 уровня k, их поэлементный максимум и оценка.

4+Решение
5Сложность

O(m·d log d) на таблицу и O(m) на вопрос.

6Типичные ошибки
  • Сложить оценки глав. Общие слова считаются много раз — уже второй пример.
  • Максимум по отрезку перебором. O(m·(b − a)) на вопрос: на всех главах романа и пяти тысячах вопросов — сотни миллионов операций.
  • Усреднить оценки или регистры. Среднее регистров — набросок «средней главы», а не их объединения.
  • Забыть про поправку для малых чисел. Короткие главы при большом m оставляют пустые регистры.

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

SYS Структура данных HyperLogLog Число разных элементов потока в килобайте памяти: длинные серии нулей в хешах и среднее по регистрам. O(1) на элемент, O(m) на оценку 2 задачи DS Структура данных Разреженная таблица Минимум любого отрезка за O(1) после O(n log n) подготовки: два перекрывающихся блока длиной 2^k. O(1) на запрос, O(n log n) на построение 2 задачи
Каталог алгоритмов