200A — Кино

В этой задаче было дано поле размером n × m и k запросов. Каждый запрос –-- это клетка поля. Нужно было для каждого запроса находить ближайшую к заданной не занятую клетку (при этом ближайшая клетка находится по манхэттенской метрике). После этого найденная клетка помечалась как занятая. В задаче предполагалось решение за время . Сначала поясним идею решения, затем покажем, как достигается такая временная оценка. Идея решения состоит в следующем. Прежде всего, если n > m, то повернем матрицу на 90 градусов (далее будет пояснено зачем). Будем хранить две матрицы n × m, в которых для каждой клетки будем хранить ближайшую свободную клетку слева и справа. Пусть теперь приходит запрос клетка (x, y). Будем перебирать величину d на сколько строчек мы отступим вниз и вверх. Когда мы зафиксировали d, то рассмотрим строку, например, x–d (аналогичные действия нужно будет проделать для строки x + d). В данной строке найдем при помощи наших матриц ближайшие свободные клетки слева и справа от клетки (x–d, y) и попробуем улучшить ответ. В тот момент, когда величина d станет больше, чем текущая найденная величина ответа, остановимся, т.к. в этом случае ответ уже не улучшится. После того, как мы найдем ответ на запрос – ближайшую клетку, нужно пересчитать значения в массивах. Это можно делать, используя, например, для каждой строки структуру DSU.

Покажем теперь, почему данное решение работает за время . Предположим, у нас все запросы одинаковы, т.е. одна и та же точка (x, y). Тогда если поле достаточно большое, то все точки будут располагаться в виде квадрата, повернутого на 45 градусов, с центром в точке (x, y). При этом сторона квадрата будет иметь величину порядка . Тогда и диагональ, которую мы рассмотрим в результате решения, описанного выше, имеет величину порядка . Т.е. в каждом запросе мы рассматриваем строчек и в каждой строке мы совершаем O(1) действий. Если поле такое, что квадрат не помещается в него, т.е. слишком узкое либо по вертикали, либо по горизонтали, то получится нечто, похожее на прямоугольник, у которого одна из сторон будет меньше . Тогда повернем поле таким образом, чтобы меньшая сторона этого прямоугольника соответствовала строкам. В результате мы будем проходить при каждом запросе также не более строк и в каждой строке совершать не более O(1) действий. Данная задача предполагалась как самая сложная задача контеста.

200B — Напитки

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

200C — Чемпионат по футболу

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

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

200D — Язык программирования

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

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

200E — Тракторный институт

В данной задаче по сути было дано четыре числа c₃, c₄, c₅, s. Нужно было найти такие числа 0 ≤ k₃ ≤ k₄ ≤ k₅, что c₃·k₃ + c₄·k₄ + c₅·k₅ = s и при этом |c₃·k₃–c₄·k₄| + |c₄·k₄–c₅·k₅| минимально.

Для начала переберем k₄ так, чтобы s–c₄·k₄ ≥ 0. Затем рассмотрим 4 случая, в зависимости от того, каковы по знаку значения под модулями.

Рассмотрим случай c₃·k₃–c₄·k₄ ≥ 0 и c₄·k₄–c₅·k₅ ≥ 0. Тогда нужно минимизировать c₃·k₃–c₅·k₅. При этом 0 ≤ k₃ ≤ k₄ ≤ k₅ и c₃·k₃ + c₅·k₅ = s–c₄·k₄. Рассмотрим диофантово уравнение c₃·k₃ + c₅·k₅ = s–c₄·k₄. При этом оно может не иметь решений. Рассмотрим случай, когда решения есть. Поскольку c₃, c₅ ≥ 0, то для минимизации c₃·k₃–c₅·k₅ нужно минимизировать k₃ и максимизировать k₅. Все решения диофантового уравнения c₃·k₃ + c₅·k₅ = s–c₄·k₄ можно выразить через один параметр k. Тогда необходимо найти отрезок значений k, при которых k₃ будет подходящим, отрезок, при котором k₅ будет подходящим, пересечь данные отрезки и, если пересечение не пусто, выбрать то значение k, при котором k₅ максимально.

Аналогично рассуждая, нужно разобрать остальные 3 случая и выбрать оптимальные значения k₃ и k₅ для фиксированного k₄. Можно было также заметить, что в каждом из случаев искомая функция линейно зависит от аргумента, а, значит, она принимает минимальное значение на отрезке в одном из его концов. Поэтому можно не рассматривать случаи, а находить отрезки k, при которых k₃, k₅ принимают допустимые значения, и считать целевую функцию в концах этих отрезков. Если при этом для всех фиксированных k₄ не существует решений диофантовых уравнений, или пересечения выше указанных отрезков пустые, то ответ IMPOSSIBLE, иначе нужно выбрать лучшее. Таким образом решение получается за O(s·log(s)) --– перебор k₄, и решение диофантова уравнения при каждом k₄.