Battle of the Brains. Отчет с финала ACM ICPC 2009

21 апреля 2009 года три сотни лучших молодых математиков и программистов собрались в Стокгольме для участия в финале Чемпионата мира по спортивному программированию ACM ICPC, главным спонсором которого выступает IBM. По приглашению этой замечательной компании я и отправился в Швецию, чтобы своими глазами увидеть битву лучших молодых умов планеты.

«Для решения серьезных проблем нужны величайшие, уверенные в своих способностях умы, способные предложить нестандартные решения, — считает доктор Билл Паучер (Bill Poucher), профессор Университета Бэйлор (Baylor University) и исполнительный директор чемпионата ICPC. — Их можно назвать атлетами инноваций. Они выходят за рамки ограничений и получают удовольствие, делая эту работу».

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

Любая проблема здесь, как бы она ни была подана, всегда упирается в составление математических моделей и решение математических задач. Решений «на пальцах» не бывает: даже если задачку и можно решить тупым перебором, такое решение не пройдет по ограничениям на ресурсы — для каждого задания существуют пороговые значения по используемой памяти и времени выполнения.

Участники

В этом году представлять Россию поехали 8 команд: ИТМО (чемпионы прошлого года), Саратовский ГУ (чемпионы России этого года), МГУ, Алтайский ГУ, Новосибирский ГУ, СПБ ГУ, Уральский и Южно-Уральский ГУ. Также среди участников были такие известные вузы как MIT, Стэнфорд, Оксфорд, Варшавский Университет, Университет Карнеги-Меллона и Циньхуа. Предматчевые расклады были простые: команда ИТМО приехала отстаивать статус Чемпионов мира, а все остальные приехали мешать это им сделать :). Так же намечалось интересное российско-китайское противостояние: от Китая традиционно приехало немало сильных команд, готовых бороться за самые высокие места.

Соревнования и итоги

Непосредственно финальные соревнования проходили в KTH – Королевском технологическом университете Стокгольма и ровно в 9 утра 21 апреля был дан старт соревнованиям.

В этом году участникам было предложено 11 задач, наиболее простой из которых оказалась задачка с индексом «А»: ее решили очень быстро и для большинства команд именно она была первой решенной задачей.

За 5 часов соревнований было решено 9 из 11 задач: это смогли сделат две команды – ИТМО и Университет Цинхуа. Победителя определили по затраченному времени: показав результат в 1381 минут второй раз подряд Чемпионами мира стали ребята из ИТМО!

Финальные результаты

Место/ Название ВУЗа/ Решено/ Время

1 / St. Petersburg State University of IT, Mechanics and Optics / 9/ 1381

2 / Tsinghua University / 9 / 1800

3 / St. Petersburg State University / 8 / 1176

4 / Saratov State University / 8 / 1305

5 / University of Oxford / 7 / 998

6 / Zhejiang University / 7 / 1117

7 / Massachusetts Institute of Technology/ 7 / 1143

8 / Altai State Technical University / 7 / 1254

9 / University of Warsaw / 7/ 1413

10/ University of Waterloo / 6 / 787

11 / I. Javakhishvili Tbilisi State University / 6 / 933

12 / Carnegie Mellon University / 6 / 1045

Задача «А»: Осторожный подход

Представь себя авиадиспетчером и что тебе надо составлят максимально безопасное расписание посадок самолетов в аэропорту. Права на ошибку нет: на кону жизни людей.

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

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

К примеру, если есть три самолета с посадками 10:00am, 10:05am и 10:15am, то минимальный промежуток между посадками составляет 5 минут: между первыми двумя. Промежутки в расписании посадок не должны быт одинаковыми – но самый маленький из них должен быть как можно больше.

Входные параметры:

Input-файл состоит из нескольких тестовых случаев, описывающих разные исходные сценарии посадок. Каждый тестовый случай начинается с цифры n (2<=n<=8), обозначающей количество самолетов в сценарии. Далее следует n линий, каждая из которых содержит два числа [ai, bi], временной диапазон, в течение которого i-й самолет может приземлиться. Числа ai, bi указываются в минутах и находятся в таком диапазоне: 0 ? ai ? bi ? 1440.

Заканчивается входной файл строкой с 0.

Выходные параметры:

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

dvd

На нашем диске ты найдешь задачи этого года, а так же подборку фотографий с финала ACM ICPC 2009 в Стокгольме.

Battle of the Brains. Отчет с финала ACM ICPC 2009

Участники

Соревнования и итоги

Финальные результаты

Задача «А»: Осторожный подход

dvd

links