Вчера закончился длинный тур Открытой олимпиады 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$$$ типа:
- $$$q.r < m$$$
- $$$q.l \ge m$$$
- Оставшиеся
Чтобы решить запросы первого и второго типа, мы можем просто вызвать функцию $$$solve(l, m, q1)$$$ и $$$solve(m, r, q2)$$$, а вот с третьим типом мы должны разобраться отдельно. Сведём все запросы 3 типа к запросам 2 типа.
Мы будем активно пользоваться таким фактом — все запросы третьего типа имеют прыжок, начинающийся в левой половине и заканчивающийся в правой. Давайте для каждого сделаем все прыжки до такого включительно. Для этого нам пригодится понимать, с какой позиции мы сделаем прыжок через разрез $$$(m - 1, m)$$$. У каждой позиции из левой половины есть какие-то прыжки, ведущие в правую половину. Если их кратчайший прыжок вправо меньше, чем $$$q.r$$$ у запроса, то они — кандидат на прыжок вправо, а иначе из них будет идти максимальный прыжок в левую половину (для каждой позиции такой прыжок ровно один).
