Вчера закончился длинный тур Открытой олимпиады 2024-25, мне оттуда очень понравилась задача F (инопланетные омофоны). Возможно, некоторые скажут, что там очевидное решение (про которое я тоже напишу), но я таких идей раньше не встречал и не думал в ту сторону. Зато я придумал другое решение, более техничное, но тоже интересное.

Само условие можно найти тут.

Общие идеи для решения:

Чтение очередного слога я буду называть прыжком по строке. Прыжок зависит от текущий позиции (его старт) и от правой границы, до которой мы прыгаем. Слово, которое мы получаем, по факту является массивом из типов звуков. Сравнение двух слов — это сравнение этих двух массивов на равенство. Делать это не хешами звучит очень сложно, поэтому для сравнения подотрезков нам нужно будет посчитать их хеши. Также, для определения, какой именно звук мы произнесём при прочтении слога, мы по факту должны выделить компоненты связности, слоги из одной компоненты звучат одинаково, а из разных — по-разному. Ну и наконец, для определения прыжка очень полезен будет алгоритм Ахо-Корасик, без него никуда не деться. Так как при прыжке у нас фиксирован старт, а конец не фиксирован, строки из набора следует развернуть, а затем проходиться по строке справа-налево (обычный Ахо-Корасик умеет находить слова, которые заканчиваются в какой-то позиции, а если мы разверём слова и направление прохода, то получим слова, которые начинаются в какой-то позиции).

Теперь же перейдём к решениям задачи. Нормальное решение, которое сдало большинство, звучит так:

Мы умеем для позиции искать самое длинное слово, которое начинается в ней. Почему мы не можем всегда делать просто максимальные прыжки? В какой-то момент максимальный прыжок будет пересекать правую границу отрезка. Но до этого момента мы прыгать спокойно можем. А в момент пересечения возникает очень хитрое замечание: оставшийся отрезок строки, который надо пропрыгать — это префикс какой-то строки из набора. Так как суммарная длина строк в наборе $$$S \le 10^6 + 26$$$, мы можем просто решить задачу для каждого префикса каждой строки, тогда мы победим. Информация, которая нам будет нужна — это хеш и количество прыжков, которые мы сделаем (нужны оба параметра для того, чтобы хеши прыжков с двух частей можно было объединить).

А чтобы решить задачу для префикса каждой строки, сделаем так: будем считать ответ в порядке возрастания длин строк в наборе. Тогда применима такая же идея — сначала мы прыгаем, сколько можем, а последний прыжок может оказаться префиксом какой-то строки, но мы её уже были обязаны рассмотреть. Таким образом, за $$$O(S)$$$ мы решили задачу для всех префиксов.

Чтобы быстро понимать в строке $$$t$$$, до куда мы допрыгаем по максимальным прыжкам, можно насчитать бинарные подъёмы. Итого получается $$$O(n \ log \ n)$$$ на эту часть. Общая сложность решения $$$O(n \ log \ n + S)$$$ (алфавит считаем константной). С этой информацией хеш считается за $$$O(1)$$$, так что на запросы мы ответим просто за $$$O(q)$$$.

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

Второе решение:

Решать будем оффлайн, у нас будет $$$2q$$$ запросов вида "посчитать хеш на интервале $$$[l, r)$$$" (для удобства будем считать, что мы должны прийти не в позицию $$$r$$$, которая нам даётся, а в $$$r + 1$$$, потому что после последнего прыжка мы как бы оттуда должны читать следующий слог).

Задачи, в которых есть какие-то прыжки по массиву, иногда позволяет решать техника Разделяй-и-Властвуй по запросам. Попробуем её тут увидеть.

Пусть у нас есть функция $$$solve(l, r, q)$$$, которая решает все запросы с $$$l \le q.l$$$ и $$$q.r < r$$$. Введём середину $$$m = \lfloor \frac{l + r}{2} \rfloor$$$. Поделим запросы на $$$3$$$ типа:

1. $$$q.r < m$$$
2. $$$q.l \ge m$$$
3. Остальные

Первый тип запросов решается так: $$$solve(l, m, q1)$$$. Второй, аналогично, $$$solve(m, r, q2)$$$. Однако перед этим запуском хочется разобраться с запросами третьего типа. Я хочу свести третий тип ко второму, тогда запуск от правой половины решит как 2 так и 3 тип запросов.

Третий тип запросов имеет хорошее свойство — есть прыжок через разрез $$$(m - 1, m)$$$. То есть найдётся такой прыжок, что его старт в левой половине, а старт следующего уже в правой. Если мы научимся делать все прыжки до этого включительно, то мы умеем получать запрос типа 2. Заметим, что все прыжки из левой части в левую никак не зависят от того, какая у запроса правая граница, они и так не могут прыгнуть во вторую половину. Это чем-то напоминает дерево (вернее лес). Каждая позиция — это или корень, который ведёт вправо, или у неё есть предок. С таким деревом задача решается очень просто — храним в позиции хеш до корня и сам корень, из корня делаем прыжок вправо. Однако для прыжка через разрез правая граница запроса уже имеет значение, и, возможно, максимальная строка окажется слишком длинной.

Поэтому мы будем хранить не максимальный прыжок вправо, а минимальный. Таким образом, если минимальный прыжок не заходит за границу запроса, то мы из позиции прыгнем куда-то вправо, но мы точно знаем, что это будет прыжок через разрез. А если минимальный прыжок слишком длинный, то мы точно не перепрыгнем разрез.

Если мы будем отвечать на запросы в порядке убывания правой границы, то для каждой позиции слева минимальный прыжок сначала будет доступен, но в какой-то момент (а именно, когда правая граница будет левее, чем позиция, куда ведёт прыжок) перестанет быть возможным, и тогда позиция слева перестанет быть корнем, её надо будет подвесить к максимальному левому прыжку. Это звучит как СНМ. Оставим от него только сжатие путей. Теперь мы быстро умеем понимать, из какой позиции мы будем делать прыжок через разрез, надо просто вызвать сжатие путей от левой границы запроса. При сжатии путей нам нужно поддерживать хеш прыжков и их количество.

Осталось научиться делать максимальный прыжок вправо, длина которого ограничена правой границей запроса. Мы умеем искать максимальный прыжок с помощью Ахо-Корасика, а также у нас есть суффиксные ссылки в нём. Построим также сжатые суффиксные ссылки — это ссылки, ведущие в ближайшую терминальную вершину. Тогда, если построить бинарные подъёмы на этих ссылках, то мы можем с помощью них найти нужный прыжок. С помощью них же можно найти и минимальный прыжок вправо (это можно ещё и ускорить, сделав предварительно на сжатых ссылках ladder decomposition).

Кратко: идём в порядке убывания правой границы, подвешиваем все минимальные прыжки, которые теперь слишком длинные, все прыжки кроме последнего нам посчитает СНМ, а последний найдём бинарными подъёмами.

По итогу из запроса $$$(l, r)$$$ получаем запрос $$$(l', r)$$$, где $$$l' \ge m$$$, следовательно, его можно пустить во второй тип.

Итоговая сложность: $$$O(n \ log^2 \ n + q \ log \ n \ log \ S + S \ log \ S)$$$.

Выглядит долго, есть несколько оптимизаций, сильно ускоряющих решение. Во-первых, для поиска минимальных прыжков можно использовать ladder decomposition. Во-вторых, как известно, на пути до какой-то вершины может быть не более $$$\sqrt{2S}$$$ терминальных вершин, так что глубина бинарных подъёмов не $$$20$$$, а $$$11$$$.

И последняя. Иногда при разделяйке условие выхода ставится не $$$(l = r)$$$ (в случае полуинтервалов $$$r - l = 1$$$), а $$$r - l \le 10$$$ или $$$r - l \le 30$$$. При этом условии запросы чуть менее тривиально обрабатываются, не просто "Ответ 0" или что-то такое, а пишется наивное решение, которое работает быстрее на маленьких размерах. А как выбирать этот размер и почему вообще происходит ускорение? У классической разделяйки ровно $$$log \ n$$$ слоёв. Однако, если мы выберем некоторый размер $$$B$$$, на котором мы обрубаем рекурсию, то слоёв будет всего лишь $$$log \ (n / B)$$$, или же $$$log \ n - log \ B$$$. В данной задаче наивное решение будет работать за $$$(r - l)^2$$$, что можно оценить сверху как $$$(r - l)B$$$. Поэтому суммарно все наивные решения отработают за $$$nB$$$. Новое время работы получается уже несколько лучше:

$$$O(nB + (log \ n - log \ B) (n \ log \ n + q \ log \ S)$$$. При маленьких $$$B$$$ вторая часть работает явно дольше, чем первая. Поэтому $$$B$$$ можно увеличить. Правда не стоит увеличивать слишком сильно, всё-таки, $$$nB$$$ растёт очень быстро. Если взять $$$B \simeq log \ n$$$, то выходит время уже чуть получше:

$$$O(n \ log \ n + (log \ n - log \ log \ n) (n \ log \ n + q \ log \ S))$$$.

Улучшение несильное, но всё же не стоит такое недооценивать, особенно если умное решение имеет большую константу.

Реализация тут.