Я честно старался не пройти: долго писал 1-ю задачу, забыл поменять ограничения к large-тесту 2-й задачи, не заметил четвертую вершину у треугольника в графе 3-й задачи и забил на hard 4-й, но не получилось – занял 77 место, и, как следствие, попадаю в полуфинал. К сожалению, в деле «непопадания» в полуфинал преуспели остальные казахстанские участники, так что я, похоже, поеду один :(

Далее – немного о задачах (полные условия лежат здесь).

Задача A. How Big Are the Pockets?

В задаче требуется посчитать суммарную площадь «карманов» простого невыпуклого прямоугольного многоугольника. Точка считается лежащей в кармане, если она не лежит в многоугольнике и выше и ниже (или левее и правее) нее есть точки границы многоугольника. Гарантируется, что никакая координата никакой точки многоугольника не превышает по абсолютному значению 3000.

Решение

Для каждой целочисленной абсциссы x найдем y1 = min(y: (x,y) принадлежит многоугольнику) и y2 = min(y: (x,y) принадлежит многоугольнику). Аналогичное действие проделаем для ординат. Теперь посчитаем площадь Sa исходного многоугольника и Sb – площадь расширенного многоугольника. Расширенным будем считать исходный многоугольник с карманами. Sa считается методом трапеций, а Sb – перебором всех клеток 1×1 принадлежащих расширенному многоугольнику. Ответом к задаче будет Sb – Sa.

Задача B. Portal

Задача на лабиринт с портальной пушкой из Portal. Ходом считается только перемещение. Создание портала ходом не считается.

Решение

В качестве состояния будем использовать координаты 3-х клеток: наше местоположение, положение первого портала и положение второго портала (если подумать, то достаточно хранить всего лишь один портал, но с заданными ограничениями все работает и так). Если построить граф между этими состояниями, то можно заметить, что в нем будут только ребра весами 1 и 0. На таком графе задачу нахождения кратчайшего пути можно решить за линейное время обходом в ширину, используя следующий трюк: если производится переход по ребру весом 0 то вершину нужно добавлять не в конец очереди, а в начало. Самое простая реализация использует list или deque из STL.

Задача C. No Cheating

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

Решение

Построим граф, используя направления списывания в качестве ребер. Задача сводится к нахождению наибольшего независимого множества вершин в этом графе. В общем виде задача NP-полная, однако если присмотреться, то можно заметить, что построенный граф двудольный. А для двудольного графа количество вершин в наибольшем независимом множестве равно N – K, где N – количество вершин в графе, а K – количество ребер в наибольшем паросочетании.

Задача D. Endless Knight

Нужно посчитать, сколькими способами можно добраться ходом коня из (1, 1) в (W, H), если ходить можно только так, что обе координаты увеличиваются, и есть запрещенные клетки.

Решение

Для маленьких ограничений задача решается обычной динамикой. Для больших, возможно, нужно использовать малые ограничения на количество запрещенных клеток и считать количества путей до каждой из них и между ними. UPD: Как отметил u1ik в своем комментарии: «Да, в четвертой задаче брутфорсная формула вкл./искл. Только надо еще научиться быстро считать С(n, m) для больших чисел по модулю.»