Команда студентов механико-математического факультета МГУ им. М. В. Ломоносова в этом году завоевала золотые медали в финале чемпионата мира по командному программированию среди студентов (International Collegiate Programming Contest, ICPC), который проводит ведущая мировая компьютерная ассоциация Association for Computing Machinery. Команда МГУ заняла второе место, пропустив вперед только команду Шанхайского университета Жиатонг, ставшую абсолютным чемпионом мира.
О финале, о подготовке вице-чемпионов мира в командных соревнованиях и об особенностях олимпиадного программирования рассказывает руководитель команды МГУ, старший преподаватель мехмата МГУ Антон Панкратьев.
- Расскажите, пожалуйста, о соревновании.
Чемпионат мира ACM ICPC проводится уже больше 30 лет. Первоначально это мероприятие организовывалось только для университетов США и Канады, позже в нем стали принимать участие представители Австралии и Новой Зеландии, затем – европейские и азиатские вузы. Сейчас соревнование охватывает студентов со всего мира. Через сито четвертьфиналов и полуфиналов проходит около 7 тыс. команд.
В финальном соревновании команде из трех человек предоставляется компьютер и предлагается набор из 8-12 задач на пять часов. Решения посылаются жюри и проверяются на заранее подготовленном наборе тестов. Лучшей становится команда, решившая большее число задач. Если несколько команд решили одинаковое число задач, их места определяются по штрафному времени, которое считается по каждой решенной задаче от момента начала соревнования до момента ее сдачи и затем суммируется по всем решенным задачам. Если команда сдала задачи на 30-й, 35-й и 40-й минутах, суммарное штрафное время составит 105 минут. Кроме того, за каждую попытку сдать неверное решение добавляется 20 минут штрафного времени, но только в том случае, если эту задачу в конце концов удается решить.
В финальных соревнованиях в этом году участвовало 103 команды. Призовых мест, как правило, 12: четыре комплекта золотых медалей, четыре серебряных и четыре бронзовых. Кроме того, определяется абсолютный чемпион мира, а также чемпионы континентов. Например, в этом году команда МГУ заняла второе место и стала вице-чемпионом мира, но, поскольку мы вперед пропустили только китайцев, то одновременно завоевали звание чемпионов Европы.
Команды Варшавского университета и СПбГУ, занявшие восьмое и девятое места, показали абсолютно идентичные результаты. Жюри решило вручить дополнительный комплект серебряных медалей.
Финалу предшествуют полуфинальные соревнования. Российские команды вместе с белорусами, представителями Южного Кавказа, иногда Украины участвуют в северо-восточном европейском региональном полуфинале, который традиционно проводится в Санкт-Петербурге в ноябре. По правилам ACM ICPC, от университета в финал выходит только одна команда, однако в полуфиналах могут участвовать несколько. Традиционно университеты, которые из года в год показывают высокие результаты, такие как МГУ, СПбГУ ИТМО, СПбГУ, Саратовский госуниверситет и ряд других, в нашем полуфинале представляют две-три, иногда даже четыре команды.
В полуфинал команды попадают из четвертьфинальных соревнований. В МГУ проходит четвертьфинал для команд Москвы и Подмосковья, в котором только от Московского университета участвует около 20 команд, преимущественно с мехмата и ВМиК, много команд из МГТУ им. Баумана, МАИ, Физтеха и ряда других вузов, которые занимаются олимпиадным программированием.
Участники четвертьфинала регистрируются на сайте чемпионата, и в соответствии с правилами состав команды не может меняться в течение года. Еще одно ограничение состоит в том, что участник не может принимать участие в соревнованиях, если он уже дважды выходил в финал, поэтому многие талантливые студенты довольно рано заканчивают свои выступления в ACM ICPC. Кроме того, нельзя принимать участие более чем в пяти четвертьфиналах.
- Промежуточные соревнования и финал проходят в одинаковом формате?
Небольшие различия могут быть в том, на каких языках разрешается писать решения. Для каждой задачи также указываются ограничения по времени выполнения и по памяти. Чтобы их удовлетворить, необходимо тщательно обдумывать алгоритм и правильно выбирать язык программирования, поскольку это напрямую влияет на быстродействие программы.
Текущие результаты отображаются на табло, которое показывает расположение мест, успешные и неуспешные попытки сдачи задач, с какой попытки задача решена. Это достаточно захватывающее действо, потому что с решением одной или двух задач ситуация может кардинально поменяться, особенно, если команды показывают близкие результаты.
За час до окончания соревнования результаты на таблице замораживаются для поддержания интриги. Это действительно время адреналинное. В этом году в финале было введено новшество – в замороженной таблице показывали, что команда предпринимает попытку сдать задачу. Из этого можно сделать вывод, что задача решена, но решение может быть ошибочным. Только когда команда предпринимает вторую попытку сдачи, становится понятно, что первая была неудачной.
Финальные соревнования представляют собой настоящее шоу. Все 100 команд сидят в одном зале, и, как только команда успешно сдает задачу, ей приносят цветной воздушный шарик. Эта процедура продолжается и после заморозки результатов и остается единственным способом определить, что команда успешно сдала задачу.
- Какие у вас впечатления о финале этого года?
Финал 2010 проходил в китайском Харбине. Как известно, это город русского происхождения, и нам было приятно побывать в этом кусочке России в Китае. Время финала было выбрано нестандартное – самое начало февраля, хотя обычно он проходит в марте - апреле. В начале февраля в Харбине проходит фестиваль ледяных скульптур, и организаторы приурочили соревнования к этому событию, для участников проводились экскурсии. Это захватывающее зрелище, несмотря на тридцатиградусный мороз.
Финал проходил в зале библиотеки Технического университета Харбина. Конкуренция была в основном между российскими и китайскими командами. Эти соревнования на протяжении всего первого десятилетия XXI века выигрывали команды России, Китая и Польши, и в этом году 13 первых мест заняли студенты из Китая, России, Украины, Польши и Швеции. Первые две команды-чемпиона – Шанхайский и Московский университет – решили по семь задач из 11, а следующие команды на призовых местах – по шесть задач. В начале соревнований одним из лидеров был Стэнфордский университет, но к середине соревнований они затормозили и не смогли получить медали, как и вообще все команды из американских вузов.
К середине соревнований вперед вырвался Шанхайский университет. И только команда МГУ пыталась его догнать. Эти две команды сильно оторвались от всех остальных – к моменту заморозки результатов у студентов из Шанхая было решено семь задач, у наших ребят - шесть. В последний час зрители видели, что обе команды предпринимали попытки сдать очередную задачу. Наши ребята сдали седьмую задачу, по количеству задач догнав шанхайцев, но у китайской команды было лучшее время. Конечно, нам немного обидно, но при этом мы проиграли очень сильной команде.
- Какова история участия российских команд в этом чемпионате?
Российские команды участвуют в финалах ACM ICPC с 1996 года. У истоков олимпиадного программирования в МГУ стоял мой отец, ведущий научный сотрудник механико-математического факультета Евгений Васильевич Панкратьев. В 1996 году ребята пришли к нему с инициативой, он ее подхватил и с тех пор каждый год всю эту деятельность организовывал, возил ребят на различные соревнования и тренировочные сборы. К сожалению, два года назад его не стало. Сейчас мы продолжаем его дело.
Наши коллеги и одновременно конкуренты, студенты ВМиК, тоже выходили в финал. Но надо подчеркнуть, что команда, выступающая в финале, представляет именно университет, а не определенный факультет. Команды могут быть смешанными так, в прошлом году в команду МГУ входили два студента ВМиК и один с мехмата, а в позапрошлом – наоборот. Часто такие команды формируются из выпускников школы Колмогорова при МГУ или из студентов, приехавших учиться в МГУ из одного города. Ребята, которые вместе учились несколько лет, поступают на разные факультеты, но продолжают дружить и хотят участвовать вместе. Большинство участников соревнований, которые показывают высокие результаты, приходят в университет уже с наградами за школьные успехи в программировании, это могут быть медали соревнований мирового уровня.
Команда МГУ три раза завоевывала золотые медали ACM ICPC – в 2003-м, 2005-м и в этом году, все три раза мы были вице-чемпионами.
- Почему в финале выбирается по четыре золотых, серебряных и бронзовых призера?
Думаю, это тоже элемент шоу. Лет десять назад было по три комплекта медалей каждого достоинства. Принятый сегодня комплект из 12 медалей впервые удалось расширить команде Петрозаводского университета. Три года назад они заняли 13-е место, решив столько же задач, что и медалисты. Поэтому жюри пошло на исключительный шаг и вручило дополнительные бронзовые медали, желая подчеркнуть, что команды поднимаются выше в таблице результатов именно по числу решенных задач. Аналогично команда Уральского государственного университета в этом году оказалась единственной командой за пределами первых двенадцати, решившей не менее шести задач, и – теперь уже традиционно для таких случаев – получила бронзу.
Это и своеобразный пиар. Немаловажная составляющая этого события - дальнейшая карьера участников. Все триста человек, пробившиеся в финал, являются программистами высочайшего уровня. Но если человек может похвастать, что он стал медалистом, то это очень серьезная заявка. Поэтому организаторы вместо того, чтобы сделать медалистами девять студентов, дают такую возможность 36 участникам.
Но такое количество медалей на самом деле отражает уровень команд. Участники из первой десятки могут показывать очень близкие результаты, например, два года назад команды, занявшие второе, третье и четвертое места, решили одинаковое количество задач, но отличались по времени в пределах 10 минут.
- Какого рода задачи решают участники финала?
Приведу пример одной теоретико-числовой и одной геометрической задачи. Дано большое число, например 20 десятичных цифр, и рассматриваются все перестановки его цифр. Требуется вычислить наибольший общий делитель всех полученных в совокупности чисел. Эту задачу в свое время предложил Евгений Васильевич Панкратьев; она довольно хитрая, тупого перебора здесь мало. Пример геометрической задачи – есть прямоугольный параллелепипед, две точки на его поверхности, в одной из них находится таракан, в другой кусочек сыра. Нужно вычислить кратчайший путь между этими двумя точками. Надо анализировать развертки, которых очень много, оптимальный маршрут может проходить по пяти граням из шести.
- Как проходит подготовка команд, в чем заключается роль тренеров, руководителя команды?
Команды готовятся в течение года. Еженедельно, а перед финалом - несколько раз в неделю проходят тренировки, которые состоят в решении задач из соревнований прошлых лет разного уровня. Тренеры выбирают задачи, проводят тренировки, помогают найти правильные подходы к решению. Тренеры нашей команды – в основном бывшие участники и победители аналогичных соревнований: Петр Митричев, Михаил Левин, Олег Христенко.
Команду надо научить выбирать свою стратегию, которая имеет очень большое значение для победы. Есть команды, которые стараются быстро написать легкие задачи, чтобы потом подумать над сложными, а есть такие, кто решают легкие задачи и одновременно начинают продумывать сложные. Силы надо рассчитывать. Можно, решив сначала сложные задачи, потом добрать легкие и выиграть по числу задач. А можно растерять запал на легких задачах и остаться без сил на решение сложных.
Как правило, в команде один человек пишет задачу, второй следит, чтобы в коде не было ошибок. Бывают случаи, когда команда считает, что задачу проще полностью переписать другому участнику. Но и это не всегда приводит к победе. Два года назад сильнейшая варшавская команда – действующие чемпионы мира, которым все прочили повторное чемпионство, - уткнулась в одну задачу, переписывали ее три раза, но так и не сдали, в итоге вообще не получив медалей. С моей точки зрения, их подвела неправильная стратегия.
Помимо тренерских задач, есть еще множество организационных – команду надо вывозить на тренировочные сборы, на различные соревнования. Эти задачи ложатся на плечи руководителя команды. В течение года проходит немало очных соревнований, например открытое первенство Уральского государственного университета или Всесибирская олимпиада им. Поттосина. Дважды в год Петрозаводский университет проводит тренировочные сборы, на которые собираются лучшие команды. Это в основном участники из сильнейших российских вузов, но приезжают и студенты из Белоруссии, Украины, бывают японцы, американцы. Об уровне мероприятия говорит тот факт, что два года назад из 12 победителей финала семь команд прошли петразоводские сборы. Каждый день ребята пишут пятичасовой контест, потом делается разбор задач. Каждый вуз должен предоставить свой комплект задач, то есть команда учится не только решать, но и писать задачи, а это тоже очень важно. Очень полезно также сравнивать свое решение с теми, которые предложат другие участники. Если команда правильно делает выводы, потенциал для ее развития колоссален.
С 2004 года проходит организованный МГУ и компанией CBOSS Открытый кубок по программированию, который теперь носит имя Евгения Васильевича Панкратьева. Это соревнование организовано по принципу Кубка мира по биатлону – несколько этапов в год, зачетные очки, победитель определяется по итогам всего года. Количество этапов постоянно растет, сейчас их около десяти, в том числе гран-при Петергофа, гран-при Беларуссии, соревнования в Тбилиси. Генеральный спонсор кубка - компания "Яндекс", которая также поддерживает участие наших команд в различных соревнованиях, в частности поездку на финал. Еще один наш спонсор – "Газпром ВНИИГАЗ" – поддерживает участие команды в петрозаводских сборах, кроме того, олимпиадники выполняют по их заказу программистские работы, которые требуют эффективной реализации.
- Расскажите о победителях этого года.
Все они студенты мехмата. Пятикурсник Алексей Гусаков пять лет участвует в чемпионате в составе различных команд, я очень рад, что к концу карьеры в АСМ ICPC он достиг такого выдающегося результата. Илья Корнаков учится на четвертом курсе, очень талантливый программист. Третьекурсник Илья Разенштейн, еще будучи школьником, показывал высочайшие результаты на международных соревнованиях.
- Как распределяются роли между тремя участниками команды?
Распределение ролей обычно таково: два хороших программиста и один хороший математик. При этом, как правило, все трое универсалы, программисты разбираются в математике, а математик сам может написать программу. Но есть задачи на реализацию, а есть задачи, которые требуют хорошей математики. Бывает и так, что команда состоит из трех очень сильных индивидуалов, они распределяют задачи между собой и каждый пишет свою. Такая команда была у нас два года назад, показала очень высокий результат, завоевав серебряные медали.
Участники этого года тоже очень сильны индивидуально, но больше работают в команде. Они вместе уже третий год, хорошо сработались, знают, кто, к кому, за каким советом может обратиться, но в финал пробились первый раз.
- Можно ли по результатам финала делать выводы об уровне обучения программированию в соответствующих университетах?
Думаю, эти результаты не полностью отражают уровень обучения програмированию. Многие университеты, где преподается программирование, вообще не принимают участия в таких соревнованиях. В олимпиадном программировании есть очень сильная математическая составляющая, поэтому для успеха команды важна математическая подготовка.
[ фото - AECMS - ACM_ICPC_0329 ] Антон Панкратьев: "Участники нашей команды этого года очень сильны индивидуально, но больше работают вместе"