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

Сверка реплик

хеширование дерево распределённые системы префиксные суммы

Две реплики базы данных хранят по n блоков, и по сети нужно выяснить, какие блоки разошлись. Пересылать все блоки дорого, поэтому обе стороны строят над ними одинаковое дерево Меркла и сверяют хеши сверху вниз. Дерево устроено как в RFC 6962: если в отрезке больше одного блока, левое поддерево берёт наибольшую степень двойки, меньшую длины отрезка, правое — остаток.

Сверка начинается с корней. Если хеши узлов совпали, внутрь не заходят: всё под ними одинаково. Если не совпали и узел — один блок, этот блок разошёлся. Если не совпали и узел внутренний, сверяют оба его поддерева. Каждая сверка пары узлов — одно сравнение. Совпадений хешей у разных данных не бывает.

По содержимому блоков обеих реплик найдите, сколько сравнений сделает сверка и какие блоки разошлись. Среди тестов — исходники этого сайта на двух коммитах: блок — файл, его содержимое — идентификатор git или «-», если файла в этой версии нет.

Вход

В первой строке n (1 ≤ n ≤ 5·10⁴). Во второй — n блоков первой реплики, в третьей — второй: слова из латинских букв, цифр и знака «-» длиной до 12 символов.

Выход

В первой строке — число сравнений. Во второй — номера разошедшихся блоков по возрастанию через пробел (нумерация с единицы) или «-», если реплики совпадают.

Примеры

Пример 1

Вход

8
162bb1f0 878c8d3f f0fe0865 269cb77c 04ceca25 baa3ba11 17640f86 be3c2e6e
162bb1f0 878c8d3f f0fe0865 269cb77c 04ceca25 5e93c4cd 17640f86 be3c2e6e

Выход

7
6

Пример 2

Вход

5
0ff6d13d c30c45e6 8b53e711 80eb0941 a373041e
08ed8f88 c30c45e6 8b53e711 80eb0941 46553a59

Выход

7
1 5

Ограничения

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

Разбор

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

1Подсказка 1

Считать SHA-256 не обязательно. Когда хеши двух узлов различаются, если совпадений у разных данных не бывает?

2Подсказка 2

Узел различается тогда и только тогда, когда в его отрезке есть хотя бы один разошедшийся блок. Как быстро узнать, есть ли такой блок в отрезке [l, r)?

3Идея

Отметим разошедшиеся блоки и посчитаем префиксные суммы отметок: в отрезке есть различие, если сумма на нём не ноль. Дальше повторяем сверку буквально: стек отрезков, начиная с [0, n); каждый снятый отрезок — одно сравнение; если различий нет — дальше не идём; если отрезок из одного блока — записываем его; иначе кладём два поддерева.

4Разбор

В первом примере восемь блоков, разошёлся шестой. Сверка: корень (различается), обе половины по четыре блока (правая различается), обе четвертушки правой половины (различается левая — блоки 5 и 6), и наконец блоки 5 и 6 по отдельности. Всего 1 + 2 + 2 + 2 = 7 сравнений вместо восьми. Выгода видна на больших репликах: в седьмом тесте пятьдесят тысяч блоков и двадцать расхождений, а сравнений — несколько сотен.

Сколько в общем случае? Каждый различающийся внутренний узел добавляет два сравнения — своих детей. Различающихся узлов не больше, чем разошедшихся блоков, умноженных на глубину дерева, поэтому сравнений O(d log n) для d расхождений — и не больше 2n − 1, если различается всё. Худший случай для протокола — расхождения, раскиданные равномерно, как в девятом тесте: каждое тянет за собой отдельный путь от корня. Соседние расхождения, как в восьмом, делят верх пути и обходятся дешевле.

Шестой тест — исходники этого сайта на двух коммитах, 4224 файла, 64 из них разные. Двоичное дерево находит их за 423 сравнения. Сам git сверяет иначе — по папкам, и в статье о дереве Меркла на тех же двух коммитах выходит 758 сравнений: у папки бывают сотни детей, и при различии сверяются все. Двоичное дерево платит за это глубиной: путь к блоку длиннее.

4+Решение

5Сложность

O(n) на префиксные суммы и O(число сравнений) на сверку — не больше O(n).

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

Считать только различающиеся узлы. Сравнение стоит одинаково, совпадут хеши или нет: совпавший сосед различающегося узла тоже сравнивался. В первом примере такой счёт даёт 4 вместо 7.
Делить отрезок пополам. В RFC 6962 левому поддереву достаётся наибольшая степень двойки, меньшая длины: для пяти блоков это 4 и 1, а не 2 и 3. Во втором примере от этого зависит число сравнений.
Забыть про совпадающие реплики. Корни совпали — одно сравнение, и выводится «-».

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

SYS Структура данных Дерево Меркла Хеши хешей: отпечаток всего набора, поиск расхождений за несколько сравнений и доказательство из log n хешей. O(n) на построение, O(log n) на доказательство и его проверку 2 задачи TEC Приём Префиксные суммы Сумма любого отрезка за O(1) после одного прохода; двумерный вариант считает сумму любого прямоугольника картинки. O(n) на построение, O(1) на запрос 2 задачи