SnarkNews on ACM ICPC Final-2012

 

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

Скачать в .html

Успех российских и белорусских команд на чемпионате Мира по программированию: новые рекорды.

В Варшаве (Польша) прошёл финал очередного, уже 36-го, командного студенческого Чемпионата Мира по программированию под эгидой ACM (Association for Computing Machinery). В отборочных турах чемпионата 2012 года стартовали более 8500 команд из 2219 университетов 85 стран мира, в финал были отобраны 112 команд.
По странам наибольшее представительство у США - 18 команд, 16 команд представляют Китай, 12 - Россию.

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

Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики после двухлетного перерыва вернул себе звание чемпионов мира и Европы. В составе команды - уже выигрывавший чемпионат мира Евгений Капун, а также впервые участвующие в финале Михаил Кевер и Нияз Нигматуллин. Команда была несомненным лидером сезона, выиграв в ноябре 2011 года полуфинал Чемпионата мира в Северо-Восточном полуфинальном регионе и став при этом чемпионом России, показав лучший результат на учебно-тренировочных сборах, проходивших зимой 2012 года в Петрозаводске, став лучшей из студенческих команд в очередном розыгрыше Открытого Кубка им. Е. В. Панкратьева по программированию (многоэтапном международном командном соревновании, состав участников которого не ограничен студенческими командами) и выиграв ряд региональных открытых турниров. Михаил Кевер также показал лучший результат среди российских участников в финале неофициального личного первенства мира - TopCoder Open-2011, который прошёл в октябре 2011 года в США. Для тренера команды - доцента Андрея Сергеевича Станкевича - это уже четвёртый победный финал - три предыдущих были в 2004 году в Праге (Чехия), в 2008 году в Банффе (Канада) и в 2009 году в Стокгольме (Швеция).
При этом СПб НИУ ИТМО играет ведущую роль в организации российских соревнований по программированию, в частности, Северо-Восточного Европейского полуфинала Чемпионата Мира по программированию (NEERC). Директором полуфинала является профессор СПб НИУ ИТМО Владимир Глебович Парфёнов, председателем жюри - сотрудник СПб НИУ ИТМО Роман Анатольевич Елизаров. За 16 прошедших полуфиналов уровень проведения соревнований и подготовки задач NEERC достиг - а во многом и превзошёл - уровень собственно финалов Чемпионата Мира. А с прошлого года компания Mail.Ru Group вместе с СПб НИУ ИТМО проводит крупнейший индивидуальный турнир по программированию для русскоязычных программистов - Russian Code Cup. В следующем году СПб НИУ ИТМО будет организатором финала Чемпионата Мира по программированию: 37-й финал будет проведён в Санкт-Петербурге.
Хозяев нынешнего финала - Варшавский университет - представляла очень сильная и опытная команда. В частности, в составе команды - абсолютный победитель Международной олимпиады школьников по информатике 2007 года Tomasz Kulczynski. Тем более, что на предыдущем Чемпионате Мира эта команда, от которой специалисты ожидали как минимум золотых медалей, осталась вообще без медалей. Свой последний шанс команда реализовала достойно, до последнего момента претендуя на чемпионство. Отставая от СПб НИУ ИТМО по штрафному времени, варшавская команда в последний момент попыталась сдать десятую задачу, но неудачно. Интересно, что у команд, занявших первые два места, набор решённых задач отличается при том, что две задачи из двенадцати не решила ни одна команда. Отметим, что команда Варшавского университета также принимала участие в сборах в Петрозаводске и также заняла там второе место после команды СПб НИУ ИТМО.
Третье место команды МФТИ в составе Рената Гимадеева, Якова Длугача и Павла Шишкина (тренер - Евгений Яковлевич Барский) является лучшим результатом вуза за всё время выступления в финалах Чемпионата мира. История её выступлений во многом похожа на историю выступлений команды Варшавского университета - отличное начало прошлого сезона, не особо удачный прошлый финал и реализованный второй шанс.
МФТИ участвует в организации и проведению соревнований по программированию уже давно: ещё в 2004 году в сотрудничестве с компанией "НИКС" были проведены личное студенческое первенство Москвы и турнир "НИКС Open", далее в течение нескольких лет проводились московские и межрегиональные соревнования (последнее соревнование серии на данный момент - турнир MIPT Open в 2011 году). Однако успех к командам МФТИ в соревнованиях по программированию пришёл в последние годы. Это закономерный результат осознанной политики руководства университета на развитие направления, связанного с информационными технологиями, на активную работу среди перспективных абитуриентов - победителей школьных соревнований по программированию, на привлечение высококлассных специалистов, в том числе и из российских регионов (например, многократных призёров соревнований по программированию Виталия Гольдштейна (Саратов) и Дмитрия Жукова (Орёл)), на взаимовыгодное сотрудничество с отечественными компаниями-разработчиками программного обеспечения, например, с Яндексом и ABBYY. Свою роль сыграла и организованная при участии МФТИ и МГУ на базе Яндекса единая система подготовки для московских команд - Яндекс.Тренировки, и регулярное проведение сборов на базе МФТИ для команд Московского региона перед полуфиналом Чемпионата Мира. Кстати, с лета 2012 года принято решение сделать эти сборы открытыми.
Четвёртое место, завоевав титул чемпионов Азии, заняла команда Шанхайского университета Жиатонг. Хотя состав этой команды был не настолько силён по именам, как в прошлые годы (команды университета становилась чемпионами мира в 2002, 2005 и 2010 годах), участникам из Шанхая удалось завоевать последнюю из золотых медалей, решив семь задач с наилучшим штрафным временем.

Российские команды завоевали чемпионский титул, золотую медаль за 3 место и бронзовую медаль за 10 место. В прошлом и позапрошлом годах россияне завоёвывали лишь по одной золотой медали (2 место и титул чемпионов Европы у команды МГУ в 2010 году и 4 место и титул чемпионов Европы у команды СПбГУ в 2011 году), чемпионами же становились представители Китая. Хотя в 2009 году российским командам удалось завоевать три золотых медали - за 1, 3 и 4 места.
Команды северо-восточной полуфинальной зоны (куда входят все постсоветские государства, кроме Украины и Молдовы) получили 5 медалей из 12.

Команда Белорусского государственного университета в составе Дмитрия Богданова, Юрия Писарчика и Сергея Соболя заняла пятое место и была награждена серебряными медалями. Двое из трёх участников команды уже выступали в финалах - Дмитрий Богданов участвовал в финале в 2010 году, Юрий Писарчик - в 2011. При этом и Дмитрий, и Юрий являются призёрами Международной олимпиады школьников по информатике - Дмитрий был удостоен золотой медали в 2009 году, Юрий - серебряной в 2008. Тренером команд БГУ является Владимир Михайлович Котов. Команда не очень удачно стартовала на турнире, однако в последней трети соревнований выправила ситуацию, сумев сдать три задачи. С учётом двенадцатого места и бронзовых медалей команды БГУИР, успех для белорусских команд значительный. Среди составляющих этого успеха хочется отметить массовость участия белорусских школьников в соревнованиях по информатике - например, школьные команды Беларуси составляют значительную часть команд, участвующих в школьных командных соревнованиях по программированию, школьники активно участвуют в соревнованиях, проводимых на базе проекта Codeforces. Интересно, что действующим трёхкратным абсолютным победителем Международной олимпиады школьников по информатике является одиннадцатиклассник из Гомеля Геннадий Короткевич, успешно участвующий уже во "взрослых" соревнованиях - второе место в рейтинг-листе TopCoder, первое место в рейтинг-листе Codeforces, призовые места в Открытом Кубке им. Е. В. Панкратьева - и это при том, что в последнем соревновании он в одиночку соревнуется с командами. Из прошлых успехов команд БГУ можно отметить третье место и золотые медали на Чемпионате Мира 2004 года; в составе команды тогда выступал, в частности, Иван Метельский, ныне отвечающий за подготовку задач в соревнованиях TopCoder.

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

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

Результаты других команд, представлявших Россию и СНГ, таковы:
Команда Саратовского государственного университета решила 6 задач и заняла 13 место, команда Казахско-Британского технического университета решила 6 задач и заняла 16 место (это лучший результат за всё время выступления команд Казахстана в финалах ACM ICPC), команда Нижегородского ГУ решила 5 задач и заняла 18 место, команда НТУ "Харьковский ПИ" решила 5 задач и заняла 21 место, команда СПбГУ решила 5 задач и заняла 23 место, команда U of Latvia решила 5 задач и заняла 28 место, команда Уральского федерального университета решила 5 задач и заняла 29 место, команда Волгоградского ГТУ решила 4 задачи и заняла 40 место, команда Таврического НУ решила 4 задачи и заняла 41 место, команда Томского ГУ решила 4 задач и заняла 60 место. Команды Уфимского ГАТУ и Алтайского ГТУ решили по 3 задачи, команда Удмуртского ГУ решила 2 задачи.

Чемпионаты мира по программированию по версии ACM проводятся, начиная с 1977 года, по многоуровневой системе (сначала отборочные соревнования, затем финальные). С 1977 по 1985 год в соревнованиях участвовали только североамериканские команды. Первой командой не из Северной Америки, принявшей участие в соревнованиях, была команда из Новой Зеландии, участвовавшая в 1986 году. После того, как руководство чемпионатом переместилось в Университет Бэйлор, Сан-Антонио, а директором соревнований стал Билл Пучер, возглавляющий чемпионат и по сей день, в соревнованиях стали принимать участие всё большее число команд из-за пределов Северной Америки, и с 1991 года соревнования получают статус чемпионата мира по программированию, а победитель объявляется Чемпионом Мира. Финальные соревнования проводятся в разных странах и городах: например, в 2011 году финальная часть соревнований проходила в США (Орландо), в 2010 - в Китае (Харбин), в 2009 году в Швеции (Стокгольм), в 2008 году финальная часть соревнований проходила в Канаде, в 2007 - в Японии (Токио), в 2006 - в США (Сан-Антонио, Техас), в 2005 году - в Китае (Шанхай), в 2004 году - в Чехии (Прага). Но чаще всего - 27 раз из 36 - финалы проводились в США. Генеральным спонсором соревнований с сезона 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 проходил одновременно в Барнауле, Тбилиси, Санкт-Петербурге и Ташкенте, а квота от региона на финал составила 16 команд.

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

.