SnarkNews on ACM ICPC Final-2010

 

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

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

В Харбине прошёл финал очередного, уже 34-го, командного Чемпионата Мира по программированию под эгидой ACM (Association of Computing Machinery). В отборочных турах чемпионата 2010 года стартовали 7319 команд из 1931 университетов 82 стран мира, в финале приняли участие 103 команды.
По странам наибольшее представительство у США - 21 команда, 20 команд представляют Китай, 11 - Россию.

Чемпионом мира стала команда Шахнайского Университета Жиатонг (Китай) в составе Bin Jin, Wu Zhuojie, Zhao Zheng, решившая 7 из 11 предложенных задач. Также золотые медали получила занявшая второе место и ставшая чемпионом Европы команда Московского Государственного Университета, также решившая 7 задач, команда Национального Тайваньского Университета (Тайвань), занявшая третье место c 6 решёнными задачами, и команда Киевского национального университета им. Тараса Шевченко (Украина), занявшая четвёртое место также с 6 задачами. Команды Петрозаводского Государственного Университета, Университета Синьхуа (Китай), Саратовского Государственного Университета, Варшавского университета (Польша) и Санкт-Петербургского Государственного Университета заняли места с 5 по 9 соответственно и получили серебряные медали, команды Университета Фудан (Китай), Университета Чжуньшань (Китай), Королевского Технологического Института (Швеция) и Уральского Государственного Университета заняли места с 10 по 13 соответственно и были награждены бронзовыми медалями. Все команды, занявшие места с третьего по тринадцатое, решили по 6 задач.

В состав новых чемпионов мира - команды Шанхайского университета - входит действующий победитель TopCoder Open (неофициального личного первенства мира по программированию, проводимого компанией TopCoder) Jin Bin, который, таким образом, установил уникальное достижение: стал первым, кто в одном сезоне выиграл командное и личное первенства мира по программированию. Учитывая традиционно сильное выступление китайских команд, а особенно - команды Шанхая на "домашних" турнирах (этот же университет выиграл чемпионат мира в 2005 году, когда чемпионат также проводился в Китае), результат в чём-то закономерный.

Единственной командой, кроме чемпионов мира, решившей 7 из 11 предложенных задач, стали чемпионы Европы - команда Московского Государственного Университета. В составе команды - студенты механико-математического факультета МГУ Алексей Гусаков, Илья Корнаков и Илья Разенштейн.
МГУ, наряду с СПбГУ ИТМО, был первым российским вузом, принимавшим участие в Чемпионатах Мира по программированию. Эти два университета участвуют во всех финалах, начиная с 1995 года. Начиная с первого "российского" финала в 1995 году, подготовку команд МГУ возглавлял ведущий научный сотрудник мехмата МГУ Евгений Васильевич Панкратьев. Под его руководством команды МГУ дважды - в 2003 и 2005 годах - становились вице-чемпионами мира, а в 2002, 2006, 2007 годах - завоёвывали бронзовые медали. Также по инициативе и при активном участии Е.В. Панкратьева МГУ в сотрудничестве с российскими IT-компаниями организовал Открытый Кубок по программированию - регулярное многоэтапное соревнование, в котором участвуют команды из России, стран бывшего СССР, а также некоторых стран Восточной Европы. После трагической гибели Евгения Васильевича в январе 2008 года Открытому Кубку было присвоено его имя. Подготовку команд мехмата МГУ возглавил его сын - доцент МГУ Антон Евгеньевич Панкратьев, который достойно продолжил дело отца: в 2008 году команда МГУ завоевала серебряные медали, а в этом уже в третий раз в истории стала вице-чемпионом мира и во второй раз - чемпионом Европы.
Для всех участников команды МГУ это был первый финал, причём в полуфиналах северо-западного европейского подрегиона (NEERC) команда в таком составе участвует третий раз. В прошлом году они заняли третье место - но в финал поехала другая команда МГУ, которая заняла второе место (от одного вуза в финал выходит только одна команда). Зато в этом сезоне команда стабильно показывала высокие результаты: заняла второе место по итогам VI Открытого Кубка им. Е.В. Панкратьева, второе место в полуфинале NEERC, в декабре 2009 года в Петрозаводске выиграла сборы команд вузов-финалистов Чемпионата мира. Отметим, что Илья Разенштейн, ещё будучи нижегородским школьником, в 2006 и 2007 входил в состав сборной России на Международной олимпиаде по информатике - и оба раза выигрывал золотые медали.

Третье место заняла команда Национального Университета Тайваня. Это первые золотые медали для тайваньских студентов.

На четвётром месте команда Киевского Национального университета им. Т.Г. Шевченко. Это повторение лучшего результата для украинских команд (до этого 4 место было у команды Львовского Национального Университета в 2008 году). В составе команды - Даниил Нейтер, Владислав Симоненко и Андрей Гриненко. Все они в своё время были призёрами Международных олимпиад школьников по информатике: Даниил Нейтер выигрывал золотые медали в 2006 и 2007 годах, Андрей Гриненко - золотую медаль в 2005 году и бронзовую в 2004, Владислав Симоненко - серебряную медаль в 2006 году. При этом Андрей Гриненко уже участвовал в финале Чемпионата Мира по программированию в 2007. В этом сезоне команда выиграла полуфинал юго-восточного европейского подрегиона с отрывом в 2 задачи от второго места, а на традиционных сборах команд вузов-финалистов Чемпионата Мира, состоявшихся в декабре 2009 года в Петрозаводске, заняла второе место после команды МГУ. Тренирует команду Виталий Бондаренко.

Результат российских команд в финале Чемпионата Мира, конечно, уступает результатам предыдущих лет, особенно с учётом того, что в 2004, 2006, 2008 и 2009 годах российские команды становились чемпионами мира (СПбГУ ИТМО в 2004,2008,2009 и Саратовский ГУ в 2006). Тем не менее, в Харбине россияне завоевали 5 медалей из 13 - одну золотую, три серебряных и одну бронзовую - больше, чем представители любой другой страны (у Китая одна золотая, одна серебряная и две бронзовых).

Пятое место заняла команда Петрозаводского Государственного Университета в составе Дениса Денисова, Алексея Николаевского и Ильи Николаевского. Эта команда уже участвовала в финале ACM ICPC в 2007 году в Токио, где заняла 13 место и завоевала бронзовые медали. В этом году команда выиграла полуфинал северо-восточного европейского региона (NEERC) и стала Чемпионом России. Денис Денисов в 2006 году участвовал в Международной олимпиаде школьников по информатике, где был награждён золотой медалью. Тренирует команду Денис Петрович Власов.
Отметим огромный вклад Петрозаводского Государственного Университета в подготовку команд-участниц Чемпионата Мира по программированию: в течение уже 9 лет в Петрозаводске организуются сборы для сильнейших российских - а теперь уже и зарубежных - команд. Интересно, что все чемпионы мира 2004,2006-2009 и чемпионы Европы 2004-2010 годов проходили подготовку на сборах в Петрозаводске. В этом году на конференции, проходящей одновременно с финалом, пользовался успехом совместный доклад представителей МГУ и ПетрГУ, посвящённый Открытому Кубку им. Е.В. Панкратьева и петрозаводским сборам. Так что в успехе всех команд-участниц сборов, а это все российские и украинские команды - призёры чемпионата - есть большая заслуга организаторов сборов - сотрудников ПетрГУ: В.А. Кузнецова, Д.П. Власова, ректора ПетрГУ А.В. Воронина, президента ПетрГУ В.Н. Васильева.

Седьмое место заняла команда Саратовского Государственного Университета в составе Натальи Бондаренко, Дмитрия Матова и Владимира Якунина. Для каждого из них это уже второй финал Чемпионата Мира: Наталья Бондаренко и Дмитрий Матов вместе со Станиславом Паком в прошлогоднем финале заняли 4 место и завоевали золотые медали. Кстати, эта же команда в сезоне 2008-2009 стала первой командой - чемпионом России, не представляющей вузы Москвы или Санкт-Петербурга. Владимир Якунин принимал участие в финале Чемпионата Мира в 2005 году в Шанхае.
Саратовская школа программирования имеет высокую репутацию, подтверждённую результатами в финалах Чемпионата Мира: в 2002 году дебют команды университета в финале Чемпионата Мира принёс ей серебряные медали и звание чемпионов Европы, в 2003 и 2007 году были вновь завоёваны серебряные медали, в 2009 - золотые, а в 2006 году команда СГУ стала победителем Чемпионата Мира. Достижения саратовцев внушительны и на школьном уровне: так, например, в 2008 году первые три места на Всероссийской олимпиаде школьников по информатике заняли ученики саратовских школ. Обеспечивает высокий уровень проведения соревнований созданный при Саратовском Государственном Университете центр олимпиадной подготовки программистов имени Н.Л. Андреевой, который работает как со школьниками, так и со студентами. Благодаря сотрудничеству с IT-компаниями, руководители которых сами в своё время представляли Саратов в олимпиадах по программированию, многие выпускники остаются работать в Саратове, участвуя по мере возможности в подготовке следующих поколений программистов. Так, например, тренером команды является чемпион Европы 2002 года, тренер чемпионов мира 2006 года Михаил Расихович Мирзаянов. А возглавляет центр доцент Саратовского ГУ Антонина Гавриловна Фёдорова.
Команда Санкт-Петербургского Государственного Университета в составе Дмитрия Антипова, Алексея Левина и Арсения Смирнова заняла девятое место и также была награждена серебряными медалями. Для Дмитрия это второй финал - первый был в 2005 году в Шанхае. В этом году команда заняла 3 место по результатам Открытого Кубка им. Е.В. Панкратьева, а также выиграла проводившийся во время сборов в Петрозаводске Кубок Главы Республики Карелия.
Тренер команды - Андрей Сергеевич Лопатин - будучи участником чемпионата мира по программированию, добился уникального результата, став в 2000 и 2001 годах двукратным чемпионом мира. Сейчас А.С. Лопатин не только руководит подготовкой студенческих команд, но и играет ключевую роль в проведении учебно-тренировочных сборов к Международным олимпиадам школьников по информатике, возглавляет команду России на этих олимпиадах.

Команда Уральского Государственного Университета в составе Ивана Бурмистрова, Дениса Дублённых и Евгения Курпилянского заняла 13 место и была удостоена бронзовых медалей. Команда стартовала не очень удачно, и перед последним часом соревнований занимала 44 место. Однако в последний час уральцы сдали 3 задачи и во второй раз в истории вуза стали призёрами Чемпионата Мира. Тренер команды - студент УрГУ Алексей Самсонов, в прошлом двукратный участник финалов Чемпионата Мира (2008, 2009).
Уральский Государственный Университет является центром спортивного программирования Урала. Командный Чемпионат Урала по программированию, который проводится с 1997 года, стал одним из первых региональных соревнований по программированию в России, архив задач с онлайн-проверкой acm.timus.ru активно используется многими командами и участниками при подготовке к соревнованиям. Сейчас УрГУ проводит также открытые личные студенческие турниры, открытый чемпионат УрГУ, а также - для школьников - региональную командную олимпиаду и вузовскую академическую олимпиаду. Возглавляет подготовку команд декан матмеха УрГУ Магаз Оразкимович Асанов. В частности, им был разработан рейтинг вузов по результатам полуфинальных и финальных соревнований Чемпионата Мира по программированию, использующийся уже 10 лет.

Результаты других команд, представлявших Россию и СНГ, таковы: Команды Белорусского Государственного Университета, Государственного Университета - Высшей Школы Экономики, Национального Технического Университета "Харьковский политехнический институт", Новосибирского Государственного Университета, Санкт-Петербургского Государственного Университета информационных технологий, механики и оптики и Самарского Государственного Аэрокосмического Университета решили по 5 задач и классифицированы на 14-35 местах. Команды Уфимского Государственного Авиационно-Технического университета и Ижевского Государственного Технического Университета решили по 4 задачи и классифицированы на 36-61 местах.

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

Чемпионаты мира по программированию: некоторые факты


По правилам чемпионата мира, в соревнованиях могут участвовать команды университетов, составленные из 3 участников. Каждый участник должен быть студентом или аспирантом соответствующего университета, при этом для одного человека запрещено выступление более, чем в двух финалах.
На время соревнований (обычно оно составляет пять часов) каждой команде из трёх участников предоставляется один компьютер с установленными на нём средствами разработки программ и выходом на систему автоматического (или полуавтоматического, как это принято в финале) тестирования. Для решения участникам обычно предлагается от 8 до 12 задач. Решением каждой задачи должна являться программа на одном из принятых на соревнованиях языков программирования (в этом году это Java, C, C++). Если команда считает, что решение готово, она направляет его на тестирование. Система проверки тестирует решение на заранее заданном автором задачи наборе тестов. Если на каком-то тесте программа некорректно завершилась, превысила заданное в условии задачи время работы на одном тесте, или дала неправильный ответ, команда получает краткое сообщение об ошибке. При этом сам тест, на котором произошла ошибка, команде не сообщается. Если же программа правильно отрабатывает на всех тестах, то задача команде засчитывается, кроме того, к "штрафному времени" прибавляется время от начала соревнований до момента сдачи задачи, а также по 20 минут за каждую неудачную отправку решения, сделанную по этой задаче. Побеждает команда, решившая больше всех задач, а если таких команд несколько, то команда, получившая среди них наименьшее "штрафное время".
Схема распределения медалей менялась из года в год, пока в последнее время не установился следующий вариант: места с 1 по 4 получают золотые медали, места с 5 по 8 - серебряные, места с 9 по 12 - бронзовые. Далее идут команды, решившие то же число задач, что и команда, занявшая 13 место, у которых в качестве места указано 13-е (то есть для этих команд "штрафное время" не учитывается, а в списке они расположены по алфавиту), потом - команды, решившие на одну задачу меньше, чем 13-е место (у них у всех также указано одно и то же место), и так до тех пор, пока количество команд, решивших данное или меньшее количество задач, составляет больше половины от всех участнков финала. Остальные команды получают Honorable Mention, то есть грамоту участника без указания места.
Однако в распределении медалей встречаются и исключения: в 2007, 2009 и 2010 году были присуждены дополнительные бронзовые медали за 13 место, так как отрыв 13 места от 12 был значительно меньше, чем отрыв 13 места от 14. Также в 2010 году команды, занявшее 8 и 9 место, показали идентичный результат и обе были награждены серебряными медалями.

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

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

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