SnarkNews on ACM ICPC Final-2009

 

Бета-версия пресс-релиза. Замечания и предложения отправлять на new.opencup(собака)gmail(тoчка)com.

Скачать в .html

Новый российский рекорд на чемпионате мира по программированию!

В Стокгольме (Швеция) прошёл финал очередного, уже 33-го, командного Чемпионата Мира по программированию под эгидой ACM (Association of Computing Machinery). В отборочных турах чемпионата 2009 года стартовали 7109 команд из 1838 университетов 88 стран мира, в финал были отобраны 100 команд.
По странам наибольшее представительство у США - 21 команда, 16 команд представляют Китай, 8 - Россию.

Чемпионом мира и Европы стала команда Санкт-Петербургского университета информационных технологий, механики и оптики в составе Владислава Исенбаева, Максима Буздалова и Евгения Капуна (тренер команды - Андрей Сергеевич Станкевич), решившая 9 из 11 предложенных задач. Для СПбГУ ИТМО это третий титул чемпиона мира и Европы, что является рекордом среди всех вузов, участвовавших в Чемпионатах Мира по программированию. Также золотые медали получили: занявшая второе место и ставшая чемпионом Азии команда Университета Синьхуа (Китай), занявшая третье место команда Санкт-Петербургского Государственного Университета и занявшая четвёртое место команда Саратовского Государственного Университета.
Серебряными медалями награждены занявшая пятое место команда Оксфордского университета (Великобритания), занявшая шестое место команда университета Чжэцзян (Китай), занявшая седьмое место команда Массачусеттского Технологического Института (США), ставшая также чемпионом Северной Америки, и занявшая восьмое место команда Алтайского Государственного Технического Университета.
Команды Варшавского Университета (Польша), Университета Ватерлоо (Канада), Тбилисского государственного университета (Грузия), Университета Карнеги-Меллон (США) и Южно-Китайского технологического университета (Китай) заняли места с 9 по 13 соответственно и были награждены бронзовыми медалями.

Санкт-Петербургский государственный университет информационных технологий, механики и оптики защитил завоёванное в прошлом году звание чемпионов мира и Европы, несмотря на то, что состав команды полностью сменился. В этом году чемпионами стали Владислав Исенбаев, Максим Буздалов и Евгений Капун. Весь сезон команда выступала довольно успешно, показав лучший результат на учебно-тренировочных сборах перед финалом и выиграв ряд региональных открытых турниров. Владислав Исенбаев также вышел в финал неофициального личного первенства мира - TopCoder Open-2009, который состоится летом этого года в США. Для тренера команды - доцента Андрея Сергеевича Станкевича - это уже третий победный финал - два предыдущих были в 2004 году в Праге (Чехия) и в 2008 году в Банффе (Канада). При этом СПбГУ ИТМО играет ведущую роль в организации российских соревнований по программированию, в частности, Северо-Восточного Европейского полуфинала Чемпионата Мира по программированию (NEERC). Директором полуфинала является профессор СПбГУ ИТМО Владимир Глебович Парфёнов, председателем жюри - сотрудник СПбГУ ИТМО Роман Анатольевич Елизаров. За 13 прошедших полуфиналов уровень проведения соревнований и подготовки задач NEERC достиг - а во многом и превзошёл - уровень собственно финалов Чемпионата Мира. И закономерно, что перед финалом Чемпионата Мира В.Г. Парфёнов, Р.А. Елизаров, а также ректор СПбГУ ИТМО профессор Владимир Николаевич Васильев были по решению организаторов финала награждены почётной премией DeBlasi Award за значительный вклад в проведение и организацию соревнований. Так что победы студентов СПбГУ ИТМО базируются на прочном фундаменте. Интересно, что команды СПбГУ ИТМО завоёвывали золотые медали в течение 7 из 9 последних лет (в 2004, 2008 и 2009 - чемпионы мира, в 2001, 2003, 2005 и 2007 - третье место), что также является уникальным достижением.
Университет Синьхуа, команда которого заняла второе место, собрал очень сильный состав. Достаточно заметить, что среди участников команды был нынешний лидер мирового индивидуального рейтинга спортивного программирования по результатам соревнований компании TopCoder, организующей наиболее авторитетные индивидуальные соревнования по спортивному программированию. Перед стартом соревнований именно команда Университета Синьхуа считалась фаворитом. Однако, ликвидировав за последний час отставание на две задачи от команды СПбГУ ИТМО, китайские студенты всё равно проиграли победителям за счёт худшего времени.
Занявшая третье место команда СПбГУ в составе Сергея Копелиовича, Олега Давыдова и Юрия Петрова практически всё время соревнований лидировала или шла на втором месте после команды СПбГУ ИТМО. К сожалению, команда СПбГУ в последний час сдала две задачи против трёх у команды Синьхуа, которая и вышла на второе место с перевесом в одну задачу. Учитывая достижения участников команды - выход в финал TopCoder Open-2008, а также золотые медали Международной олимпиады школьников по информатике 2005 и 2006 года для Сергея Копелиовича, титул победителя TopCoder High School Tournament - 2007 (чемпионата мира по программированию среди школьников, проводимого компанией TopCoder) у Юрия Петрова, "золото" надо признать закономерным результатом для этой команды. Отметим, что в прошлом году команда также рассматривалась как фаворит чемпионата, тем не менее заняла лишь 11-е место, получив бронзовые медали. Так что - учитывая, что правила Чемпионата Мира запрещают одному человеку участвовать в финале более двух раз - команда реализовала последнюю возможность занять высокое место в финале Чемпионата Мира.
Тренер команды - Андрей Сергеевич Лопатин - будучи участником чемпионата мира по программированию, добился уникального результата, став в 2000 и 2001 годах двукратным чемпионом мира. Сейчас А.С. Лопатин не только руководит подготовкой студенческих команд, но и играет ключевую роль в проведении учебно-тренировочных сборов к Международным олимпиадам школьников по информатике, возглавляет команду России на этих олимпиадах.
Четвёртое место заняла команда Саратовского Государственного Университета, в которую входили Наталья Бондаренко, Дмитрий Матов и Станислав Пак. В ноябре 2008 года эта команда выиграла полуфинал Чемпионата Мира, одновременно завоевав звание чемпиона России. Впервые за все 13 лет проведения чемпионата победа досталась команде не из Москвы или Санкт-Петербурга. При этом саратовская школа программирования имеет высокую репутацию, подтверждённую результатами в финалах Чемпионата Мира: в 2002 году дебют команды университета в финале Чемпионата Мира принёс ей серебряные медали и звание чемпионов Европы, в 2003 и 2007 году были вновь завоёваны серебряные медали, а в 2006 году команда СГУ стала победителем Чемпионата Мира. Достижения саратовцев внушительны и на школьном уровне: так, например, в 2008 году первые три места на Всероссийской олимпиаде школьников по информатике заняли ученики саратовских школ. Обеспечивает высокий уровень проведения соревнований созданный при Саратовском Государственном Университете центр олимпиадной подготовки программистов имени Н.Л. Андреевой, который работает как со школьниками, так и со студентами. Благодаря сотрудничеству с IT-компаниями, руководители которых сами в своё время представляли Саратов в олимпиадах по программированию, многие выпускники остаются работать в Саратове, участвуя по мере возможности в подготовке следующих поколений программистов. Так, например, тренером команды является чемпион Европы 2002 года, тренер чемпионов мира 2006 года Михаил Расихович Мирзаянов. А возглавляет центр доцент Саратовского ГУ Антонина Гавриловна Фёдорова.

Российские команды улучшили показанный в 2008 году результат в финале чемпионата мира, завоевав чемпионский титул, три золотые и одну серебряную медаль: до этого более 2 золотых медалей российским участникам завоевать не удавалось. Команды северо-восточной полуфинальной зоны (куда входят все постсоветские государства, кроме Украины и Молдовы) получили 5 медалей из 12.
Во время финала также была проведена конференция, на которой большим успехом пользовался доклад представителей Петрозаводского Государственного Университета о проводящихся в течение немногим менее 10 лет в Петрозаводске сборах для сильнейших российских - а теперь уже и зарубежных - команд. Так что в успехе всех команд-участниц сборов, а это и чемпионы мира - команда Санкт-Петербургского государственного университета информационных технологий, механики и оптики, и все российские команды - призёры чемпионата - есть большая заслуга организаторов сборов.

Занявшая восьмое место и награждённая серебряными медалями команда Алтайского ГТУ в составе Андрея Акиньшина, Алексея Избышева и Максима Колосовского подтвердила неслучайность высоких результатов команд Сибири на чемпионатах мира по программированию: в 2006 году команда Алтайского ГТУ заняла 3 место и была награждена золотыми медалями, в 2007 году команда Новосибирского ГУ заняла 5 место и была награждена серебряными медалями. При этом Алтайский ГТУ является одним из центров проведения школьных и студенческих соревнований по программированию. Соревнования Северо-Восточного Европейского полуфинала для команд Сибири и Дальнего Востока проводятся именно в Барнауле. Директором полуфинала для сибирской группы вузов является тренер команды Алтайского ГТУ Елена Николаевна Крючкова. Стабильно высокие результаты показывают и барнаульские школьники.

Кроме России, Северо-Восточный Европейский полуфинальная зона включает в себя и другие страны бывшего СССР (кроме Украины и Молдовы). Для команд Южного Кавказа полуфинальные соревнования организовываются в Батуми. Несмотря на политические проблемы, руководство батумского полуфинала, и в первую очередь директор полуфинала, президент Ассоциации поддержки программирования, тренер команд Тбилисского Государственного Университета Теодоре Ясонович Заркуа, делают всё от них зависящее для сохранения наработанных связей с коллегами из России и других стран бывшего СССР. В Батуми и Новосибирске уже третий год организуется Кубок памяти выдающегося математика академика Ильи Несторовича Векуа, при этом в прошлом году Кубок проводился также в Москве и Санкт-Петербурге. Команда Тбилисского Государственного Университета в составе Николоза Джимшелеишвили, Гиорги Леквеишвили и Эльдара Богданова проходила подготовку к финалу, в частности, в рамках интернет-зеркала учебно-тренировочных сборов команд России и СНГ, проводимых в Петрозаводске. "Зеркало" организовано для российских и зарубежных команд в МГУ на сервере Открытого Кубка им. Е.В. Панкратьева - крупнейшего регулярного многоэтапного соревнования по программированию, в котором принимают участие сильнейшие команды не только практически из всех стран бывшего СССР, но и из некоторых стран Восточной Европы. При этом координатором "зеркала" по работе с регионами и отдельными командами является Т.Я. Заркуа. Так что "бронзовый" дебют команды Тбилисского ГУ является несомненно позитивным моментом - и отличным подтверждением того факта, что равноправное сотрудничество педагогических и научных коллективов приводит к закономерным успехам.

Результаты других команд, представлявших Россию и СНГ, таковы:
Команда Московского государственного университета решила 6 задач и заняла 17 место, команды Новосибирского государственного университета, Уральского государственного университета и Таврического национального университета им. Вернадского (Украина) решили по 5 задач и заняли соответственно 21, 22 и 32 место, команды НТУУ "Киевский Политехнический Институт" (Украина), Белорусского Государственного Университета (Беларусь) и Киевского Национального Университета (Украина) решили по 4 задачи и заняли соответственно 37, 38 и 39 место, команда Южно-Уральского государственного университета решила 3 задачи и заняла 54 место.

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

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


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

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

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

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