SnarkNews on ACM ICPC Final-2007

 

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

Пять российские команд стали призёрами Чемпионата Мира по программированию!

В Токио прошёл финал очередного, уже 31-го, командного Чемпионата Мира по программированию под эгидой ACM (Association of Computing Machinery). В отборочных турах чемпионата 2007 года стартовали 6 099 команд из 1756 университетов 82 стран мира, в финале приняли участие 88 команд.
По странам наибольшее представительство у США - 20 команд, 12 команд представляют Китай, 10 - Россию.

Чемпионом мира стала команда Варшавского Университета (Польша) в составе Филипа Вольски, Мартина Пилипчука и Марека Цыгана (Filip Wolski, Marek Cygan, Marcin Pipipczuk), решившая 8 из 10 предложенных задач. Также золотые медали получили решившая 7 задач и занявшая второе место команда Университета Синьхуа (Китай), команда Санкт-Петербургского университета информационных технологий, механики и оптики, занявшая третье место и команда Массачусетского технологического института (США), занявшая четвёртое место. Команды Новосибирского Государственного Университета, Саратовского Государственного Университета, Университета Твенте (Голландия) и Шанхайского Университета имени Мао Цзе-Дуна (Китай) заняли места с 5 по 8 соответственно и получили серебряные медали, команды Университета Ватерлоо (Канада), Московского Государственного Универстета, Оклендского университета (Новая Зеландия) и Калифорнийского технологического института заняли места с 9 по 12 соответственно и были награждены бронзовыми медалями. Все команды, занявшие места с третьего по двенадцатое, решили по 6 задач. Впоследствии решением Директората финала команда Петрозаводского Государственного Университета, единственная из оставшихся команд, решившая 6 задач и занявшая 13 место, также была удостоена бронзовых медалей.

Новые чемпионы мира и Европы - команда Варшавского университета - на протяжении всего сезона доминировала в командных соревнованиях по программированию. Её участники добивались больших успехов и в личных соревнованиях, в частности, Марек Цыган был победителем Google Code Jam - 2005, а Филип Вольски, который сейчас учится на первом курсе, четыре раза выигрывал золотые медали на Международных олимпиадах школьников по информатике. В процессе подготовки к финалу команда Варшавы принимала участие в том числе и в открытых тренировках на сайтах МГУ и СПбГУ ИТМО, а также одержала уверенную победу на традиционных зимних сборах команд-участниц чемпионата мира по программированию, проводимых в Петрозаводске. На сборах команда Варшавского университета участвовала в двух этапах Открытого Кубка МГУ-CBOSS по программированию, на которых заняла первое и второе места.
В команде Университета Синьхуа, ставшей чемпионом Азии, лидером является Lou TianCheng, занимающий на данный момент третье место в мировом индивидуальном рейтинге спортивного программирования по результатам соревнований TopCoder. Кстати, лидером этого рейтинга является россиянин Пётр Митричев, в прошлом двукратный вице-чемпион мира по версии ACM в составе команды МГУ.
Команда Санкт-Петербургского государственного университета информационных технологий, механики и оптики, в состав которой входят Искандер Акишев, Михаил Дворкин и Роман Сатюков, также показывала отличные результаты на протяжении всего сезона. Уже в текущем году команда выиграла Кубок Главы Республики Карелия, а Михаил Дворкин стал победителем Зимнего Кубка Test-The-Best, финал которого проводился в середине февраля в Минске. Тренером команды,лауреатом премии Президента Российской Федерации Андреем Станкевичем, была проделана большая работа по подготовке команды к финалу, и это дало свои результаты. Интересно, что команды СПбГУ ИТМО завоёвывали золотые медали в течение 5 из 7 последних лет (в 2001, 2003, 2004 - чемпионы мира, 2005 и 2007 годах), что является уникальным достижением.
Команда Массачусетского Технологического Института второй год становится чемпионом Северной Америки. В прошлом году команда завоевала 8 место и серебряные медали, так что представители MIT достигли значительного улучшения результата и стали первой после 2002 года командой США, получившей золотые медали.

Результат российских команд в финале Чемпионата Мира, конечно, уступает результатам 2003-2006 годов, когда сразу две российские команды выигрывали золотые медали, а в 2003 и 2006 команды СПбГУ ИТМО и Саратовского ГУ становились чемпионами мира. Тем не менее, россияне в Токио выиграли 5 медалей из 13: одну золотую, две серебряных и две бронзовые - больше, чем представители любой другой страны.
Пятое место заняла команда Новосибирского Государственного Университета в составе Степана Гатилова, Владислава Кузькокова и Вячеслава Токарева. Вячеслав уже участвовал в финале ACM ICPC в 2005 г. в Шанхае, Степан и Владислав - первокурсники, однако они уже имеют опыт серьёзных соревнований, в частности, в составе школьной команды они заняли вторые места на трёх этапах Открытого Кубка МГУ-CBOSS, в котором участвуют в основном студенты, аспиранты и выпускники вузов. Тренеры команды - Т.Г. Чурина и Т.В. Нестеренко. Команда показала отличный результат, при этом не обошлось и без некоторого невезения - сибиряков отделили от золотых медалей всего 2 штрафные минуты...
Занявшей шестое место команде Саратовского Государственного Университета, в которую входили Виталий Гольдштейн, Сергей Назаров и Алексей Климов, удалось решить достаточно сложную задачу E, которую, кроме них, из призёров решили только чемпионы мира. Команда также хорошо поработала перед финалом, так, в частности, Виталий Гольдштейн и Сергей Назаров вышли в финал Зимнего Кубка Test The Best. Результат команды, тренером которой является М.Р. Мирзаянов, подтвердил высокий уровень саратовской школы программирования.
Занявшая десятое место команда Московского Государственного Университета в составе Егора Куликова, Михаила Левина и Павла Наливайко является действующим чемпионом России, так что от неё ожидали большего. Тем более, что Егор Куликов в 2005-2006 годах участвовал в полуфиналах четырёх всемирных индивидуальных турниров по программированию, организуемых Google и TopCoder, а Павел Наливайко уже был чемпионом Европы и вице-чемпионом мира в 2005 году в составе команды МГУ вместе с Петром Митричевым и Владимиром Рычёвым. Уже в 2007 году Егор и Павел участвовали в финале Зимнего Кубка Test The Best. Увы, после крайне неудачного старта команда одно время шла в районе 30-40 мест. Но, проявив спортивный характер, команда МГУ сумела в итоге войти в первую десятку и завоевать бронзовую медаль. Для тренера команды Е.В. Панкратьева это уже пятая подряд медаль Чемпионата мира, завоёванная его командами (золотые медали в 2003 и в 2005, бронзовые в 2001, 2006, 2007, в 2004 году команды, возглавляемой Е.В. Панкратьевым, в финале не было).
Команда Петрозаводского Государственного Университета в составе Дениса Денисова, Алексея и Ильи Николаевских оказалась единственной командой, решившей 6 задач, но не вошедшей в первые 12 команд. Так что решение Директората ACM ICPC о присуждении команде ПетрГУ бронзовых медалей выглядит достаточно закономерным. Отметим огромный вклад Петрозаводского Государственного Университета в подготовку команд-участниц Чемпионата Мира по программированию огромен: в течение более 5 лет в Петрозаводске организуются сборы для сильнейших российских - а теперь уже и зарубежных - команд. Так что в успехе всех команд-участниц сборов, а это и чемпионы мира команда Варшавского Университета, и все российские команды - призёры чемпионата - есть большая заслуга организаторов сборов: сотрудников ПетрГУ В.А. Кузнецова, Э.А. Завьяловой, аспиранта ПетрГУ Д.П. Власова, двукратного чемпиона мира, тренера команд СПбГУ А.В. Лопатина.

Результаты других команд, представлявших Россию и СНГ, таковы: Команда Санкт-Петербургского Государственного Университета решила 5 задач и классифицирована на 14-25 местах. Команды Белорусского Государственного Университета, Ставропольского Государственного Университета, Уральского Государственного Университета, Вологодского Государственного Педагогического Института, Национального Технического Университета Украины "КПИ" решили по 4 задачи и классифицированы на 26-43 местах. Команда Орловского Государственного Технического университета решила 3 задачи и классифицирована на 44-64 местах. Команда Казахского Национального Университета удостоена Honorable Mention.

Чемпионаты мира по программированию по версии ACM проводятся, начиная с 1977 года, по многоуровневой системе (сначала отборочные соревнования, затем финальные). С 1977 по 1985 год в соревнованиях участвовали только североамериканские команды. Первой командой не из Северной Америки, принявшей участие в соревнованиях, была команда из Новой Зеландии, участвовавшая в 1986 году. После того, как руководство чемпионатом переместилось в Университет Бэйлор, Сан-Антонио, а директором соревнований стал Билл Пучер, возглавляющий чемпионат и по сей день, в соревнованиях стали принимать участие всё большее число команд из-за пределов Северной Америки, и с 1991 года соревнования получают статус чемпионата мира по программированию, а победитель объявляется Чемпионом Мира. Финальные соревнования проводятся в разных городах: например, в 2005 году финальная часть соревнований проходила в Шанхае, в 2004 году - в Праге. Но чаще всего - 26 раз из 31 - финалы проводились в США. Генеральным спонсором соревнований с сезона 1997-1998 года является компания IBM.

Fact sheet


По правилам чемпионата мира, в соревнованиях могут участвовать команды университетов, составленные из 3 участников. Каждый участник должен быть студентом или аспирантом соответствующего университета, при этом для одного человека запрещено выступление более, чем в двух финалах.
На время соревнований (обычно оно составляет пять часов) каждой команде из трёх участников предоставляется один компьютер с установленными на нём средствами разработки программ и выходом на систему автоматического (или полуавтоматического, как это принято в финале) тестирования. Для решения участникам обычно предлагается от 8 до 12 задач. Решением каждой задачи должна являться программа на одном из принятых на соревнованиях языков программирования (в этом году это Java, C, C++). Если команда считает, что решение готово, она направляет его на тестирование. Система проверки тестирует решение на заранее заданном автором задачи наборе тестов. Если на каком-то тесте программа некорректно завершилась, превысила заданное в условии задачи время работы на одном тесте, или дала неправильный ответ, команда получает краткое сообщение об ошибке. При этом сам тест, на котором произошла ошибка, команде не сообщается. Если же программа правильно отрабатывает на всех тестах, то задача команде засчитывается, кроме того, к "штрафному времени" прибавляется время от начала соревнований до момента сдачи задачи, а также по 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 года были сформированы первые четвертьфинальные подрегионы с центрами во Владивостоке, Екатеринбурге, Минске, Рыбинске, Санкт-Петербурге, Саратове. В этом году четвертьфиналы проходили уже в 14 подрегионах (центры - Алматы, Бишкек, Владивосток, Екатеринбург, Ереван, Минск, Москва, Красноярск, Новосибирск, Рыбинск, Санкт-Петербург, Саратов, Ташкент, Тбилиси), при этом полуфинал NEERC проходил одновременно в Барнауле, Ереване, Санкт-Петербурге и Ташкенте, а квота от региона на финал составила 12 команд.

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