Мне нравится идея [user:Endagorion,2015-10-25] дополнять разбор задач небольшими упражнениями, связанными с подготовкой задачи, её обобщением или наличием более эффективного решения. Попробуем и мы предложить читателю подобные вопросы по некоторым задачам.↵
Div. 2A (Поединок волшебников)↵
------------------↵
Автор идеи: Роман Гусарев, разработка: [user:timgaripov,2015-10-25].↵
↵
Найдем координату первого столкновения импульсов. Они сближаются со скоростью $p + q$, а значит первое столкновение произойдёт через $\frac{L}{p + q}$ секунд. Следовательно, координата первого столкновения может быть вычислена как $x_1 = p \cdot \frac{L}{p + q}$.↵
↵
Заметим теперь, что расстояние проходимое импульсами на обратном пути до волшебников равно расстоянию проходимому ими от волшебников до места первой встречи. Это значит, что импульсы вернутся к волшебникам одновременно, и ситуация станет идентична изначальной. Таким образом, вторая встреча (и все последующие) произойдёт в той же точке, что и первая.↵
↵
Пример решения: [submission:13836780].↵
↵
Div. 2B (Ребрендинг)↵
------------------↵
Автор идеи: [user:glebushka98,2015-10-25], разработка: [user:thefacetakt,2015-10-25].↵
↵
Тривиальное решение: будем эмулировать работу дизайнеров, а именно каждый раз ходить и честно перекрашвать все $x_i$ в $y_i$ и наоборот. Работает за $\mathcal{O}(n \cdot m)$, получает TL.↵
↵
Попробуем улучшить этот результат.↵
↵
Заметим, что одинаковые буквы переходят в одинаковые. Это означает, что позиция буквы никак не влияет на результат, и достаточно помнить для каждого возможного значения символа, во что он перейдёт. Пусть $p(i, c)$ — символ, который будет стоять вместо всех вхождений $c$ после обработки $i$ дизайнеров. Тогда:↵
<ul>↵
<li> $p(0, c) = c$ </li>↵
<li> Если $p(i - 1, c) = x_i$, то $p(i, c) = y_i$ </li>↵
<li> Аналогично, если $p(i - 1, c) = y_i$, то $p(i, c) = x_i$ </li>↵
</ul>↵
↵
Данное решение работает уже за $O(|\Sigma| \cdot m + n)$ и проходит все тесты.↵
↵
Упражнение: доведите решение данной задачи до сложности $O(\Sigma + n + m)$.↵
↵
Примеры решения: [submission:13837577] за $O(|\Sigma| \cdot m + n)$ и [submission:13839154] за $O(|\Sigma| + n + m)$.↵
↵
Div. 2C\Div. 1A (Медианное сглаживание)↵
------------------↵
Автор идеи и разработчик: [user:Sender,2015-10-25].↵
↵
Назовём статичными точками позиции, которые не могут измениться, сколько бы раз мы не применяли к последовательности алгоритм медианного сглаживания. Оба конца являются статичными точками по определению. Также, легко заметить, что если рядом стоят два одинаковых символа, то обе эти позиции так же являются статичными точками.↵
↵
Исследуем влияние статичных точек на соседние элементы. Пусть $a_{i - 1} = a_i$, то есть элемемнты $i - 1$ и $i$ являются статичными точками. Пусть также $a_{i + 1}$ статичной точкой пока не является, следовательно $a_{i + 1} \ne a_i$ и $a_{i + 1} \ne a_{i + 2}$. Из предыдущего предложения и того, что возможны только $0$ и $1$ делаем вывод, что $a_i = a_{i + 2}$ и после одного применения алгоритма медианного сглаживания будет выполнено $a_i = a_{i + 1}$. То есть любая статичная точка за один шаг превращает все соседние элементы в статичные точки. Таким образом, любая последовательность в итоге стабилизируется.↵
↵
Остаётся только вычислить скорость стабилизации и результирующие значения. Заметим, что если между двумя статичными точками $i$ и $j$ нет других статичных точек, то это означает чередование всех символов между позициями $i$ и $j$. Несложно проверить, что в чередующейся последовательности новые статичные точки не образуются, следовательно последовательность будет оставаться чередующейся пока до неё не дойдёт влияние одной из соседних статичных точек.↵
↵
Итоговое решение: выделим все статичные точки в изначальной последовательности и найдём $max(min(|i - s_j|))$, где $s_j$ — множество индексов позиций статичных точек. Сложность решения $O(n)$.↵
↵
Упражнение 1: взломайте решение честно моделирующее применение алгоритма медианного сглаживания до стабилизации процесса.↵
↵
Упражнение 2: придумайте как ускорить квадратичное решение с помощью битового сжатия (и всё равно получить TL).↵
↵
Примеры решений: [submission:13838940] и [submission:13838480].↵
↵
Div. 2D\Div. 1B (Чип и Дейл спешат на помощь)↵
------------------↵
Автор идеи и разработчик: [user:StopKran,2015-10-25].↵
↵
Заметим, что если собственная скорость дирижабля задана вектором $(a_x, a_y)$, а скорость ветра вектором $(b_x, b_y)$, то реальный вектор движения дирижабля определяется как $(a_x + b_x, a_y + b_y)$.↵
↵
Одним из ключевых моментов в решении задачи является понимание монотонности функции ответа по времени. Если дирижабль может достичь цели за $\tau$ секунд, то он сможет достичь её и за $\tau + x$ секунд, для любого $x \ge 0$. Это очевидно вытекает из условия, что максимально возможная собственная скорость дирижабля строго превосходит скорость ветра в любой момент времени. ↵
↵
Поскольку функция ответа монотонна, воспользуемся методом бинарного поиска по ответу, а именно, научимся проверять для фиксированного параметра $\tau$, возможно ли добраться от точки $(x_1, y_1)$ до точки $(x_2, y_2)$ за время $\tau$. Будем учитывать перемещение под действием ветра и собственное перемещение отдельно. Найдём сперва смещение дирижабля вызванное ветром:↵
↵
<ul>↵
<li> $(x_n, y_n)$ = $(x_1 + v_x \cdot \tau, y_1 + v_y \cdot \tau)$, если $\tau \leq t$; </li>↵
<li> $(x_n, y_n)$ = $(x_1 + v_x \cdot t + v_x \cdot (\tau - t), y_1 + v_y \cdot t + v_y \cdot (\tau - t))$, если $\tau > t$. </li>↵
</ul>↵
↵
Остаётся только проверить, что используя только лишь собственную скорость можно добраться за время $\tau$ из точки $(x_n, y_n)$ в точку $(x_2, y_2)$.↵
↵
Итоговая сложность: $O(log \frac{C}{\epsilon})$, где $C$ — максимальная координата, а $\epsilon$ — требуемая точность.↵
↵
Упражнение 1: подумайте как решить задачу, в случае когда не гарантируется, что дирижабль всегда быстрее ветра.↵
↵
Упражнение 2: можете ли вы решить задачу за время $O(1)$?↵
↵
Примеры решений: [submission:13838659] и [submission:13842505].↵
↵
Div. 2E\Div. 1C (Три государства)↵
------------------↵
Автор идеи и разработчик: [user:haku,2015-10-25].↵
↵
**Утверждение.** Пусть в неориентированном невзвешенном связном графе выделенны три различные вершины $u$, $v$, $w$. Одна из минимальных сетей, связывающих выделенные вершины, выглядит как некоторая вершина графа $c$, возможно совпадающая с одной из выделенных, из которой исходят кратчайшие пути к каждой из выделенных вершин, причём эти пути являются вершинно-непересекающимися.↵
↵
**Доказательство.** Одним из оптимальных связывающих подграфов обязательно является дерево. Действительно, в противном случае на любом цикле найдётся ребро, которое можно выкинуть, и это не ухудшит ответ, поскольку он не зависит от количества используемых рёбер. Листьями дерева могу являться только вершины $u$, $v$ и $w$, иначе ответ можно было бы улучшить, просто выкинув такой листь. Дерево, у которого не более чем три листа, имеет не более одной вершины степени больше двух, которая и будет вершиной $c$ из утверждения выше. Разумеется, любой путь от $c$ до листа имеет смысл заменить на кратчайший. Отдельно возможен вырожденный случай, что дерево ответа — это бамбук, но в таком случае вершиной $c$ является одна из трёх выделенных вершин (не лист).↵
↵
Теперь имеем следующий метод для нахождения длины кратчайшей связывающей сети: перебрать все вершины, включая выделенные, и из сумм кратчайших расстояний от данной вершины до выделенных выбрать минимальную. Ясно, что таким образом мы переберём длины различных связывающих сетей, среди которых будет и длина кратчайшей, и поэтому минимум будет ответом.↵
↵
Для сведения исходной задачи к задаче поиска минимальной связывающей сети, можно представить карту в виде графа, где вершинам соответствуют клетки, принадлежащие государствам или допускающие постройку дороги, а ребро между двумя вершинами ставится, если они являются соседними в таблице. Все вершины, соответствующие одному государству, необходимо сжать в одну. Несложно заметить, что исходная задача таким образом свелась к вышеописанной.↵
↵
Примеры решений: [submission:13843265] — описанное решение реализовано через бфс на 0-1 графе, [submission:13840329] — здесь логика решения несколько иная, разбираются два принципиально разных случая.↵
↵
Div. 1D (Сверхсекретное задание)↵
------------------↵
Автор идеи и разработчик: [user:glebushka98,2015-10-25].↵
↵
Если $s > \frac{n \cdot (n - 1)}{2}$, то ответом является сумма $k$ минимальных элементов. ↵
↵
Пусть $i_1<i_2<$ ... $<i_k$ — индексы элементов, которые войдут в итоге в ответ. Заметим, что относительный порядок выбранных элементов менять не имеет смысла, а значит, мы можем однозначно сказать, какой из выбранных элементов займёт какую позицию в ответе. $T$ — минимальное количество операций, за которое их можно поставить на $k$ первых мест. $T=(i_1 - 1) + ... +(i_k - k)=\sum\limits_{p = 1}^ki_p$ — $\dfrac{k\cdot(k+1)}{2}$.↵
↵
$T$$\le$$S$ $\Rightarrow$ $\sum\limits_{p=1}^ki_p$ $\le$ $\dfrac{k\cdot(k+1)}{2}+S$. $M=\dfrac{k\cdot(k+1)}{2}+S$. ↵
↵
Посчитаем динамику $d[i][j][p]$ — минимально возможная сумма, если среди первых $i$ элементов выбрать $j$ с суммой индексов не больше $p$. В целях оптимизации использования памяти будем хранить каждый раз только два верхних уровня динамики.↵
↵
Итоговая сложность решения: $O(n^4)$ по времени и $O(n^3)$ по памяти.↵
↵
Примеры решений: [submission:13845513] и [submission:13845571].↵
↵
Div. 1E (День рождения)↵
------------------↵
Автор идеи: [user:_meshanya_,2015-10-25], разработчик: [user:romanandreev,2015-10-25].↵
↵
Задача естественно разбивается на две подзадачи: быстрое построение графа вложенности и нахождение максимального независимого множества в этом графе. Заметим сразу, что если строка $s_2$ является подстрокой строки $s_1$, а строка $s_3$ является подстрокой строки $s_2$, то $s_3$ очевидно является подстрокой строки $s_1$. Таким образом, граф вложений зададаёт частично упорядоченное множество.↵
↵
Для быстрого построения графа воспользуемся алгоритмом [Ахо-Корасик](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA). С помощью данной структуры мы построим все существенные рёбра графа, то есть такие рёбра $uv \in E$, что не найдётся $w$, такого что $uw \in E$ и $wv \in E$. Одним из возможных способов является:↵
<ul>↵
<li> Построить структуру Ахо-Корасик; </li>↵
<li> Для каждой вершины найти и запомнить ближайшую терминальную в суффиксном пути; </li>↵
<li> Ещё раз скормить каждую строку автомату Ахо-Корасик, при этом каждый раз после добавления очередного символа требуется проводить ребро в ближайшую терминальную вершину в суффиксном пути; </li>↵
<li> Кроме существенных рёбер, данный алгоритм возможно добавит ещё какие-то корректные рёбра, но это никак не влияет на результат работы следующего шага; </li>↵
<li> Транзитивно замкнуть построенный граф. </li>↵
</ul>↵
↵
Для решение второй части данной задачи требует применить [теорему Дилворта](https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%94%D0%B8%D0%BB%D1%83%D0%BE%D1%80%D1%81%D0%B0). Восстановление ответа следует из конструктивного доказательства теоремы. ↵
↵
Получаем $O(L + n^3)$ на построение графа + $O(n^3)$ на нахождение максимальной антицепи, итоговая сложность решения: $O(L + n^3)$, где $L$ — суммарная длина всех строк.↵
↵
Поздравляем [user:ikatanic,2015-10-26] — единственного человека сдавшего эту задачу во время тура. Для дальнейшего уточнения решения предлагается посмотреть [submission:13851141].↵
↵
Упражнение: научитесь решать задачу с сохранением асимптотики, при условии что требуется найти множество строк максимальное не по размеру, а по суммарной длине.
Div. 2A (Поединок волшебников)↵
------------------↵
Автор идеи: Роман Гусарев, разработка: [user:timgaripov,2015-10-25].↵
↵
Найдем координату первого столкновения импульсов. Они сближаются со скоростью $p + q$, а значит первое столкновение произойдёт через $\frac{L}{p + q}$ секунд. Следовательно, координата первого столкновения может быть вычислена как $x_1 = p \cdot \frac{L}{p + q}$.↵
↵
Заметим теперь, что расстояние проходимое импульсами на обратном пути до волшебников равно расстоянию проходимому ими от волшебников до места первой встречи. Это значит, что импульсы вернутся к волшебникам одновременно, и ситуация станет идентична изначальной. Таким образом, вторая встреча (и все последующие) произойдёт в той же точке, что и первая.↵
↵
Пример решения: [submission:13836780].↵
↵
Div. 2B (Ребрендинг)↵
------------------↵
Автор идеи: [user:glebushka98,2015-10-25], разработка: [user:thefacetakt,2015-10-25].↵
↵
Тривиальное решение: будем эмулировать работу дизайнеров, а именно каждый раз ходить и честно перекрашвать все $x_i$ в $y_i$ и наоборот. Работает за $\mathcal{O}(n \cdot m)$, получает TL.↵
↵
Попробуем улучшить этот результат.↵
↵
Заметим, что одинаковые буквы переходят в одинаковые. Это означает, что позиция буквы никак не влияет на результат, и достаточно помнить для каждого возможного значения символа, во что он перейдёт. Пусть $p(i, c)$ — символ, который будет стоять вместо всех вхождений $c$ после обработки $i$ дизайнеров. Тогда:↵
<ul>↵
<li> $p(0, c) = c$ </li>↵
<li> Если $p(i - 1, c) = x_i$, то $p(i, c) = y_i$ </li>↵
<li> Аналогично, если $p(i - 1, c) = y_i$, то $p(i, c) = x_i$ </li>↵
</ul>↵
↵
Данное решение работает уже за $O(|\Sigma| \cdot m + n)$ и проходит все тесты.↵
↵
Упражнение: доведите решение данной задачи до сложности $O(\Sigma + n + m)$.↵
↵
Примеры решения: [submission:13837577] за $O(|\Sigma| \cdot m + n)$ и [submission:13839154] за $O(|\Sigma| + n + m)$.↵
↵
Div. 2C\Div. 1A (Медианное сглаживание)↵
------------------↵
Автор идеи и разработчик: [user:Sender,2015-10-25].↵
↵
Назовём статичными точками позиции, которые не могут измениться, сколько бы раз мы не применяли к последовательности алгоритм медианного сглаживания. Оба конца являются статичными точками по определению. Также, легко заметить, что если рядом стоят два одинаковых символа, то обе эти позиции так же являются статичными точками.↵
↵
Исследуем влияние статичных точек на соседние элементы. Пусть $a_{i - 1} = a_i$, то есть элемемнты $i - 1$ и $i$ являются статичными точками. Пусть также $a_{i + 1}$ статичной точкой пока не является, следовательно $a_{i + 1} \ne a_i$ и $a_{i + 1} \ne a_{i + 2}$. Из предыдущего предложения и того, что возможны только $0$ и $1$ делаем вывод, что $a_i = a_{i + 2}$ и после одного применения алгоритма медианного сглаживания будет выполнено $a_i = a_{i + 1}$. То есть любая статичная точка за один шаг превращает все соседние элементы в статичные точки. Таким образом, любая последовательность в итоге стабилизируется.↵
↵
Остаётся только вычислить скорость стабилизации и результирующие значения. Заметим, что если между двумя статичными точками $i$ и $j$ нет других статичных точек, то это означает чередование всех символов между позициями $i$ и $j$. Несложно проверить, что в чередующейся последовательности новые статичные точки не образуются, следовательно последовательность будет оставаться чередующейся пока до неё не дойдёт влияние одной из соседних статичных точек.↵
↵
Итоговое решение: выделим все статичные точки в изначальной последовательности и найдём $max(min(|i - s_j|))$, где $s_j$ — множество индексов позиций статичных точек. Сложность решения $O(n)$.↵
↵
Упражнение 1: взломайте решение честно моделирующее применение алгоритма медианного сглаживания до стабилизации процесса.↵
↵
Упражнение 2: придумайте как ускорить квадратичное решение с помощью битового сжатия (и всё равно получить TL).↵
↵
Примеры решений: [submission:13838940] и [submission:13838480].↵
↵
Div. 2D\Div. 1B (Чип и Дейл спешат на помощь)↵
------------------↵
Автор идеи и разработчик: [user:StopKran,2015-10-25].↵
↵
Заметим, что если собственная скорость дирижабля задана вектором $(a_x, a_y)$, а скорость ветра вектором $(b_x, b_y)$, то реальный вектор движения дирижабля определяется как $(a_x + b_x, a_y + b_y)$.↵
↵
Одним из ключевых моментов в решении задачи является понимание монотонности функции ответа по времени. Если дирижабль может достичь цели за $\tau$ секунд, то он сможет достичь её и за $\tau + x$ секунд, для любого $x \ge 0$. Это очевидно вытекает из условия, что максимально возможная собственная скорость дирижабля строго превосходит скорость ветра в любой момент времени. ↵
↵
Поскольку функция ответа монотонна, воспользуемся методом бинарного поиска по ответу, а именно, научимся проверять для фиксированного параметра $\tau$, возможно ли добраться от точки $(x_1, y_1)$ до точки $(x_2, y_2)$ за время $\tau$. Будем учитывать перемещение под действием ветра и собственное перемещение отдельно. Найдём сперва смещение дирижабля вызванное ветром:↵
↵
<ul>↵
<li> $(x_n, y_n)$ = $(x_1 + v_x \cdot \tau, y_1 + v_y \cdot \tau)$, если $\tau \leq t$; </li>↵
<li> $(x_n, y_n)$ = $(x_1 + v_x \cdot t + v_x \cdot (\tau - t), y_1 + v_y \cdot t + v_y \cdot (\tau - t))$, если $\tau > t$. </li>↵
</ul>↵
↵
Остаётся только проверить, что используя только лишь собственную скорость можно добраться за время $\tau$ из точки $(x_n, y_n)$ в точку $(x_2, y_2)$.↵
↵
Итоговая сложность: $O(log \frac{C}{\epsilon})$, где $C$ — максимальная координата, а $\epsilon$ — требуемая точность.↵
↵
Упражнение 1: подумайте как решить задачу, в случае когда не гарантируется, что дирижабль всегда быстрее ветра.↵
↵
Упражнение 2: можете ли вы решить задачу за время $O(1)$?↵
↵
Примеры решений: [submission:13838659] и [submission:13842505].↵
↵
Div. 2E\Div. 1C (Три государства)↵
------------------↵
Автор идеи и разработчик: [user:haku,2015-10-25].↵
↵
**Утверждение.** Пусть в неориентированном невзвешенном связном графе выделенны три различные вершины $u$, $v$, $w$. Одна из минимальных сетей, связывающих выделенные вершины, выглядит как некоторая вершина графа $c$, возможно совпадающая с одной из выделенных, из которой исходят кратчайшие пути к каждой из выделенных вершин, причём эти пути являются вершинно-непересекающимися.↵
↵
**Доказательство.** Одним из оптимальных связывающих подграфов обязательно является дерево. Действительно, в противном случае на любом цикле найдётся ребро, которое можно выкинуть, и это не ухудшит ответ, поскольку он не зависит от количества используемых рёбер. Листьями дерева могу являться только вершины $u$, $v$ и $w$, иначе ответ можно было бы улучшить, просто выкинув такой листь. Дерево, у которого не более чем три листа, имеет не более одной вершины степени больше двух, которая и будет вершиной $c$ из утверждения выше. Разумеется, любой путь от $c$ до листа имеет смысл заменить на кратчайший. Отдельно возможен вырожденный случай, что дерево ответа — это бамбук, но в таком случае вершиной $c$ является одна из трёх выделенных вершин (не лист).↵
↵
Теперь имеем следующий метод для нахождения длины кратчайшей связывающей сети: перебрать все вершины, включая выделенные, и из сумм кратчайших расстояний от данной вершины до выделенных выбрать минимальную. Ясно, что таким образом мы переберём длины различных связывающих сетей, среди которых будет и длина кратчайшей, и поэтому минимум будет ответом.↵
↵
Для сведения исходной задачи к задаче поиска минимальной связывающей сети, можно представить карту в виде графа, где вершинам соответствуют клетки, принадлежащие государствам или допускающие постройку дороги, а ребро между двумя вершинами ставится, если они являются соседними в таблице. Все вершины, соответствующие одному государству, необходимо сжать в одну. Несложно заметить, что исходная задача таким образом свелась к вышеописанной.↵
↵
Примеры решений: [submission:13843265] — описанное решение реализовано через бфс на 0-1 графе, [submission:13840329] — здесь логика решения несколько иная, разбираются два принципиально разных случая.↵
↵
Div. 1D (Сверхсекретное задание)↵
------------------↵
Автор идеи и разработчик: [user:glebushka98,2015-10-25].↵
↵
Если $s > \frac{n \cdot (n - 1)}{2}$, то ответом является сумма $k$ минимальных элементов. ↵
↵
Пусть $i_1<i_2<$ ... $<i_k$ — индексы элементов, которые войдут в итоге в ответ. Заметим, что относительный порядок выбранных элементов менять не имеет смысла, а значит, мы можем однозначно сказать, какой из выбранных элементов займёт какую позицию в ответе. $T$ — минимальное количество операций, за которое их можно поставить на $k$ первых мест. $T=(i_1 - 1) + ... +(i_k - k)=\sum\limits_{p = 1}^ki_p$ — $\dfrac{k\cdot(k+1)}{2}$.↵
↵
$T$$\le$$S$ $\Rightarrow$ $\sum\limits_{p=1}^ki_p$ $\le$ $\dfrac{k\cdot(k+1)}{2}+S$. $M=\dfrac{k\cdot(k+1)}{2}+S$. ↵
↵
Посчитаем динамику $d[i][j][p]$ — минимально возможная сумма, если среди первых $i$ элементов выбрать $j$ с суммой индексов не больше $p$. В целях оптимизации использования памяти будем хранить каждый раз только два верхних уровня динамики.↵
↵
Итоговая сложность решения: $O(n^4)$ по времени и $O(n^3)$ по памяти.↵
↵
Примеры решений: [submission:13845513] и [submission:13845571].↵
↵
Div. 1E (День рождения)↵
------------------↵
Автор идеи: [user:_meshanya_,2015-10-25], разработчик: [user:romanandreev,2015-10-25].↵
↵
Задача естественно разбивается на две подзадачи: быстрое построение графа вложенности и нахождение максимального независимого множества в этом графе. Заметим сразу, что если строка $s_2$ является подстрокой строки $s_1$, а строка $s_3$ является подстрокой строки $s_2$, то $s_3$ очевидно является подстрокой строки $s_1$. Таким образом, граф вложений зададаёт частично упорядоченное множество.↵
↵
Для быстрого построения графа воспользуемся алгоритмом [Ахо-Корасик](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA). С помощью данной структуры мы построим все существенные рёбра графа, то есть такие рёбра $uv \in E$, что не найдётся $w$, такого что $uw \in E$ и $wv \in E$. Одним из возможных способов является:↵
<ul>↵
<li> Построить структуру Ахо-Корасик; </li>↵
<li> Для каждой вершины найти и запомнить ближайшую терминальную в суффиксном пути; </li>↵
<li> Ещё раз скормить каждую строку автомату Ахо-Корасик, при этом каждый раз после добавления очередного символа требуется проводить ребро в ближайшую терминальную вершину в суффиксном пути; </li>↵
<li> Кроме существенных рёбер, данный алгоритм возможно добавит ещё какие-то корректные рёбра, но это никак не влияет на результат работы следующего шага; </li>↵
<li> Транзитивно замкнуть построенный граф. </li>↵
</ul>↵
↵
Для решение второй части данной задачи требует применить [теорему Дилворта](https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%94%D0%B8%D0%BB%D1%83%D0%BE%D1%80%D1%81%D0%B0). Восстановление ответа следует из конструктивного доказательства теоремы. ↵
↵
Получаем $O(L + n^3)$ на построение графа + $O(n^3)$ на нахождение максимальной антицепи, итоговая сложность решения: $O(L + n^3)$, где $L$ — суммарная длина всех строк.↵
↵
Поздравляем [user:ikatanic,2015-10-26] — единственного человека сдавшего эту задачу во время тура. Для дальнейшего уточнения решения предлагается посмотреть [submission:13851141].↵
↵
Упражнение: научитесь решать задачу с сохранением асимптотики, при условии что требуется найти множество строк максимальное не по размеру, а по суммарной длине.
