Степан i "Великi любителi Гаррi Потера"#152

Степан i "Великi любителi Гаррi Потера" (Розбір)

Побудуємо граф: вершини — заклинання, ребра — пари спарених заклинань. Комбінація — це шлях із вершини (базове заклинання) у вершину (основне), а її запис — конкатенація рядків уздовж шляху. Вага «входу» у вершину дорівнює довжині її рядка |s_v|.

Крок 1: найкоротша комбінація. Мінімальна довжина запису — це найкоротший шлях у графі з вагами на вершинах, який знаходиться звичайним алгоритмом Дейкстри: релаксація ребра u \to v дає \mathrm{dist}[v] = \mathrm{dist}[u] + |s_v|, база — \mathrm{dist}[1] = |s_1|. При N \le 1000 достатньо навіть найпростішої реалізації за \mathcal{O}(N^2 + M).

Крок 2: лексикографічний мінімум. Серед усіх найкоротших комбінацій треба вибрати найменшу. Для цього для кожної вершини зберігатимемо її найкращого попередника — тобто такого, що конкатенація вздовж отриманого шляху є найменшою з можливих. Попередники утворюють дерево, і рядок для вершини — це рядок її батька плюс власний s_v.

Коли вершина фіналізується Дейкстрою, для кожного сусіда ми або вперше задаємо як попередника, або порівнюємо з поточним попередником вершини і переприв'язуємо до кращого. Це коректно: якщо рядки для і мають однакову довжину, то дописування спільного суфікса s_j зберігає порядок.

Крок 3: як швидко порівняти два рядки. Наївне порівняння коштувало б , а це до 10^6 символів на кожну релаксацію. Натомість застосуємо поліноміальне хешування разом із двійковими підйомами.

Для кожної вершини зберігаємо хеш усього накопиченого рядка — при додаванні s_v він перераховується за за формулою h_v = h_{\text{батька}} \cdot P^{|s_v|} + h(s_v). Крім того, зберігаємо таблицю двійкових підйомів: предків на 2^i кроків угору й сумарну довжину цих кроків. Це дозволяє за \mathcal{O}(\log N) знайти, яка саме вершина покриває символ із заданим глобальним зсувом, і хеш префікса до цього символу.

Тепер порівняння двох рядків рівної довжини — це двійковий пошук найдовшого спільного префікса: перевіряємо рівність хешів префіксів довжини , звужуємо межі й наприкінці порівнюємо перші різні символи. Разом — \mathcal{O}(\log^2) на порівняння.

Наприкінці відновлюємо відповідь, ідучи від вершини по попередниках до вершини , і виводимо конкатенацію у прямому порядку.

Порада: беріть великий простий модуль (наприклад, 10^9+9), а надійніше — два різні модулі, бо кількість порівнянь велика і випадкова колізія зіпсує відповідь.