Задача А. Игра.

Идея: Андрей Комаров.
Реализация: Малова Анна.
Разбор: Малова Анна.

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

Решением задачи является проверка всех клеток игрового поля и пар соседних клеток игрового поля, удолетворяют ли они указанным выше условиям. Итоговая сложность: O(n²).

Задача B. Таймер.

Идея: Виталик Аксёнов.
Реализация: Артем Васильев.
Разбор: Артем Васильев.

В задаче нужно найти максимальное возможное число, которое может получиться на таймере после t секунд, если разрешено не более k раз заменить число на таймере на наименьшее число, не меньшее x и делящееся на y.

В заданных ограничениях всегда возможно получить число, которое делится на y. Рассмотрим первый момент, когда такое число появилось на таймере. Можно показать, что это число будет наименьшим среди чисел, не меньших x и делящихся на y. Обозначим его за z.

Существует не более двух различных оптимальных способов получить z на таймере. Первый из способов это использовать уязвимость до первого тика таймера. В таком случае мы тратим одно использование уязвимости и ноль секунд. Второй способ — не тратить использование уязвимости и подождать необходимое количество секунд. Этот способ возможен только тогда, когда z-x ≤ t и затрачивает z-x секунд и ноль использований уязвимости. Обозначим время после получения z за t_o, а оставшееся количество использований за k_o.

После того, как на таймере появилось z, действия Пети становятся однозначными. Нам выгодно использовать как можно больше уязвимостей, потому что они прибавляют дополнительно y-1 секунд. Отсюда ответ равен z + min(t_o, k_o) · (y-1) + t_o.

Осталось проверить оба способа получить число z, вычислить ответ для получившихся t_o и k_o и выбрать максимальный из них. Время работы решения — O(1) на один тестовый пример.

Задача C. Обратная задача о наибольшей возрастающей подпоследовательности.

Идея: Андрей Станкевич, Николай Ведерников.
Реализация: Николай Ведерников.
Разбор: Николай Ведерников.

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

Данную задачу можно решить конструктивно. Например так d[i] = a[i] · n — i + 1, где n — длина последовательности. Докажем, что это последовательность подходит.

∀ i < j для которых d[i] < d[j] будет выполнено: (d[j] — d[i]) · n ≥ n, а (j — i) < n ⇒ a[i] < a[j]. Аналогично в другую сторону.

∀ i < j для которых d[i] = d[j] будет выполнено: a[i] > a[j].

Кроме того, существует решение, использующее алгоритм топологической сортировки.

Задача D. Трехцветные шахматы.

Идея: Виталий Демьянюк.
Реализация: Виталий Демьянюк.
Разбор: Виталий Демьянюк.

В задаче требовалось подсчитать количество способов покрасить каждую не покрашеную клетку доски n × m в три цвета так, чтобы никакие две соседние клетки не были покрашены в одинаковый цвет.

Данная задача является задачей динамического программирования по изломанному профилю.

Занумеруем все цвета. Каждому состоянию соответствует четверка чисел (x, y, c, mask), где (x,y) – координаты клетки в которой начинается излом профиля. Рассмотрим все клетки профиля в порядке обхода сверху вниз. Тогда c – цвет первой клетки профиля. Рассмотрим i-тую клетку профиля и множество цветов в которые она не покрашена. Это множество состоит из двух цветов. Тогда i-тый бит mask равен 0, если цвет i+1 клетки профиля равен минимуму этого множества, 1 – если максимуму.

В каждом состоянии будем хранить количество способов покрасить соответствующую часть доски. Пересчет значений такой же как и в любой другой задаче динамического программирования по изломанному профилю. Для получения ответа переберем все c и mask и просуммируем значение в состояниях (n, m, c, mask).

Время работы — O(nm2ⁿ).

Задача Е. Как проложить сеть.

Идея: Борис Минаев.
Реализация: Борис Минаев.
Разбор: Борис Минаев.

В задаче требовалось подсоединить все компьютеры к коммутаторам, которые расположены по кругу, затратив при этом наименьшее количество кабеля. Эту задачу можно решать с помощью алгоритма поиска максимального потока минимальной стоимости. Однако мы опишем решение, которое использует метод динамического программирования, а также имеет лучшее время работы.

Для начала рассмотрим более легкую задачу. Пусть компьютеры и коммутаторы расположены на прямой. Назовем балансом разность между количеством компьютеров, которые мы рассмотрели, и количеством подсоединений к коммутаторам, которые использовали. Для каждого баланса от -n до n будем хранить наименьшую стоимость его достижения. Стоимость достижения баланса нужно определить таким образом, чтобы при балансе 0 его стоимость совпадала со стоимостью прокладки всей сети. Например, это можно сделать следующим образом: eсли после добавления очередного устройства модуль баланса увеличился, то из его стоимости вычитается расстояния до устройства, иначе добавляется. Теперь воспользуемся методом динамического программирования. Будем рассматривать устройства слева направо. Если текущее устройство — компьютер, то баланс нужно обязательно увеличить на один и соответствующим образом изменить его стоимость. Если же мы рассмотриваем коммутатор, то необходимо перебрать, сколько компьютеров будет к нему подключено, и аккуратно пересчитать стоимость баланса (возможно, первые несколько подключений будут его увеличивать, а следующие — уменьшать). Такое решение работает за O(n²·(n+m)).

Рассмотрим способ, который позволяет уменьшить время работы алгоритма до O(n·(n+m)). Самое долгоработающее место алгоритма — обновление значений динамического программирования при обработке коммутатора. Будем находить стоимость получения балансов от меньших к большим. При этом будем поддержить очередь, в которой хранятся стоимости получения нужного баланса из различных предыдущих состояний балансов. При переходе к новому значению баланса нужно, возможно, удалить из очереди первый элемент (если к текущемему коммутатору нельзя поключить нужное количество компьютеров), добавить возможность получить текущий баланс не использовав коммутатор совсем, а также изменить все текущие стоимости, которые есть в очереди — для этого нужно прибавить (или отнять) расстояние до коммутатора. В очереди всегда должна хранится возрастающая последовательность стоимостей. Тогда ответ для текущего баланса всегда будет находится на первом месте очереди.

Теперь вернемся к задаче на круге. Разрежем круг и зафиксируем количество проводов, которые проходят через разрез. Можно легко показать, что если существует оптимальный ответ, в котором ровно столько проводов проходят через разрез, то существует оптимальный ответ, в котором эти провода подключены к первым устройствам соответствующего типа. Таким образом мы получили решение на круге за O(n²·(n+m)).