Битва Мозгов

Кислицин Никита (udalite.livejournal.com)

Хакер, номер #114, стр. 071

ACM ICPC - чемпионат мира по спортивному программированию

Этой весной, с 6 по 10 апреля, в маленьком горном городке Банф на западе Канады, три сотни лучших молодых математиков и программистов собрались в одном месте для участия в чемпионате мира по спортивному программированию ACM ICPC, главным спонсором которого выступает корпорация IBM. По приглашению этой замечательной компании я и отправился в Канаду, чтобы своими глазами увидеть битву лучших молодых умов планеты.

Спортивное программирование

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

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

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

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

Участники

В финале ACM ICPC 2008 участвовало 100 команд со всего мира, причем от каждого ВУЗа могла быть заявлена только одна команда, состоящая из трех участников – студентов, либо аспирантов этого учебного заведения.

У России в этом году было весьма впечатляющее как по количеству, так и по именам, представительство из 11 команд: Алтайский ГТУ, Спб ИТМО, Ижевский ГТУ, МГУ, МФТИ, Новосибирский ГУ, Орловский ГТУ, Петрозаводский ГУ, СпбГТУ, Ставропольский ГУ и Уральский ГУ. Так же среди участников были такие известные вузы как MIT, Стэнфорд, Оксфорд и Принстон. И конечно же, на финал 2008 приехали победители прошлогоднего турнира – команда Варшавского Университета.

Команды начали прибывать в Банф за три дня до финального соревнования: нужно было отдохнуть после сложного перелета (многие летели с тремя-четырьмя пересадками), более-менее привыкнуть к новому часовому поясу (-9 часов от Москвы) и соринетироваться на достаточно интересной местности: Банф представляет собой очень уютный маленький городок, окруженный высокими скалистыми горами и национальным парком с термальными источниками.

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

Однако чем ближе был финал, тем неохотнее участники говорили о нем, предпочитая разговаривать о погоде, ледниках и клубнике на завтрак. Все-таки цена приближающегося финала для каждого из участников была огромна: каждый проделал большой путь и огромную работу, чтобы попасть сюда. В этом смысле каждый из трехсот участников финала ACM ICPC уже был победителем: он проделал невероятную работу, чтобы приехать и участвовать в этом чемпионате. Но каждый кто приехал – приехал не только чтобы участвовать, но и чтобы попытаться выиграть. А сделать это было ой как не просто.

Финал

Для решения 11 предложенных в этом году задач участникам было отпущено 5 часов, и в 8 утра 9 апреля время пошло. Соревнование проходило в большом зале, где было размещено сто столов, сто компьютеров и триста стульев. Участники были физически изолированы и могли пользоваться только тем, что было на их столах: бумагой, ручками, калькуляторами и одним компьютером с установленными компиляторами C, C++ и Java – язык каждая команда могла выбирать по своему усмотрению. Помимо этого, конечно, присутствовал доступ к полуавтоматической тестирующей системе для проверки решений, которая прогоняла тестируемую программу на наборе тестов, проверяя корректность работы.

Главный показатель, по которому оценивается выступление команд – это количество решенных задач. На втором месте стоит параметр «время», который формируется как сумма времен, прошедших с начала соревнования до принятия тестирующей системой каждой из отправленных задач. Так же к этому времени добавляется по 30 минут штрафного времени за каждую неудачную тестирующую попытку, если в итоге эта задача была принята системой.

Само соревнование, несмотря на отсутствие какого-то живого действа, не смотрится скучно. Во-первых, это заслуга прекрасной организации: резульатыт команд транслируются online на больших дисплеях и можно наблюдать живую статистику: кто сколько задач решил, какие задачи проверяются, какие задачи решают чаще всего и так далее. Во-вторых, после начала соревнования всме желающим раздали сами задачи и каждый мог попробовать свои силы в их решении – во всяком случае, поразмышлять над ними. Ну и в третьих, во время финала в зале стояла такая мощная творческая и созидательная атмосфера, что оттуда совсем не хотелось уходить.

Результаты

Выше я написал, что результаты транслировались online на больших экранах. Однако за 1 час до окончания конкурса эти результаты перестали публиковаться: на экране лишь показывались проверяемые задачи, результат проверки не показывался и было непонятно, какие задачи защитаны, а какие – нет. По замыслу организаторов это должно было сохранить интригу до финального объявления результатов. И сохранило бы, если бы одна из команд решила бы больше всех задач: в этом случае пришлось бы считать время.

Однако судьба, знания и талант ребят из ИТМО (Санкт-Петербургский государственный университет информационных технологий, механики и оптики) распорядились по другому: они решили 8 из 11 задач и сразу после окончания соревнования можно было с достаточными оснаваниями полагать, что именно они и выиграли Чемпионат.

В итоге так и получилось. Финальные результаты (12 призеров):

Place Name Solved Time

1 St. Petersburg University of IT, Mechanics and Optics 8 1187

2 Massachusetts Institute of Technology 7 997

3 Izhevsk State Technical University 7 1008

4 Lviv National University 7 1010

5 Moscow State University 7 1165

6 Tsinghua University 7 1347

7 Stanford University 7 1354

8 University of Zagreb 7 1404

9 University of Waterloo 7 1597

10 Petrozavodsk State University 6 819

11 St. Petersburg State University 6 826

12 Belarusian State University 6 857

Заключение

Для обычного человека спортивное программирование – понятие сродни айсбергу. Видна только лишь малая часть всего, что существует, и та часть, которая скрыта, как раз и представляет собой наибольшую значимость. Потому что любой финал любого чемпионата мира был бы невозможен без долгой подготовки участников, без фундаментального обучения и накопления знаний, без тренировок и участия в многочисленных отборочных раундах. Финал ACM ICPC – как раз вершина айсберга, под которой находятся тысячи команд и участников, экспабайты накопленных знаний и долгие годы учебы и тренировок.

Но именно все это и представляет наибольшую ценность: это будущее человечества и фундаментальной науки. Кто знает, может, кто-то из этих патней в будущем поможет разработать систему для предсказания землетрасений, или для моделирования развития и лечения неизлечимых болезней.

Вот что сказал Билл Паучер (Bill Poucher): «Энергия, свежие идеи и талант этих суперзвезд способны помочь обществу в решении многих проблем и изменить мир к лучшему. Они умеют работать в команде, и они добьются успеха, значительно расширяя возможности, которые мы используем сегодня для взаимодействия друг с другом».

Пример задачи: Поиск пароля

Хочешь попробовать свои силы в решении задач с Чемпионата? Нет проблем. Вот сокращенный и адаптированный перевод одной из задач.

Ты - компьютерный взломщик и почти взломал крутейшую систему. Одна проблема - тебе нужен особый пароль, о котором ты знаешь совсем немного.

Известно, что он состоит из букв алфавита [a-z], кроме того ты можешь узнать его длину и некоторые его части (которые могут перекрывать друг друга). И конечно, не известно где конкретно в пароле они располагаются.

Задача - написать программу, которая из входной информации (длина пароля, некоторые куски пароля, которые могут пересекать друг друга)  будет определять число возможных паролей и если это число не больше 42, то выводить все варианты.

Входные данные таковы, что число вариантов пароля не больше 10^15. Длина пароля от 1 до 25, число известных кусков пароля - от 0 до 10.

WWW

• icpc.baylor.edu – официальный сайт Чемпионата. Тут ты можешь посмотреть фото и видео-архив, скачать задания с предыдущих соревнований и получить любую другую информацию о Чемпионате.
• www.snarknews.info – Новости российских и международных чемпионатов по программированию
• www.topcoder.com – сайт «сольного» чемпионата для программистов
• www.opencup.ru – открытый чемпионат МГУ по программированию
• google.com/codejam – чемпионат codejam, который проводит Google
• acm.timus.ru – сайт УрГУ, посвященный олимпиадам по программированию. Тут размещен выдающийся архив задач и проверяющая система

DVD

На нашем диске ты найдешь PDF-документы с задачами с прошлых чемпионатов, а так же фотографии с финала ACP ICPC 2008 в Канаде.