Финал ACM ICPC: уехали золотом, но мы не первые

В этом году финал самого крупного турнира по программированию ACM-ICPC, спонсируемый компанией IBM, проходил в довольно экзотическом месте. Когда мне сказали, что это будет Китай, я был уверен - наверняка, Пекин или Шанхай. Но ребята из IBM меня озадачили: "Нет, Стёпа, ты едешь в Харбин". Харбин?!

Начиная когда-то как русская железнодорожная станция, город дорос до десяти миллионов населения и стал одним из крупнейших научных центров Китая. Именно сюда и собрались три сотни программистов со всего мира, чтобы принять участие в битве мозгов - люди не только чрезвычайно умные, но и смелые. В Харбине действительно очень холодно, стрелка термометра подчас опускается до минут 30 градусов. Обычно участникам финала ACM-ICPC выдают разноцветные майки с эмблемой турнира и названием университета. В Харбине этого было мало: спортсменов-программистов надо не просто одеть так, чтобы отличить от прочей публики, но и защитить от мороза. В итоге распознать участников и организаторов на улице (если, конечно, они рисковали выбраться из отеля или кампуса) было очень просто. Синяя куртка с капюшоном, теплые штаны и шапка-ушанка с символикой IBM - сразу видно, свой идет. Америнка-организатор шутит: «Да вам же не должно быть холодно». Как же, кажется, мозг уже замерз.

Всего в день соревнований участвовало 103 команды. Несмотря на победу в прошлом году (и позапрошлом, между прочим), фаворитами считались хозяева турнира - Китайцы, представленный 20 командами. Тут надо сказать, что команда СПбГУ ИТМО, которая выиграла ACM ICPC год назад в Стокгольме, в этот раз не выступала. Их обыграла на отборочной стадии другая команда того же ВУЗа, как говорят, слабее – но это спорт, а здесь есть место для удачи. Всего от России приняло участие 11 команд. Из США в свою очередь в финала пробились аж 18 университетов, при этом несмотря на громкие названия вузов, многие в результате оказались самыми аутсайдерами, красуясь на последних местах турнирной таблицы. Ни одной решенной задачи? А вы говорите: "Силиконовая долина". Ха!
Регламент соревнований не претерпел изменений. Все команды, состоящие из трех студентов, собираются в одном большом помещении, где им дается 5 часов, чтобы решить 11 задач разной степени сложности. Задачи отбираются в обстановке строгой секретности жюри, состоящим в основном из профессоров и преподавателей разных вузов - в общем, достать их заранее абсолютно нереально.

Все задачи четко алгоритмические, но при этом, как правило, смоделированы на основе реальных проблем, входящих в «сферу интересов» инициативы IBM Smarter Planet (Разумная планета) – таких, например, как создание электронного расписания аэропорта для безопасной посадки самолетов, которое бы учитывало изменение погодных условий и другие неожиданности, или оптимизация системы полива растений на сельско-хозяйственном предприятии, или оценка воздействия изменения климата на вымышленную географическую территорию. Разработать систему для считывания штрихкода, рассчитать минимальную численность армию для взятия виртуальных замков, вычислить длину кратчайшего пути для капитана спасательной лодки, регулярно инспектирующего группу туристических островов - все это пришлось решать участникам харбинского финала. Полные тексты заданий ты можешь найти на нашем диске. Стоит отметить, что все задания составлены на английском языке, поэтому единственной книгой, которую допускается использовать участникам, является словарь.

У каждой команды есть только один компьютер с установленными компиляторами C, C++ и Java – язык каждая команда могла выбирать по своему усмотрению. При этом задачи передаются на проверку полуавтоматической системе, которая сама компилирует предоставленный код и прогоняет на тестовых результатах, проверяя разные аспекты работы программы. На выходе результаты сверяются с эталонными, после чего обновленные данные по решенным задачам отображаются на общем табло и в онлайне. Помимо правильности результата проверяется, укладывается ли программа в лимиты по времени, поэтому решения "в лоб" с помощью тупого перебора, хотя это и редко возможно, сразу отметается. Хочешь попробовать? Ради бога, но от штрафного бала не уйдешь.

За 30 минут до окончания соревнования результаты на табло перестают отображаться, чтобы поддержать интригу. Пока на первом месте команда Шанхайского университета, но у нашего МГУ им. Ломоносова еще есть шансы. Мы смотрим на ребят, они что-то очень быстро делают: авось, еще получится? Будем первыми? Пошел обратный отсчет, сопровождаемый всеобщим ликованием "three", "two", "one" - время вышло. Увы, на объявлении результатов чуда не произошло. На первом месте оказались молодцы-китайцы из Шанхая, наши ребята из МГУ - на втором месте. Но это все равно золотая медаль: на ACM-ICPC вручается по четыре золотых, серебряных и бронзовых медали. В числе призеров попали еще три российские команды: Петрозаводский университет, Саратовский университет (серебро) и Санкт-Петербургский университет (бронза). Четвертое место завоевал Киевский университет. Очень достойно, но все равно жаль, что не первые.