|
№ 27 (4132)
июль 2005 |
Студенты МГУ снова завоевали «золото» на Студенческом командном чемпионате мира по программированию
Мы летим в Шанхай. Мы – это команда студентов Московского государственного университета, направляющаяся на финал Чемпионат мира по программированию среди студенческих команд.
За время полета еще раз вспоминаем историю чемпионатов и оцениваем свои шансы в предстоящем финале. Студенческие командные олимпиады по программированию, проводимые ACM, зародились около 30 лет назад как соревнования между несколькими американскими университетами. К настоящему времени они приобрели огромную популярность, в них участвуют более 4000 команд более чем из 1500 университетов почти из 100 стран. Сформировалась трехуровневая система проведения чемпионата: четвертьфиналы, полуфиналы и финал.
Российские команды подключились к соревнованиям в начале 90-х годов. Первые попытки были неудачными, а в сезоне 95/96 учебного года две российские команды (Московского государственного университета им. М.В. Ломоносова и Санкт Петербургского института точной механики и оптики) прошли в финал, где заняли места во втором десятке. С тех пор ни МГУ, ни СПбИТМО не пропустили ни одного финала. В 96/97 учебном году был сформирован Северо-восточный Европейский регион, куда вошли все государства бывшего Советского Союза кроме Украины и Молдовы. Представительство этого региона в финалах постоянно возрастало от 3 мест в 1997 году до 12 – в нынешнем. При определении количества мест в финале, выделяемых какому-либо региону, учитывается количество команд, принимающих участие в четвертьфиналах и полуфиналах, а также результаты, показанные в предыдущих чемпионатах. Успехи российских команд впечатляют: за эти годы они трижды завоевывали Кубок (становились чемпионами мира), и на их счету еще несколько золотых медалей (они вручаются обычно за первые три или четыре места).
В 1996 году мы очень плохо представляли себе уровень других команд и, соответственно, не могли прогнозировать результаты. Нынешний уровень российских команд мы могли оценивать достаточно объективно, основываясь на результатах не только полуфинальных, но и ряда других соревнований. Почти все российские финалисты принимали участие в традиционных сборах, проводимых Петрозаводским университетом во время зимних студенческих каникул. Значение этих сборов трудно переоценить – за 9 дней было проведено 8 полноценных пятичасовых туров. Кроме собственно соревнований, проводился разбор задач, а также команды имели возможность доделывать задачи, не сданные во время тура.
И, конечно же, все команды активно участвовали в открытых тренировках, проводимых разными университетами, как российскими, так и зарубежными.
Итак, главным фаворитом (по крайней мере, среди российских команд) представлялась команда СПбГУИТМО в составе Оршанского, Павлова и Маврина – действующих чемпионов России и мира. Баланс очных встреч с этой командой у нас был отрицательный (но далеко не нулевой). Другим российским командам мы проигрывали очень редко, хотя и от них можно было ждать сюрпризов. В частности, очень высоко оценивали потенциал новосибирской команды. Из зарубежных команд хорошие результаты на отдельных Интернет-соревнованиях показывали команды Шанхайского университета и Массачусетского технологического института. Свои шансы на медали и даже на золотые медали мы оценивали как вполне реальные, а вот на победу надежды было мало. Дополнительная ответственность ложилась на нас в связи с неудачным выступлением команды МГУ на предыдущем чемпионате. Необходимо было показать, что этот сбой был случайным.
Шанхай поразил нас своими контрастами. От аэропорта до метро ехали на скоростном поезде. Плавный разгон, скорость даже не ощущается, а спидометр показывает более 430 км/час. На современном метро доехали до железнодорожного вокзала. Далее решили идти пешком, хотя можно было пару остановок проехать на автобусе. Идем по каким-то трущобам, где в каждой подворотне что-то шипит на каких-то жаровнях, из окон торчат бамбуковые шесты со свисающими тряпками. И вдруг выходим к современной гостинице.
У нас была возможность в течение двух дней акклиматизироваться и познакомиться с достопримечательностями Шанхая и его окрестностей. Шестнадцатимиллионный город является торговым центром Китая. Традиционная китайская архитектура соседствует с современными небоскребами. Бесчисленное множество магазинов и магазинчиков, реклама компаний со всего света. Парки в восточном стиле, пагоды, буддистские храмы. Многочисленные велосипедисты и многоярусные развязки автострад.
Третьего апреля переезжаем в пятизвездочную гостиницу «Шангри-Ла», где будут проходить соревнования (до этого жили в гостинице поскромнее). Напряженная четырехдневная программа. Основные события назначены на седьмое апреля. Из остальных мероприятий отмечу только уже ставшие традиционными соревнования, когда командам дается задание написать некоторую игровую программу. Точнее, для игровой программы, разработанной организаторами, каждая команда реализует своего игрока, а потом проводится турнир, определяющий победителей. Особенность нынешнего задания состояла в том, что нужно было реализовать не одного игрока (обычно это была какая-либо машинка), а «футбольную» команду из пяти игроков. Игра запускалась на параллельном суперкомпьютере, где каждому игроку отводился отдельный процессор. Во время ужина все участники чемпионата имели возможность наблюдать за игрой. После трех туров (когда каждая команда сыграла по три игры), половина команд выбывала из соревнований, во второй круг выходили 36 команд. После еще трех туров оставалось 12 команд, которые в шести турах определяли тройку победителей. Наша команда показала хороший результат только в первой игре. Во второй круг она прошла (даже с лучшим результатом среди российских команд), но на этом ее карьера завершилась: в решающий турнир она не попала.
Наступило 7 апреля – день решающих сражений. В центре огромного зала заняли места 78 команд. С одного края – жюри, с другого – зрители: тренеры команд, представители прессы, болельщики. По крайней мере, китайские СМИ уделяют соревнованиям много внимания. К сожалению, представителей российского телевидения нет. В Москве за ходом соревнований болельщики и журналисты следили по Интернету. Текущее положение команд видно на страничке соревнований в Интернете, а вот полноценный видеорепортаж организовать не получилось. Единственное, что удалось сделать – это подключиться к Интернету из нашего номера и периодически пересылать фотографии, сделанные во время соревнований.
Удар гонга, и соревнования начались. Зрители могли следить за результатами на большом экране в фойе и на десятках мониторов в интернет-кафе этажом ниже. Зрителям также дают условия задач, пытаемся оценить их сложность, выбрать наиболее простую. Томительные минуты ожидания первых результатов. Наконец, несут первый шарик и прикрепляют его у столика команды МГУ. На мониторах видим – 23-я минута, МГУ, задача E. Ждем, чем ответят соперники. Только через 10 минут свою первую задачу (Н) сдает следующая команда – университета Амиркабира. Команда СПбГУИТМО, которую считаем главным конкурентом, сдает свою первую задачу (J) на 38-й минуте. Мы с нетерпением ждем, кто же первым сдаст 2-ю задачу. Команда МГУ, 49-я минута, задача (H). Ребята «поймали кураж». С первой попытки сдают еще 5 (на 68-й, 96-й, 131-й, 158-й и 186-й минутах). С каждой задачей отрыв от преследователей увеличивается. Так продолжается до 186-й минуты, когда наша команда сдает 7-ю задачу. У ближайших преследователей, команды СПбГУИТМО, сдано только 5. Правда, в течение следующих 10 минут они сдают еще две, сравниваясь по количеству решенных задач, но значительно (почти 3 часа) уступая по штрафному времени (888 минут против 711). Кажется, что борьба за первое место развернется между этими командами: впереди еще почти 2 часа и 3 нерешенные задачи. Ко мне несколько раз подходят корреспонденты различных газет и журналов: всех впечатляет выступление нашей команды. Отмахиваюсь – «цыплят по осени считают». До заморозки монитора время проходит в напряженном ожидании. Питерцы отметились неудачной посылкой задачи G, наши не проявляют никаких признаков активности. Подтягиваются другие команды. За час до конца соревнований, когда монитор «замораживается», команда университета Ватерлоо, как и лидеры, сдала 7 задач. По 6 задач имеют в своем активе команды Вроцлава и Шанхая. Далее идет группа команд с пятью задачами. Лучшее время в этой группе у шведской команды (действующего вице-чемпиона мира). Настораживает, что она сдала задачу D, для решения которой нужно знать некоторый не слишком известный математический результат, получить который в ходе соревнований практически невозможно. Эту задачу не сдал никто из лидеров, только команда из Киото, выступающая довольно неудачно. Среди российских команд также наблюдаются перемещения по турнирной таблице: опускается вниз удачно стартовавшая команда СПбГУ, приближаются к лидерам команды Ижевска и Уфы, поправляет турнирное положение стартовавшая крайне неудачно новосибирская команда (первая успешная сдача у них была только на 90-й минуте). Совсем не клеятся дела у нижегородцев.
Последний час результаты на мониторе не обновляются, и о сданных задачах можно судить только по разноцветным шарикам, которые приносят командам. Наша команда сидит в противоположном конце зала, мы ее практически не видим. Напряженно смотрим, не несут ли темно-синий, темно-фиолетовый или серебристый шарик (соответствующие задачам, не решенным лидерами). Среди зрителей проносится радостный гул: команде Шанхайского университета принесли 7-й шарик. И только за несколько минут до конца соревнований судьи понесли серебристый шарик: кто-то решил задачу D. Проносят его мимо команды МГУ, мимо питерцев и останавливаются около команды Шанхайского университета. Болельщики, среди которых оказалось много местных студентов, взрываются восторженными криками. Команда Шанхайского университета повторяет свой успех трехлетней давности, становясь чемпионом мира.
При взгляде на итоговую таблицу, возникает впечатление, что это уже было раньше. Как и два года назад, золотые медали завоевали команды МГУ и СПбГУИТМО, занявшие соответственно 2-е и 3-е места. Но на этот раз команда МГУ завоевала также звание чемпионов Европы. Среди медалистов и еще одна российская команда: на этот раз бронзовые медали завоевала команда Ижевска, повторив свой прошлогодний успех. Достойно выступили и другие наши команды.
Потом было торжественное закрытие и три дня, проведенные в Пекине.
Оценивая в целом результат выступления команды МГУ на прошедшем чемпионате, считаю его очень успешным: это лучший результат, показанный ею за 10 лет выступлений в финалах чемпионатов мира. Надеюсь, что это не предел, и в будущем команда МГУ сможет наконец-то завоевать заветный кубок.
Руководитель команды, вед. н. с. механико-математического факультета Е.В. Панкратьев
|
