Отчёт о прохождении первого раунда Russian Code Cup
В субботу 19 апреля прошёл первый отборочный раунд чемпионата Russian Code Cup. Предлагаем вашему вниманию отчёт о том, как проходил раунд, с какими сложностями мы столкнулись, о задачах раунда и его результатах.
Начало чемпионата удивило всех неожиданно высокими показателями: на момент старта 1 раунда для участия в чемпионате зарегистрировалось уже более 5000 участников. Для сравнения, в 2013 году всего в чемпионате участвовало более 3500 программистов. И количество заявок постоянно растет, ведь регистрироваться можно вплоть до начала последнего квалификационного раунда.
В самом раунде приняло участие рекордное за все годы количество участников — 1255! Такого еще не было! В прошлом году в первом раунде было 754 участника. Обратной стороной такой популярности и возросшей нагрузки стали технические проблемы с сервером, наблюдающиеся на протяжении всего раунда. Страницы с задачами и результатами были недоступны или доступны с большой задержкой. И если бы сервер не упал, то в первом раунде приняли бы как минимум 3000 участников, судя по данным логов о количестве запросов.
Но раунд все же прошел до конца. Из-за технических проблем результаты раунда не являются полностью достоверными. Было бы логично сделать его «нерейтинговым» и провести вместо него новый квалификационный раунд. С другой стороны, многие участники потратили время и силы на то, чтобы все же попытаться принять участие в раунде и решить задачи, и нам хотелось бы их поощрить их усилия и настойчивость. Поэтому мы приняли следующее решение:
1) 200 лучших участников, которые всё же приняли участие в раунде несмотря на трудности, проходят в отборочный раунд.
2) В воскресенье, 1 июня 2014 года в 13–00 будет проведен еще один, четвертый квалификационный раунд. По его результатам ещё 200 лучших участников также выйдут в отборочный раунд. Таким образом, в нём примут участие 800 программистов, а не 600. Всем прошедшим в отборочный раунд будут разосланы футболки RCC 2014.
Мы понимаем, что это довольно спорное решение и в нем есть свои минусы, но надеемся на понимание сообщества. Со своей стороны мы предпримем все возможные усилия, чтобы остальные раунды прошли без накладок и 50 сильнейших программистов вышли в финал и сразились за звание чемпиона Russian Code Cup 2014.
Участниками было прислано 5945 решений, из которых 1982 были приняты системой как верные. Использованные языки программирования распределились следующим образом: Решений на GNU C++: 2369 Решений на Visual C++: 1707 Решений на Java: 927 Решений на C#: 461 Решений на Python: 309 Все пять задач решили только три человека (для выхода в отборочный раунд необходимо было решить три задачи со штрафом не более 233 минут).
Задача А. Игра.Идея: Андрей Комаров.Реализация: Малова Анна.Разбор: Малова Анна.В данной задаче требовалось проверить, является ли игровое поле хорошим. Хорошим полем называлось поле, содержащее свободную клетку или две соседние клетки, в которых стоят одинаковые числа.Решением задачи является проверка всех клеток игрового поля и пар соседних клеток, удовлетворяют ли они указанным выше условиям. Итоговая сложность: O (n2).Задача B. Таймер.Идея: Виталик Аксёнов.Реализация: Артем Васильев.Разбор: Артем Васильев.В задаче нужно найти максимальное возможное число, которое может получиться на таймере после t секунд, если разрешено не более k раз заменить число на таймере на наименьшее число, не меньшее x и делящееся на y.В заданных ограничениях всегда возможно получить число, которое делится на y. Рассмотрим первый момент, когда такое число появилось на таймере. Можно показать, что это число будет наименьшим среди чисел, не меньших x и делящихся на y. Обозначим его как z.Существует не более двух различных оптимальных способов получить z на таймере. Первый из способов это использовать уязвимость до первого тика таймера. В таком случае мы тратим одно использование уязвимости и ноль секунд. Второй способ — не тратить использование уязвимости и подождать необходимое количество секунд. Этот способ возможен только тогда, когда z — x ≤ t и затрачивает z — x секунд и ноль использований уязвимости.Обозначим время после получения z как to, а оставшееся количество использований как ko.После того, как на таймере появилось z, действия Пети становятся однозначными. Нам выгодно использовать как можно больше уязвимостей, потому что они прибавляют дополнительно y -1 секунд.Отсюда ответ равен z + min (to, ko) • (y -1) + to.Осталось проверить оба способа получить число z, вычислить ответ для получившихся to и ko и выбрать максимальный из них. Время работы решения — 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 (nm 2 n).
Задача Е. Как проложить сеть.Идея: Борис Минаев.Реализация: Борис Минаев.Разбор: Борис Минаев.В задаче требовалось подсоединить все компьютеры к коммутаторам, которые расположены по кругу, затратив при этом наименьшее количество кабеля. Эту задачу можно решать с помощью алгоритма поиска максимального потока минимальной стоимости. Однако мы опишем решение, которое использует метод динамического программирования, а также имеет лучшее время работы.Для начала рассмотрим более легкую задачу. Пусть компьютеры и коммутаторы расположены на прямой. Назовем балансом разность между количеством компьютеров, которые мы рассмотрели, и количеством подсоединений к коммутаторам, которые использовали. Для каждого баланса от -n до n будем хранить наименьшую стоимость его достижения. Стоимость достижения баланса нужно определить таким образом, чтобы при балансе 0 его стоимость совпадала со стоимостью прокладки всей сети. Например, это можно сделать следующим образом: если после добавления очередного устройства модуль баланса увеличился, то из его стоимости вычитается расстояния до устройства, иначе добавляется. Теперь воспользуемся методом динамического программирования.Будем рассматривать устройства слева направо. Если текущее устройство — компьютер, то баланс нужно обязательно увеличить на 1 и соответствующим образом изменить его стоимость. Если же мы рассматриваем коммутатор, то необходимо перебрать, сколько компьютеров будет к нему подключено, и аккуратно пересчитать стоимость баланса (возможно, первые несколько подключений будут его увеличивать, а следующие — уменьшать). Такое решение работает за O (n 2 •(n + m)).Рассмотрим способ, который позволяет уменьшить время работы алгоритма до O (n •(n + m)). Самое долгоработающее место алгоритма — обновление значений динамического программирования при обработке коммутатора. Будем находить стоимость получения балансов от меньших к большим. При этом будем поддерживать очередь, в которой хранятся стоимости получения нужного баланса из различных предыдущих состояний балансов. При переходе к новому значению баланса нужно, возможно, удалить из очереди первый элемент (если к текущему коммутатору нельзя подключить нужное количество компьютеров), добавить возможность получить текущий баланс не использовав коммутатор совсем, а также изменить все текущие стоимости, которые есть в очереди — для этого нужно прибавить (или отнять) расстояние до коммутатора. В очереди всегда должна храниться возрастающая последовательность стоимостей. Тогда ответ для текущего баланса всегда будет находиться на первом месте очереди.Теперь рассмотрим вариант сети в виде круга. Разрежем круг и зафиксируем количество проводов, которые проходят через разрез. Можно легко показать, что если существует оптимальный ответ, в котором ровно столько проводов проходят через разрез, то существует оптимальный ответ, в котором эти провода подключены к первым устройствам соответствующего типа. Таким образом мы получили решение на круге за O (n 2 •(n + m)).
Скачать и ознакомиться с результатами тестов можно на странице результатов раунда.
