SnarkNews on ACM ICPC Final-2014

 

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

Скачать в .html

Санкт-Петербургский и Московский университеты занимают первые два места на Чемпионате Мира по программированию!

В Екатеринбурге прошёл финал очередного, уже 38-го, командного студенческого Чемпионата Мира по программированию под эгидой ACM (Association for Computing Machinery) - старейшего и самого престижного студенческого интеллектуального соревнования в мире. В отборочных турах чемпионата 2014 года стартовала 10681 команда из 2286 университетов 94 стран мира, в финал были отобраны 122 команды.
По странам наибольшее представительство у США - 19 команд, 16 команд представляют китайские вузы, 11 - российские.

Результаты финала таковы:

  • Чемпионом мира и Европы стала команда Санкт-Петербургского государственного университета, решившая 7 из 12 предложенных задач.
    В составе команды - студенты матмеха СПбГУ Дмитрий Егоров, Павел Кунявский и Егор Суворов (тренер команды - Андрей Сергеевич Лопатин), Для СПбГУ это третий титул чемпиона мира и Европы. Больше только у Университета ИТМО - 5. Отметим, что это третья подряд победа российских команд в финалах Чемпионата Мира (в 2012 и 2013 выигрывал Университет ИТМО), что является абсолютным рекордом среди всех стран с момента, как финалы ACM ICPC получили статус финалов Чемпионата Мира.
  • Второе место и золотые медали завоевала команда Московского государственного университета, также решившая 7 из 12 предложенных задач, но уступившая по второму параметру - штрафному времени.
    В составе команды - Глеб Евстропов, Михаил Пядёркин и Виктор Омельяненко (тренер команды - Антон Евгеньевич Панкратьев).

    Таким образом, российские команды завоевали первые два места, сделав своеобразный "золотой дубль". До этого подобное достижение удавалось только университетам США в 1995 и в 1997 годах. Победители соревнований получили поздравления от Председателя Правительства Российской Федерации Дмитрия Анатольевича Медведева.

  • Третье место и золотые медали у команды Пекинского университета (Китай), ставшей чемпионом Азии.
  • Четвёртое место и золотые медали у команды Национального Университета Тайваня.
  • Обе эти команды решили по шесть задач.
Серебряными медалями награждены:
  • занявшая пятое место команда Варшавского университета (Польша);
  • занявшая шестое место команда Шанхайского Университета Цзяотун (Китай);
  • занявшая седьмое место команда Токийского Университета (Япония);
  • занявшая восьмое место команда Загребского университета (Хорватия).
  • Все эти команды решили по 5 задач.
Бронзовыми медалями награждены:
  • занявшая девятое место команда Санкт-Петебургского национального исследовательского университета информационных технологий, механики и оптики, решившая 5 задач;
  • занявшая десятое место команда московского Национального исследовательского университета - Высшей школы экономики;
  • занявшая одиннадцатое место команда Университета Циньхуа (Китай);
  • занявшая двенадцатое место команда Университета имени Амоса Коменского (Словакия),
  • Команды, занявшие места с 10 по 12, решили по 4 задачи.

Это второй за всю историю финал Чемпионата Мира, проходивший в России: в прошлом году финал Чемпионата Мира принимал Санкт-Петербург. Финал был организован на очень высоком уровне: участники и гости соревнований были поселены в лучших отелях города, соревнования проходили во Дворце игровых видов спорта, с трибуны которого зрители могли наблюдать за тем, как команды решают задачи, церемонии открытия и закрытия проходили в киноконцертном театре "Космос". Основным организатором финала с российской стороны был Уральский Федеральный университет, основным партнёром с российской стороны - компания СКБ "Контур". Организация соревнований заслужила высокие оценки как от участников финала, так и от исполнительного директора ACM ICPC Билла Паучера.

Команда Санкт-Петербургского государственного университета по оценкам экспертов была одним из фаворитов соревнований. Во-первых, команда участвовала в том же составе в прошлом финале, заняла пятое место и была награждена серебряными медалями. Во-вторых, в этом сезоне команда СПбГУ одержала уверенные победы практически во всех крупных очных соревнованиях и заняла второе место в общем зачёте (и первое среди всех команд, участвующих в нынешнем финале ACM ICPC) XIV Открытого Кубка им. Е.В. Панкратьева по программированию. Однако победа не далась легко: специфика задач финала оказалась такой, что все команды-фавориты не показали ожидаемого результата; так, например, команда Шанхайского университета Цзяотун, в составе которой были два золотых медалиста финалов прошлых лет, заняла только шестое место, команда Университета Циньхуа, в составе которой был действующий победитель Международной олимпиады школьников по информатике - только одиннадцатое. Хотя команда СПбГУ стартовала очень уверенно и быстро вышла на первое место с четырьмя решёнными задачами, за час до окончания тура команда СПбГУ была только второй с теми же четырьмя решёнными задачами, отставая от лидера - команды МГУ - на 2 задачи. Однако за 45 минут до завершения соревнований команда СПбГУ сдала пятую задачу, за 14 минут до завершения соревнований - шестую и вышла вперёд по штрафному времени. Команда МГУ за 10 минут до завершения соревнований сдала седьмую задачу и вновь вышла на первое место, и только за две минуты до завершения соревнований команда СПбГУ сдала свою седьмую задачу, вышла вперёд по штрафному времени и стала Чемпионом Мира.
Все три участника команды имели опыт выступления в Международных олимпиадах школьников по информатике; более того, все они участвовали в Международной олимпиаде школьников 2011 года по информатике. Тогда Павел Кунявский был награждён золотой медалью, разделив третье место в абсолютном зачёте, Дмитрий Егоров и Егор Суворов были награждены серебряными медалями. Кроме этого, Дмитрий Егоров в том же 2011 году участвовал в Международной олимпиаде школьников по математике, где также был награждён серебряной медалью, Егор Суворов участвовал в Международной олимпиаде школьников по информатике 2012 года, заняв пятое место и завоевав золотую медаль. Интересно, что в 2011 году Дмитрий Егоров стал победителем Всероссийской олимпиады школьников по информатике, Егор Суворов занял второе место, а Павел Кунявский - третье. Если Егор и Дмитрий являются выпускниками школ Санкт-Петербурга, то Павел приехал в Санкт-Петербург из Саратова, и, будучи школьником, тренировался в центре подготовки олимпиадных программистов имени Н. Л. Андреевой при Саратовском ГУ.
Командам Санкт-Петербургского государственного университета принадлежит много исторических достижений в финалах Чемпионата Мира - в 1997 году команда СПбГУ заняла 8 место и стала первым российским призёром финала Чемпионата Мира, в 1998 году команда СПбГУ заняла второе место и стала первой российской командой, вошедшей в первую тройку, в 2000 году команда СПбГУ стала первым российским Чемпионом Мира. Всего СПбГУ участвовал в 17 финалах.
Тренер команды этого года - Андрей Сергеевич Лопатин - был участником команды СПбГУ, выигравшей два Чемпионата Мира в 2000 и 2001 годах и вместе с Николаем Дуровым стал первым в истории Чемпионатов Мира двукратным Чемпионом Мира по программированию. В дальнейшем они стали одними из создателей "ВКонтакте": долгое время Николай Дуров был техническим директором проекта, а Андрей Лопатин - его заместителем. При этом Андрей продолжал заниматься и тренерской работой. И вот сейчас он привёл команду к победе как тренер. Таким образом, Андрей причастен ко всем победам СПбГУ в финалах Чемпионата Мира. До недавнего времени Андрей также был тренером сборной России на Международной олимпиаде школьников по информатике и активно участвовал в организации подготовительных сборов; сейчас же подготовкой сборной России занимаются его ученики, в том числе Павел Кунявский и Егор Суворов. Поддержку команде обеспечивают такие компании, как "Вконтакте" и "Telegram".

Для занявшей второе место команды Московского государственного университета в составе студента ВМК МГУ Глеба Евстропова и студентов мехмата МГУ Виктора Омельяненко и Михаила Пядёркина это первый финал Чемпионата Мира. В этом сезоне команда отобралась в финал со второго места, проиграв только команде СПбГУ; в XIV Открытом Кубке им. Е.В. Панкратьева команда заняла четвёртое место в общем зачёте (и второе среди команд, участвующих в нынешнем финале). Кроме золотых медалей за второе место, команда МГУ получила два приза, вручаемых за первое правильное решение какой-либо задачи; даже у победителей - команды СПбГУ - всего один такой приз.
Интересно, что у команд МГУ и СПбГУ есть много общего. Глеб и Михаил в 2010 году одновременно участвовали в Международной олимпиаде школьников по информатике, Михаил выиграл золотую медаль, а Глеб серебряную. В команде тоже есть призёр Международных олимпиад школьников по математике: будучи белгородским школьником, Виктор Омельяненко завоевал две золотые медали на IMO: в 2009 году занял четвёртое место, в 2010 - седьмое. Если в команде СПбГУ Дмитрий Егоров и Егор Суворов в школе учились в СПб, то в команде МГУ двое - Глеб Евстропов и Михаил Пядёркин - являются выпускниками московского СУНЦ при МГУ. Участники команды МГУ также активно работают со школьной сборной России на учебно-тренировочных сборах.
МГУ, наряду с Университетом ИТМО, был первым российским университетом, принимавшим участие в Чемпионатах Мира по программированию. Эти два университета участвуют во всех финалах, начиная с 1995 года. И начиная с 1995 года, подготовку команд МГУ возглавлял ведущий научный сотрудник мехмата МГУ Евгений Васильевич Панкратьев. Под его руководством команды МГУ дважды - в 2003 и 2005 годах - становились вице-чемпионами мира, а в 2002, 2006, 2007 годах - завоёвывали бронзовые медали. Также по инициативе и при активном участии Е. В. Панкратьева МГУ в сотрудничестве с российскими IT-компаниями организовал Открытый Кубок по программированию - регулярное многоэтапное соревнование, в котором в настоящий момент участвуют команды со всего мира, при этом большинство команд представляют Россию и другие страны бывшего СССР; также в последнее время активное участие в Кубке принимают китайские вузы. После трагической гибели Евгения Васильевича в январе 2008 года Открытому Кубку было присвоено его имя. Подготовку команд мехмата МГУ возглавил его сын - доцент МГУ Антон Евгеньевич Панкратьев, который достойно продолжил дело отца: в 2008 году команда МГУ завоевала серебряные медали, в 2010 стала вице-чемпионом мира и чемпионом Европы, в 2011-2013 завоевала бронзовые медали. И вот снова золотые медали и четвёртое в истории МГУ второе место. Символично, что как Евгений Васильевич, так и Антон Евгеньевич Панкратьевы отмечены Coach Award - премией, которая вручается тренеру, 5 раз выводившему команду в финалы Чемпионата Мира, при этом удостоенный этой награды в текущем году Антон Евгеньевич является первым её лауреатом, команды которого все 5 раз завоёвывали медали Чемпионата Мира.
В подготовке московских команд к финалу Чемпионата Мира большую роль сыграл стартовавший в 2011 году проект Яндекс.Тренировки, организованный компанией "Яндекс". Используя как собственную систему Яндекс.Контест, так и совместный тренировочный проект МГУ и СПбГУ, тренеры Яндекс.Тренировок, - призёры Чемпионатов Мира по программированию прошлых лет из команд МГУ и МФТИ, по сути, создали централизованную систему тренировок для московских вузов.

Девятое место завоевала команда Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики в составе Адама Бардашевича, Артёма Васильева и Бориса Минаева.
Команда полностью поменяла свой состав после того, как университет два раза подряд выиграл звание чемпионов мира и Европы: Евгений Капун, Нияз Нигматуллин и Михаил Кевер стали двукратными чемпионами мира (первый участвовал в финалах 2009 и 2012, двое других - в финалах 2012 и 2013); ещё один чемпион мира 2013 года - трёхкратный абсолютный победитель Международных олимпиад школьников по информатике Геннадий Короткевич - имеет возможность выступить ещё в одном финале Чемпионата мира, но было принято решение о том, что этот сезон соревнований серии ACM ICPC он пропустит. Университет ИТМО является самым титулованным за всю историю Чемпионатов Мира вузом: 10 золотых медалей (из них 5 чемпионств мира), одна серебряная и вот - первая бронзовая медаль.
Отметим, что Университет ИТМО играет ведущую роль в организации российских соревнований по программированию, в частности, Северо-Восточного Европейского полуфинала Чемпионата Мира по программированию (NEERC). Директором полуфинала является профессор Университета ИТМО Владимир Глебович Парфёнов, председателем жюри - сотрудник Университета ИТМО Роман Анатольевич Елизаров. За 18 прошедших полуфиналов уровень проведения соревнований и подготовки задач NEERC достиг - а во многом и превзошёл - уровень собственно финалов Чемпионата Мира. В 2013 году Университет ИТМО был организатором первого финала Чемпионата Мира по программированию, проходившего на территории России. С 2011 года компания "Mail.Ru Group" вместе с Университетом ИТМО проводит крупнейший индивидуальный турнир по программированию для русскоязычных программистов - Russian Code Cup.

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

Результаты других команд, представлявших Россию и Северо-Восточный полуфинальный регион, таковы:

  • Команда Белорусского государственного университета (Беларусь) решила 4 задачи и заняла 14 место.
  • По 3 задачи решили команды Международного Университета информационных технологий (Казахстан) - 20 место, Национального исследовательского технологического университета "МИСиС" - 25 место, Новосибирского ГУ - 29 место, Kaunas TU (Литва) - 30 место, Ижевского ГТУ - 32 место, Ташкентского филиала МГУ - 37 место.
  • По 2 задачи решили команды Петрозаводского ГУ, Саратовского ГУ, МФТИ, Уральского ФУ, U of Latvia (Латвия) и Университета Назарбаева (Казахстан).
Отметим, что в этом году набор задач был сложнее, чем обычно, и дипломами с указанием мест награждались все команды, решившие две и более задачи, таким образом, все команды нашего полуфинального региона получили дипломы с указанием места.
Также стоит отметить, что команда Ташкентского филиала МГУ стала первой командой, представляющей Узбекистан в финалах Чемпионата Мира. При этом команда показала достойный результат, попав в группу команд, получивших диплом за 19-44 места.

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

  • в 2013 году финальная часть соревнований проходила в России, в Санкт-Петербурге;
  • в 2012 - в Польше (Варшава);
  • в 2011 году - в США (Орландо);
  • в 2010 - в Китае (Харбин);
  • в 2009 году - в Швеции (Стокгольм);
  • в 2008 году - в Канаде (Банфф, Альберта);
  • в 2007 - в Японии (Токио);
  • в 2006 - в США (Сан-Антонио, Техас);
  • в 2005 году - в Китае (Шанхай)
  • в 2004 году - в Чехии (Прага)
Чаще всего - 27 раз из 38 - финалы проводились в США. При этом Россия стала первой страной после США, в которой финалы проводились два раза подряд. Генеральным спонсором соревнований с сезона 1997-1998 года является компания IBM.

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


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

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

Однако в распределении медалей встречаются и исключения: в 2007, 2009, 2010 и 2013 году были присуждены дополнительные бронзовые медали за 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 проходил одновременно в Барнауле, Тбилиси, Санкт-Петербурге и Ташкенте, а квота от региона на финал составила 17 команд.

В прошедшие годы команды из северо-восточной полуфинальной группы и особенно - из России показывали высокие результаты в финалах:

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