SnarkNews on ACM ICPC Final-2006

 

Первая бета пресс-релиза. Замечания и предложения отправлять на snark_acm(собака)mail(тoчка)ru.

Команда Саратовского Университета - Чемпион Мира по программированию!

В Сан-Антонио прошёл финал очередного, уже 30-го, командного Чемпионата Мира по программированию под эгидой ACM (Association of Computing Machinery). В отборочных турах чемпионата 2006 года стартовали 5 606 команд из 1733 университетов 84 стран мира, в финале приняли участие 83 команды.
Эти соревнования проводятся, начиная с 1977 года, по многоуровневой системе (сначала отборочные соревнования, затем финальные). С 1977 по 1985 год в соревнованиях участвовали только североамериканские команды. Первой командой не из Северной Америки, принявшей участие в соревнованиях, была команда из Новой Зеландии, участвовавшая в 1986 году. После того, как руководство чемпионатом переместилось в Университет Бэйлор, Сан-Антонио, а директором соревнований стал Билл Пучер, возглавляющий чемпионат и по сей день, в соревнованиях стали принимать участие всё большее число команд из-за пределов Северной Америки, и с 1991 года соревнования получают статус чемпионата мира по программированию, а победитель объявляется Чемпионом Мира. Финальные соревнования проводятся в разных городах: например, в 2005 году финальная часть соревнований проходила в Шанхае, в 2004 году - в Праге. Но чаще всего - 26 раз из 30 - финалы проводились в США. Генеральным спонсором соревнований с сезона 1997-1998 года является компания IBM, и на финале в Сан-Антонио было объявлено о том, что IBM останется генеральным спонсором соревнований как минимум до 2012 года.

По правилам чемпионата мира, в соревнованиях могут участвовать команды университетов, составленные из 3 участников. Каждый участник должен быть студентом или аспирантом соответствующего университета, при этом для одного человека запрещено выступление более, чем в двух финалах.

На время соревнований (обычно оно составляет пять часов) каждой команде из трёх участников предоставляется один компьютер с установленными на нём средствами разработки программ и выходом на систему автоматического (или полуавтоматического, как это принято в финале) тестирования. Для решения участникам обычно предлагается от 8 до 12 задач. Решением каждой задачи должна являться программа на одном из принятых на соревнованиях языков программирования (в этом году это Java, C, C++. До прошлого года в этом списке был и Pascal, но в этом году он поддерживался лишь частично, а со следующего года не будет поддерживаться вообще). Если команда считает, что решение готово, она направляет его на тестирование. Система проверки тестирует решение на заранее заданном автором задачи наборе тестов. Если на каком-то тесте программа некорректно завершилась, превысила заданное в условии задачи время работы на одном тесте, или дала неправильный ответ, команда получает краткое сообщение об ошибке. При этом сам тест, на котором произошла ошибка, команде не сообщается. Если же программа правильно отрабатывает на всех тестах, то задача команде засчитывается, кроме того, к "штрафному времени" прибавляется время от начала соревнований до момента сдачи задачи, а также по 20 минут за каждую неудачную отправку решения, сделанную по этой задаче. Побеждает команда, решившая больше всех задач, а если таких команд несколько, то команда, получившая среди них наименьшее "штрафное время".

При этом участники и зрители могут в течение первых четырёх часов соревнований видеть "монитор" - таблицу, в которой команды отсортированы по текущему результату (то есть из двух команд выше находится та, у которой больше задач, а при равном числе задач - та, у которой меньше штрафное время). Также в таблице отражаются результаты попыток каждой команды по каждой задаче, что позволяет участникам хотя бы примерно ориентироваться, насколько сложной оказалась та или иная задача. В последний час соревнований таблица не обновляется - для поддержания интереса участников перед закрытием соревнований. Однако в финале, где все участники сидят в одном зале, а за каждую решённую задачу команде выдают воздушный шарик соответствующего цвета, зрители могут следить за результатами соревнований в последний час по принесённым шарикам.

Через некоторое время по окончании соревнований (обычно в тот же день) подводятся итоги и объявляется абсолютный победитель и призёры. Схема распределения медалей также менялась из года в год, пока в последнее время не установился следующий вариант: места с 1 по 4 получают золотые медали, места с 5 по 8 - серебряные, места с 9 по 12 - бронзовые. Далее идут команды, решившие то же число задач, что и команда, занявшая 13 место, у которых в качестве места указано 13-е (то есть для этих команд "штрафное время" не учитывается, а в списке они расположены по алфавиту), потом - команды, решившие на одну задачу меньше, чем 13-е место (у них у всех также указано одно и то же место), и так до тех пор, пока количество команд, решивших данное или меньшее количество задач, составляет больше половины от всех участнков финала. Остальные команды получают Honorable Mention, то есть грамоту участника без указания места.

Сейчас отбор на финальные соревнования проводится по многоступенчатой схеме: все университеты мира разбиты на регионы (по территориальному признаку), в которых проводятся полуфиналы. Наиболее крупные регионы разбиты на подрегионы, и отбор в полуфинал проводится по результатам четвертьфиналов. Более того, в некоторых регионах (например, в Китае) уже проводятся и 1/8 финала. Для каждого полуфинала каждый год определятся квота команд, которые выходят от данного полуфинала в финал, при этом от одного вуза в финале не может участвовать более одной команды. Выделяемая региону квота зависит от количества команд, участвовавших в отборочных соревнованиях от данного региона, результатов, показанных регионом, и ряда других факторов. По итогам финала также определяются чемпионы континентов - то есть лучшая команда среди всех, вышедших в финал из приписанных к данному континенту регионов.

Первой командой постсоветского пространства, участвовавшей в финале Чемпионата Мира по программированию, была команда Киевского Национального Университета имени Тараса Шевченко, участвовавшая в финале 1995 года. Российские команды участвовали в отборочных соревнованиях, начиная с 1993 года, когда в полуфинале в Варне участвовала команда СПбГУ. В финал 1996 году вышли команды сразу двух российских университетов - СПб ГУ ИТМО (первое место в полуфинале NWERC в Амстердаме) и МГУ (третье место в полуфинале SWERC в Цюрихе). В сезоне 1996-1997 года было принято решение о формировании Северо-Восточного полуфинального сектора (NEERC), куда входят все постсоветские государства, кроме Украины и Молдовы, которые участвуют в SEERC. Полуфиналы NEERC проходят в Санкт-Петербурге, а директором NEERC с момента основания является профессор СПб ГУ ИТМО Владимир Глебович Парфёнов. В сезоне 1998-1999 года были сформированы первые четвертьфинальные подрегионы с центрами во Владивостоке, Екатеринбурге, Минске, Рыбинске, Санкт-Петербурге, Саратове. В этом году четвертьфиналы проходили уже в 15 подрегионах (центры - Алматы, Баку, Бишкек, Владивосток, Екатеринбург, Ереван, Минск, Москва, Красноярск, Новосибирск, Рыбинск, Санкт-Петербург, Саратов, Ташкент, Тбилиси), при этом полуфинал NEERC проходил одновременно в Барнауле, Батуми, Санкт-Петербурге и Ташкенте, а квота от региона на финал составила 11 команд.

По результатам полуфинала 2005 года в финале в Сан-Антонио приняли участие 10 российских команд (команды Алтайского ГТУ, МГУ, Петрозаводского ГУ, Саратовского ГУ, СПбГУ, СПб ГУ ИТМО, Уральского ГУ, Уфимского ГАТУ, Южно-Уральского ГУ, Ярославского ГУ) и одна команда из Казахстана (Казахско-Британский ТУ). Кроме того, от SEERС в финале участвовали две украинские команды - команды Киевского НУ и Винницкого ГТУ. Для сравнения скажем, что Китай в Сан-Антонио был представлен 10 командами, США - 17 командами, Канада - 5 командами.

В прошедшие годы команды из постсоветских государств и особенно - из России показывали высокие результаты в финалах: в 2000 и 2001 годах команда СПбГУ становилась чемпионом мира и Европы, в 2004 году чемпионом мира и Европы стала команда СПб ГУ ИТМО.
Команды Саратовского ГУ в 2002 году и МГУ в 2005 году становились чемпионами Европы.
Второе место (и золотые медали) завоёвывали команда СПбГУ в 1998 году, команда МГУ в 2003 и 2005 годах. Третье место (также отмечаемое золотыми медалями) завоёвывали команды СПб ГУ ИТМО в 1999, 2001, 2003, 2005 годах и команда Белорусского ГУ в 2004 году.
Команда Пермского ГУ в 2004 году заняла четвёртое место и получила золотые медали, а команда СПбГУ ИТМО в 2000 году за четвёртое место получила только серебряные медали в силу того, что в то время действовали другие правила присуждения медалей.
Серебряные медали также получали команды Саратовского ГУ в 2002 и 2003 годах, Ижевского ГТУ в 2004 году, бронзовые - команды СПбГУ в 1997 и 1999 году, МГУ в 2001 и 2002 году, Киевского НУ в 2003 году, Ижевского ГТУ в 2005 году.
Чаще всего из российских вузов в финалах участвовали команды МГУ и СПб ГУ ИТМО - 11 финалов в 1996-2006 годах. В 9 финалах (1997-2001 и 2003-2006) участвовали команды СПбГУ. В общей сложности за 1995-2006 годы в финалах принимали участие команды из 18 российских, 3 украинских, 1 белорусского, 1 казахского, 1 киргизского и 1 эстонского университетов.

В этом году в финале ожидалась сильная конкуренция. Во-первых, в силу правила, запрещающего участие в финале более двух раз, закончили выступление многие сильные российские команды, в том числе команды СПб ГУ ИТМО, становившаяся чемпионом мира и Европы в 2004 году, и МГУ, становившаяся чемпионом Европы в 2005 году. Во-вторых, в силу отсутствия на финале полноценной поддержки языка Pascal, команды NEERC, много лет использовавшие именно этот язык, в большинстве своём были вынуждены перейти на C/C++ или Java. Тем не менее, чемпионом снова стала российская команда, при этом работавшая на Java!

В финале чемпионата мира 2006 года были предложены 10 задач. По результатам соревнований 2005-2006 года чемпионом мира и Европы стала команда Саратовского Государственного Университета в составе Романа Алексеенкова, Игоря Кулькина и Ивана Романова, решившая 6 задач. Команду тренирует аспирант Саратовского Государственного Университета Михаил Мирзаянов.
Кроме саратовцев, золотые медали получила занявшая второе место команда Краковского университета (Польша), также решившая 6 задач, но уступившая саратовцам по "штрафному времени", занявшая третье место с пятью задачами команда Алтайского Государственного Технического Университета в составе Дмитрия Гозмана, Романа Гоменюка и Артура Могозова (тренер команды - Е.Н. Крючкова) и занявшая четвёртое место, также с пятью задачами, команда голландского университета Твенте.

Все четыре команды, награждённые серебряными медалями, решили по пять задач. Серебряные медали и титул чемпиона Азии получила занявшая пятое место команда Шанхайского Университета (Китай), завоёвывавшего чемпионское звание в 2002 и 2005 годах. Также серебряных медалей удостоена занявшая шестое место команда Санкт-Петербургского Государственного Университета в составе Сергея Банкевича, Виталия Вальтмана и Глеба Леонова (тренер команды - чемпион мира 2000 и 2001 года Андрей Лопатин), занявшая седьмое место команда Варшавского Университета (Польша), становившегося чемпионом мира в 2003 году и занявшая восьмое место команда Массачусетского Технологического Института (США) выигрывавшего чемпионат ACM в 1978 году. Эта команда также стала чемпионом Северной Америки.

Бронзовые медали получили чемпионы России 2005 года команда Московского Государственного Университета в составе Ивана Попелышева, Андрея Румянцева, Андрея Халявина (тренер команды - Е.В. Панкратьев), занявшая девятое место с пятью задачами, команда Уфимского Государственного Авиационного Технического Университета в составе Константина Германа, Алексея Жевака, Дениса Назарова (тренер команды - А. Фридлянд), занявшая десятое место (также пять задач), а также решившие по четыре задачи с лучшим "штрафным временем" команда Университета Альберты (Канада) и золотой медалист 2005 года команда Университета Ватерлоо (Канада), становившегося чемпионом мира в 1994 и 1999 годах. Эти команды заняли, соответственно, 11 и 12 места.

Чемпионом Африки стала команда Университета Кейптауна (ЮАР), чемпионом Южной Америки - команда Технологического института аэронавтики (Бразилия), чемпионом Австралии и Океании - команда университета Аделаиды (Австралия).

Команды Киевского Национального Университета, Петрозаводского Государственного Университета, СПб ГУ ИТМО, Южно-Уральского государственного университета решили по три задачи и были квалифицированы на 19 месте (места с 19 по 38).
Команды Ярославского Государственного университета и Винницкого Национального Технического Университета решили по две задачи и были квалифицированы на 39 месте (места с 39 по 55).

Результаты российских команд можно считать выдающимися: завоёвано абсолютное первенство, две золотых медали (за 1 и 3 места), одна серебряная (за 6 место), две бронзовых (за 9 и 10 места). То есть 5 команд из 10 участвовавших получили медали. Или, иначе говоря, из 12 медалистов 5 представляют российские университеты.
Сравнив с другими странами, выставившими по 10 и более команд, видим, что у Китая из 10 команд одна серебряная медаль за 5 место, у США из 17 команд также одна серебряная медаль за 8 место.
Среди стран, от которых выступало меньшее число команд, можно отметить и выдающийся результат польских команд, представлявших центральноевропейский сектор (CEPC): из двух команд сектора две в медалях (одно золото за 2 место и одно серебро за 7 место). Возможно, что организаторам Чемпионата стоило бы пересмотреть региональные квоты на следующий год.

В заключение хочется ещё раз поздравить чемпионов мира 2006 года - команду Саратовского Государственного Университета.