532A - Шахтёры Берляндии

Доступна только английская версия разбора в английской версии поста.

532B - Рабочая группа

Эту задачу можно решить с помощью динамического программирования по поддеревьям иерархии сотрудников. Обозначим за D[v][e] максимальную эффективность, которую можно получить, взяв некоторое количество сотрудников из поддерева человека v, таким образом, чтобы их количество имело чётность e, и условие задачи выполнялось для всех взятых людей. Тогда нетрудно пересчитать D[v][e] через детей вершины v с помощью подсчёта промежуточной величины T[i][e] — максимальной эффективности, которой можно достичь, пройдя первые i поддеревьев вершины v, если чётность количества взятых людей — e.

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

532C - Игра на доске

Рассмотрим три случая.

1) x_p  +  y_p ≤  max(x_v,  y_v). В этом случае Поликарп может оказаться в (0,  0) через x_p  +  y_p ходов и Василий всегда будет "позади". Для Поликарпа достаточно делать любой возможный ход, и это приведёт его к победе. Нетрудно это объяснить тем, что условие x_p  +  y_p ≤  max(x_v,  y_v) будет выполнено и после любых возможных ходов Поликарпа и Василия. Иными словами, Василий просто не может победить.

2) x_p ≤ x_v, $y_p \leq y_v$. В этом случае Поликарп должен некоторым образом блокировать Василия. Он должен совершать такой ход, чтобы после любого возможного хода Василия неравенство было снова выполнено.

• Если x_p  =  x_v  >  0, нужно пойти в (xp  -  1,  yp).
• Если yp  =  yv  >  0, нужно пойти в (xp,  yp  -  1).
• В противном случае можно совершить любой допустимый ход.

Действуя по такой стратегии, мы снова не даём Василию возможности выиграть.

3) В противном случае рассмотрим любой кратчайший путь для Василия до точки (0,  0). Любая клетка этого пути ближе к Василию, чем к Поликарпу, поэтому Поликарп никак не может помешать Василию на этом пути. А значит, Василий дойдёт до финиша первым. Альтернативное объяснение заключается в том, что Василий всегда может сходить таким образом, чтобы ни одно из условий 1) и 2) не оказалось выполненным.

532D - Колонны

Первое наблюдение: колонна рушится только если расстояние между её соседями больше, чем 2d_i, поэтому для неё не имеет значения, где именно она находится на отрезке между своими соседками. Важно только расстояние между ними.

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

Медленный подход: для каждой предыдущей колонны проверим, может ли она быть соседом C. Ближайшая колонна, которая может, является будет тем самым левым соседом C.

Более быстрый подход: давайте обозначим за far[i] наибольшую возможную координату, где может находиться правый сосед колонны i. В нашей динамике заведём стек с возможными кандидатами на то, чтобы быть левым соседом каждой колонны. В этом стеке колонны будем поддерживать в порядке возрастания индекса (а, значит, и координаты) и одновременно в порядке убывания far[i] (действительно, нам незачем хранить в стеке колонну, если её мажорирует и по координате, и по far[i] какая-то другая колонна).

Теперь для каждой новой колонн мы должны удалить с вершины стека некоторое количество колонн со слишком малым значением far[i]. Последняя оставшаяся колонна на стеке будет той самой, через которую мы пересчитаем значение нашей динамики. Эта часть занимает O(n) времени.

Если существует колонна с far[i] не меньше координаты правой несущей колонны, то ответ--- 0, так как конструкция исходно устойчива.

Теперь посчитаем ту же самую величину справа налево. Теперь некоторые колонны связаны с левой несущей, некоторые — с правой. Мы хотим поставить новую так, чтобы попасть в пределы far[i] как для левой колонны, так и для правой. Это можно сделать, используя технику двух указателей по двум образованным стекам.

Описанное решение работает за O(n) времени и памяти.

532E - Исправление ошибок

Предположим для определённости, что S получается из W удалением более раннего символа, чем T. Тогда W  =  A  +  x  +  B  +  y  +  C, S  =  A  +  x  +  B  +  C, T  =  A  +  B  +  y  +  C, где x и y — удаляемые символы, а A, B и C — какие-то (возможно, пустые) строки.

Определим A как наибольший общий префикс S и T, а C — как наибольший общий суффикс. Удалим их из обоих строк. Теперь мы знаем буквы x и y — это соответственно первая буква строки S и последняя буква строки T. Удалим и их тоже. Остаётся лишь проверить, равны ли оставшиеся части строк.

Проделаем так для S и T, а также для T и S.

532F - Кодирование

У этой задачи возможно два направления решения.

Зафиксируем пару букв x и y. Заменим в строке S все буквы x на единицы, а все остальные буквы на нули. В строке T заменим все буквы y на единицы, а все остальные буквы на нули. С помощью алгоритма КМП или Z-функции определим все позиции, в которых строку T можно приложить к строке S так, что они совпадут. Если такое условие выполнено как для пары букв (x, y), так и для пары букв (y, x), то это значит, что в данной позиции можно приложить T к S с заменой x <-> y и возможно ещё какими-то заменами.

Теперь для каждой позиции надо проверить, разбиваются ли буквы на пары в соответствии с известной нам информацией. Это можно сделать за O(sigma), где sigma  =  26 — размер алфавита. Таким образом, решение работает за O(n  *  sigma2  +  n  *  sigma)  =  O(n  *  sigma2). Это решение при должной аккуратности реализации проходит по времени.

Другой способ — произвести замену, которая позволит нам сравнивать строки с точностью до переименовывания букв. Заменим каждую букву на расстояние до предыдущей такой же в обоих строках. Теперь для совпадения с точностью до переименования достаточно проверить, что строка T совпадает с подстрокой строки S во всех позициях кроме, возможно первых вхождений каждой буквы в T. Это можно сделать с помощью модифицированной префикс-функции или хеширования.

Пусть мы теперь знаем, что в некоторой позиции строка T совпадает со строкой S с точностью до переименовывания. Нетрудно определить, какая перестановка букв соответствует этому переименовыванию (достаточно посмотреть на первую букву каждого вида в T, чему она соответствует в S). Проверим, что эта перестановка — это набор транспозиций за O(sigma). Таким образом, получим решение за O(n  *  sigma).