Спасибо.

Ну вот и получается, что та информация не совсем точная. От MГУ отобрались 5 команд (хотя указано что, должно быть 3), от СГУ — 3 (хотя указано, что должно быть 2).

Это круто, что от сильных Вузов проходит больше команд, но то, что эти квоты "плавают" и не совпадают с офф. информацией — как-то странно.

У нас решение было за O(n^2) с хешами. Переберем подстроку из первой строки. Найдем все ее вхождения (непересекающиеся). Одинаковые подстроки будем обрабатывать один раз за O(количество таких подстрок). Для этого каждый раз будем считать хеш строки, которая получится, если заменить все непересекающиеся вхождения этой подстроки. Исходя из длин строк и количества вхождений, можно определить длину строки, на которую необходимо заменять текущую подстроку. Саму строку, на которую будем заменять, тоже можно определить однозначно — это подстрока второй строки, которая начинается с символа, который соответствует первому вхождению подстроки в первую строку.

У нас решение за честный чистый квадрат без хэшей.

Основные идеи:

1. За квадрат можно сделать несколько предподсчётов вида "lcp s[i..n] и t[j..m]" (это очевидная динамика с двумя переходами — два цикла),
2. Пусть мы зафиксировали первое вхождение строки X, которую меняем в строке A (A была изначально, надо получить B). Надо, во-первых, проверить, что это действительно первое вхождение (надо просто при движении левой границы поддерживать минимальную длину при помощи предподсчёто). Во-вторых, давайте как-нибудь найдём все последующие вхождения этой строки в A, которые будут заменены. Пока за линию (уже куб).
3. Пусть получилось K вхождений. Тогда за O(K) мы можем проверить, верно ли, что такая замена нам подходит. В самом деле, мы знаем, сколько символов останутся нетронутыми, а значит знаем длину строки Y, на которую заменим X. Также очевидно знаем, какие куски останутся нетронутыми (их K+1). Теперь надо проверить, что эти куски действительно не изменились по сравнению с A, а оставшиеся K одинаковы. Это действие выполняется за O(K).
4. Теперь заметим, что пункт три работает за квадрат. В самом деле, каждая подстрочка (а их квадрат) обрабатывается как "кандидат на замену (не обязательно первый)" только один раз.
5. Оптимизация второго пункта: при фиксированной левой границе и увеличивающейся правой будем поддерживать список позиций, из которых может начаться новое вхождение (LCP >= текущей длины). Если на какой-то позиции LCP стал слишком мал — выкинули из списка. Таким образом у нас в каждый момент бесплатно есть все вхождения данной подстроки в A. Из них можно жадно выбрать нужные по условию. При этом данная оптимизация также работает за квадрат по тем же соображениям из пункта 4.

Все материалы четвертьфинала доступны здесь.

Спасибо — но разбор короткий :)