Мне нравится идея Endagorion дополнять разбор задач небольшими упражнениями, связанными с подготовкой задачи, её обобщением или наличием более эффективного решения. Попробуем и мы предложить читателю подобные вопросы по некоторым задачам.

Div. 2A (Поединок волшебников)

Автор идеи: Роман Гусарев, разработка: timgaripov.

Найдем координату первого столкновения импульсов. Они сближаются со скоростью p + q, а значит первое столкновение произойдёт через секунд. Следовательно, координата первого столкновения может быть вычислена как .

Заметим теперь, что расстояние проходимое импульсами на обратном пути до волшебников равно расстоянию проходимому ими от волшебников до места первой встречи. Это значит, что импульсы вернутся к волшебникам одновременно, и ситуация станет идентична изначальной. Таким образом, вторая встреча (и все последующие) произойдёт в той же точке, что и первая.

Пример решения: 13836780.

Div. 2B (Ребрендинг)

Автор идеи: glebushka98, разработка: thefacetakt.

Тривиальное решение: будем эмулировать работу дизайнеров, а именно каждый раз ходить и честно перекрашвать все x_i в y_i и наоборот. Работает за , получает TL.

Попробуем улучшить этот результат.

Заметим, что одинаковые буквы переходят в одинаковые. Это означает, что позиция буквы никак не влияет на результат, и достаточно помнить для каждого возможного значения символа, во что он перейдёт. Пусть p(i, c) — символ, который будет стоять вместо всех вхождений c после обработки i дизайнеров. Тогда:

• p(0, c) = c
• Если p(i - 1, c) = x_i, то p(i, c) = y_i
• Аналогично, если p(i - 1, c) = y_i, то p(i, c) = x_i

Данное решение работает уже за O(|Σ|·m + n) и проходит все тесты.

Упражнение: доведите решение данной задачи до сложности O(Σ + n + m).

Примеры решения: 13837577 за O(|Σ|·m + n) и 13839154 за O(|Σ| + n + m).

Div. 2C\Div. 1A (Медианное сглаживание)

Автор идеи и разработчик: Sender.

Назовём статичными точками позиции, которые не могут измениться, сколько бы раз мы не применяли к последовательности алгоритм медианного сглаживания. Оба конца являются статичными точками по определению. Также, легко заметить, что если рядом стоят два одинаковых символа, то обе эти позиции так же являются статичными точками.

Исследуем влияние статичных точек на соседние элементы. Пусть a_i - 1 = a_i, то есть элемемнты i - 1 и i являются статичными точками. Пусть также a_i + 1 статичной точкой пока не является, следовательно a_i + 1 ≠ a_i и a_i + 1 ≠ 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).

Примеры решений: 13838940 и 13838480.

Div. 2D\Div. 1B (Чип и Дейл спешат на помощь)

Автор идеи и разработчик: StopKran.

Заметим, что если собственная скорость дирижабля задана вектором (a_x, a_y), а скорость ветра вектором (b_x, b_y), то реальный вектор движения дирижабля определяется как (a_x + b_x, a_y + b_y).

Одним из ключевых моментов в решении задачи является понимание монотонности функции ответа по времени. Если дирижабль может достичь цели за секунд, то он сможет достичь её и за секунд, для любого x ≥ 0. Это очевидно вытекает из условия, что максимально возможная собственная скорость дирижабля строго превосходит скорость ветра в любой момент времени.

Поскольку функция ответа монотонна, воспользуемся методом бинарного поиска по ответу, а именно, научимся проверять для фиксированного параметра , возможно ли добраться от точки (x₁, y₁) до точки (x₂, y₂) за время . Будем учитывать перемещение под действием ветра и собственное перемещение отдельно. Найдём сперва смещение дирижабля вызванное ветром:

• (x_n, y_n) = , если ;
• (x_n, y_n) = , если .

Остаётся только проверить, что используя только лишь собственную скорость можно добраться за время из точки (x_n, y_n) в точку (x₂, y₂).

Итоговая сложность: , где C — максимальная координата, а ε — требуемая точность.

Упражнение 1: подумайте как решить задачу, в случае когда не гарантируется, что дирижабль всегда быстрее ветра.

Упражнение 2: можете ли вы решить задачу за время O(1)?

Примеры решений: 13838659 и 13842505.

Div. 2E\Div. 1C (Три государства)

Автор идеи и разработчик: haku.

Утверждение. Пусть в неориентированном невзвешенном связном графе выделенны три различные вершины u, v, w. Одна из минимальных сетей, связывающих выделенные вершины, выглядит как некоторая вершина графа c, возможно совпадающая с одной из выделенных, из которой исходят кратчайшие пути к каждой из выделенных вершин, причём эти пути являются вершинно-непересекающимися.

Доказательство. Одним из оптимальных связывающих подграфов обязательно является дерево. Действительно, в противном случае на любом цикле найдётся ребро, которое можно выкинуть, и это не ухудшит ответ, поскольку он не зависит от количества используемых рёбер. Листьями дерева могу являться только вершины u, v и w, иначе ответ можно было бы улучшить, просто выкинув такой листь. Дерево, у которого не более чем три листа, имеет не более одной вершины степени больше двух, которая и будет вершиной c из утверждения выше. Разумеется, любой путь от c до листа имеет смысл заменить на кратчайший. Отдельно возможен вырожденный случай, что дерево ответа — это бамбук, но в таком случае вершиной c является одна из трёх выделенных вершин (не лист).

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

Для сведения исходной задачи к задаче поиска минимальной связывающей сети, можно представить карту в виде графа, где вершинам соответствуют клетки, принадлежащие государствам или допускающие постройку дороги, а ребро между двумя вершинами ставится, если они являются соседними в таблице. Все вершины, соответствующие одному государству, необходимо сжать в одну. Несложно заметить, что исходная задача таким образом свелась к вышеописанной.

Примеры решений: 13843265 — описанное решение реализовано через бфс на 0-1 графе, 13840329 — здесь логика решения несколько иная, разбираются два принципиально разных случая.

Div. 1D (Сверхсекретное задание)

Автор идеи и разработчик: glebushka98.

Если , то ответом является сумма k минимальных элементов.

Пусть i₁ < i₂ <  ...  < i_k — индексы элементов, которые войдут в итоге в ответ. Заметим, что относительный порядок выбранных элементов менять не имеет смысла, а значит, мы можем однозначно сказать, какой из выбранных элементов займёт какую позицию в ответе. T — минимальное количество операций, за которое их можно поставить на k первых мест. — .

T ≤ S  ≤  . .

Посчитаем динамику d[i][j][p] — минимально возможная сумма, если среди первых i элементов выбрать j с суммой индексов не больше p. В целях оптимизации использования памяти будем хранить каждый раз только два верхних уровня динамики.

Итоговая сложность решения: O(n⁴) по времени и O(n³) по памяти.

Примеры решений: 13845513 и 13845571.

Div. 1E (День рождения)

Автор идеи: meshanya, разработчик: romanandreev.

Задача естественно разбивается на две подзадачи: быстрое построение графа вложенности и нахождение максимального независимого множества в этом графе. Заметим сразу, что если строка s₂ является подстрокой строки s₁, а строка s₃ является подстрокой строки s₂, то s₃ очевидно является подстрокой строки s₁. Таким образом, граф вложений зададаёт частично упорядоченное множество.

Для быстрого построения графа воспользуемся алгоритмом Ахо-Корасик. С помощью данной структуры мы построим все существенные рёбра графа, то есть такие рёбра , что не найдётся w, такого что и . Одним из возможных способов является:

• Построить структуру Ахо-Корасик;
• Для каждой вершины найти и запомнить ближайшую терминальную в суффиксном пути;
• Ещё раз скормить каждую строку автомату Ахо-Корасик, при этом каждый раз после добавления очередного символа требуется проводить ребро в ближайшую терминальную вершину в суффиксном пути;
• Кроме существенных рёбер, данный алгоритм возможно добавит ещё какие-то корректные рёбра, но это никак не влияет на результат работы следующего шага;
• Транзитивно замкнуть построенный граф.

Для решение второй части данной задачи требует применить теорему Дилворта. Восстановление ответа следует из конструктивного доказательства теоремы.

Получаем O(L + n³) на построение графа + O(n³) на нахождение максимальной антицепи, итоговая сложность решения: O(L + n³), где L — суммарная длина всех строк.

Поздравляем ikatanic — единственного человека сдавшего эту задачу во время тура. Для дальнейшего уточнения решения предлагается посмотреть 13851141.

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