Олимпиады

Задачи KBTU Open 2008 (спасибо Герману Ильину за предоставление электронных вариантов условий).

Задача A. Computer Networks

Условие задачи сводится к нахождению минимального реберного разреза между любыми двумя вершинами в графе. Как известно величина реберного разреза между вершинами s и t численно равна величине максимального потока между этими же вершинами. Простой перебор всех пар вершин и нахождение между каждой парой вершин этого самого потока не уложится по времени. Для решения задачи достаточно заметить (доказать, интуитивно предположить ), что перебирать надо не все пары вершин, а только пары (1, i) (естественно, вместо вершины 1 можно взять любую другую).

Задача B. Contest

Динамика по двум параметрам. Пусть d[i, j] – количество различных «ranklist» для i участников распределенных по j местам (не забываем, что несколько участников могут занимать одно место). Тогда при j > i d[i, j] = 0, а в остальных случаях d[i, j] = (d[i - 1, j] + d[i - 1, j - 1]) * j.

Задача C. Counter Strike

Задача на «идею». Переберем все пары оружия и количество патронов, которые мы можем купить. Пусть a1, a2 – «damage» текущих видов оружия, а b1, b2 – соответствующие количества патронов. Надо сосчитать для всех возможных a1, a2, b1, b2, сколько максимум врагов мы сможем уложить. Теперь «идея» (одна из возможных): возьмем какое-то количество выстрелов одного оружия и найдем, сколько необходимо выстрелов другого оружия в дополнение к ним, чтобы уложить одного врага. Уложим таким образом столько врагов, сколько сможем. Для оставшегося количества патронов рекурсивно повторим процедуру. Вот и все (доказательства не спрашивать ).

Задача D. Fatboy

Задача сводилась к нахождению наибольшей общей подпоследовательности трех последовательностей так. Делается стандартной динамикой по трем параметрам: d[i, j, k] – длина наибольшей общей подпоследовательности префиксов строк длиной i, j, k.

Задача E. Super Heroes

В задаче надо было разделить данный граф на две доли так, чтобы в одной доле между каждой парой вершин было ребро (назовем эту долю A), а во второй – ребер не было вообще (B), или сказать, что такое разделение не возможно. Между вершинами из разных долей ребра могут быть. Ключевая идея – вершина с наибольшей степенью лежит в доле A. На основании ее получаем решение: взять вершину с наибольшей степенью, связанную ребрами со всеми вершинами находящимися в доле A, поместить ее в долю A, удалить ее из исходного графа и повторить операцию с оставшимися вершинами. Как только нельзя будет найти вершину, связанную со всеми из доли A, останавливаемся и проверям, есть ли ребра между оставшимися вершинами (которые относятся к доле B).

Задача G. Points

Известно, что удвоенная площадь треугольника, вершины которого имеют целочисленные координаты – целая. Таким образом надо посчитать, сколько получается треугольников с четной площадью. Если расписать площадь как векторное произведение двух векторов, то можно заметить, что ее четность зависит только от четности координат векторов, которые в свою очередь зависят только от четности координат вершин. Поэтому все вершины можно «сложить» в квадрат (0, 0) – (1, 0) – (1, 1) – (0, 1) (при этом несколько вершин могут «сложиться» в одну), а дальше – тривиальный перебор или формула.

Задача H. Sequence

Динамика по N. Пусть f[i, j] – количество хороших последовательностей длины i, оканчивающихся на j, где j – это 0 или 1. Тогда:
f[i, 0] = f[i - 1, 0] + f[i - 1, 1];
f[i, 1] = f[i - 1, 1] + f[i - 1, 0] – f[i - 2, 1] + f[i - 3, 1].
Опять же, здесь не надо хранить само количество, – достаточно его четности.