424A - Паша и приседания

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

424B - Город-миллионер

Можно отсортировать все города по возрастанию расстояния до города Томска. После чего требуется найти наименьший индекс t, для которого общее население p₀ + p₁ + ... + p_t >  = 10⁶. Для такого t значение d_t является ответом. Ограничения на N позволяют использовать сортировку с асимптотикой O(N²) или любое другое решение с такой асимптотикой.

424C - Волшебные формулы

Рассмотрим следующие формулы:

Пусть . Посчитаем значение этой функции для всех значений i (0 ≤ i ≤ n). Это можно сделать за O(n), используя соотношение .

Преобразуем c_i:

Также:

Таким образом:

Это означает, что если n / i нечетно, , иначе — . c_i может быть вычислено за O(1), благодаря чему итоговая асимптотика решения — O(n).

424D - Биатлонная трасса

Из-за лояльных ограничений по времени для Java, некоторые решения с асимптотикой O(N⁴) были зачтены. Авторское решение имеет сложность O(N³logN). Основная идея — зафиксировать верхнюю и нижнюю границы. Затем, используя какой-либо абстрактный тип данных, для каждой правой границы найти наиболее подходящую левую границу за время не хуже O(logN). Например, можно использовать контейнер set в языке программирования C++ и его метод lower_bound. Для лучшего понимания можно посмотреть на следующее изображение.

Для показанного прямоугольника мы зафиксировали верхнюю границу строкой номер 2, нижнюю — строкой номер 5. Так же мы зафиксировали правую границу столбцом номер 6. Теперь требуется найти наиболее подходящую левую границу. Для этого мы можем разделить значение времени для любого прямоугольника на слагаемое, которое зависит только от правой границы, и на слагаемое, которое зависит только от левой границы.

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

424E - Цветная Jenga

Классическая задача на динамическое программирование для нахождения математического ожидания.

Определим некоторую функцию F(S) для некоторого состояния S — математическое ожидание количества минут до конца игры, если мы находимся в этом состоянии. Для каждого цвета мы можем вычислить вероятность, с которой этот цвет выпадет при броске кубика по тривиальной формуле , где c — количество граней такого цвета на кубике. Теперь требуется найти вероятность того, что мы останемся в том же состоянии еще хотя бы на одну минуту. Это можно сделать сложив вероятность выпадения черной грани и вероятности выпадения цветов, блоки цвета которых нельзя достать из башни на данный момент. Теперь мы можем найти значение это функции используя формулу:

Далее требуется придумать как закодировать состояния. Для того, чтобы уменьшить количество различных состояний можно воспользоваться тем фактом, что имеется всего-лишь 18 различных уровней, а не 27 (некоторые комбинации являются отражением друг друга). Для лучшей производительности рекомендуется использовать хеширование. Решение данной задачи требует хорошего понимания динамического программирования и достаточно хороших реализаторских навыков.