Pull to refresh

Триумф российских команд на чемпионате мира по программированию ACM ICPC

Reading time12 min
Views5.8K
В городе Банфф (Канада, Альберта) прошёл финал очередного, уже 32-го, командного Чемпионата Мира по программированию под эгидой ACM (Association of Computing Machinery). В отборочных турах чемпионата 2008 года стартовали 6 700 команд из 1821 университетов 83 стран мира, в финал были отобраны 100 команд.

По странам наибольшее представительство у США — 20 команд, 15 команд представляют Китай, 11 — Россию.

Чемпионом мира и Европы стала команда Санкт-Петербургского университета информационных технологий, механики и оптики в составе Дмитрия Абдрашитова, Дмитрия Паращенко и Фёдора Царёва (тренер команды — Андрей Сергеевич Станкевич), решившая 8 из 11 предложенных задач.



Также золотые медали получили: занявшая второе место и ставшая чемпионом Северной Америки команда Массачусетского технологического института (США), занявшая третье место команда Ижевского государственного технического университета и занявшая четвёртое место команда Львовского Национального Университета им. Ивана Франка.

Серебряными медалями награждены занявшая пятое место команда Московского государственного университета им. Ломоносова, занявшая шестое место команда Университета Синьхуа (Китай), ставшая также чемпионом Азии, занявшая седьмое место команда Стэнфордского университета (США) и занявшая восьмое место команда Загребского Университета (Хорватия).
Команды Университета Ватерлоо (Канада), Петрозаводского государственного универстета, Санкт-Петербургского государственного университета и Белорусского государственного университета заняли места с 9 по 12 соответственно и были награждены бронзовыми медалями.

Новые чемпионы мира и Европы — команда Санкт-Петербургского государственного университета информационных технологий, механики и оптики — входили в десятку лучших команд Северо-Восточного полуфинала Чемпионата Мира по программированию ещё в 2005 и 2006 годах, занимая соответственно 10 и 7 места, однако из-за того, что правилами Чемпионата Мира не допускается участие в финале двух команд, представляющих один вуз, в финал выходила другая команда СПбГУ ИТМО, занимавшая оба раза в полуфинале второе место. В этом году команда в составе Дмитрия Абдрашитова, Дмитрия Паращенко и Фёдора Царёва в полуфинале не оставила шансов конкурентам, заняв первое место и вернув СПбГУ ИТМО звание чемпиона России — в 2005 и 2006 годах чемпионами России была команда МГУ. После победы команда продолжала упорно работать, заняла третье место в IV Открытом Кубке по программированию памяти Е.В. Панкратьева, показывала стабильно высокие результаты на регулярно организуемых в СПб ГУ ИТМО открытых тренировках — и в результате дебют в финале чемпионата мира оказался победным. Таким образом, после годичного перерыва титул чемпионов Мира и Европы снова завоевала российская команда.
Тренером команды, лауреатом премии Президента Российской Федерации Андреем Сергеевичем Станкевичем, была проделана большая работа по подготовке команды к финалу, и это дало свои результаты. При этом в открытых тренировках СПбГУ ИТМО, проводимых через Интернет, участвовали и другие российские команды-финалисты. Интересно, что команды СПбГУ ИТМО завоёвывали золотые медали в течение 6 из 8 последних лет (в 2004 и 2008 — чемпионы мира, в 2001, 2003, 2005 и 2007 — третье место), что является уникальным достижением. Возглавляет созданную в СПбГУ ИТМО систему подготовки программистов лауреат премии Президента Российской Федерации, профессор Владимир Глебович Парфёнов, являющийся директором Северо-Восточной полуфинальной зоны чемпионата мира.

Команда Массачусетского технологического института третий год подряд становится чемпионом Северной Америки. В прошлом году команда завоевала 4 место и золотые медали, в этом году, несмотря на смену состава команды (по правилам Чемпионата Мира участие в более, чем двух финалах невозможно), MIT сумел улучшить свой результат. А в следующем году американская команда, которая может сохранить свой состав, будет одним из претендентов на победу в чемпионате мира.

В занявшей третье место команде Ижевского государственного технического университета Евгений Кузяков и Виктор Камашев являются дебютантами финала, а для Александра Скиданова это уже второй финал — в 2005 году Александр участвовал в финале в составе команды ИжГТУ, занявшей 9 место и награждённой бронзовыми медалями. В этом составе команда заняла второе место в Северо-Восточном полуфинале чемпионата мира 2007 года, став вице-чемпионами России. Вообще, выступления команд Ижевского ГТУ в финалах Чемпионатов Мира являются уникальными: все три раза команда была награждена медалями: серебряными в 2004 году, бронзовыми в 2005 и вот сейчас — третье место и золотые медали. Руководит подготовкой команд Ижевского ГТУ доцент Владимир Георгиевич Тарасов, являющийся также крупным организатором соревнований по программированию в регионе: в частности, зимой 2008 года в Ижевске под его руководством была проведена школа-семинар по программированию, в которой участвовали около 30 команд, представляющих как Уральский регион, так и, например, Москву, Архангельск, Ростов или Таганрог. И подобного рода школы руководство ИжГТУ планирует сделать ежегодными.

Команда Львовского национального университета им. Ивана Франка в составе Василя Билецкого, Остапа Коркуны и Руслана Бабили стала первой украинской командой, завоевавшей в финале чемпионата мира по программированию золотые медали. Украина, наряду с Молдовой, участвует не в Северо-Восточном полуфинале (как остальные постсоветские государства), а в Юго-Восточном. В этом сезоне первые три места в Юго-Восточном полуфинале чемпионата мира заняли украинские команды, а команда Львовского НУ решила все 9 предложенных задач за 2 часа из отведённых 5, установив тем самым своеобразный рекорд полуфиналов. И вот подтверждением показанного в полуфинале высокого класса команды стало отличное выступление в финале и золотая медаль чемпионата мира. Кстати, от третьего места команду Львовского НУ отделили всего 2 минуты.

Российские команды в целом показали выдающийся результат в финале чемпионата мира, завоевав чемпионский титул, две золотые, одну серебряную и две бронзовые медали. Команды северо-восточной полуфинальной зоны (куда входят все постсоветские государства, кроме Украины и Молдовы) получили ровно половину всех присуждавшихся медалей (6 из 12), что само по себе является рекордным достижением. По предложению присутствовавшего на финале Президента Петрозаводского ГУ В.Н.Васильева достижения российских команд в чемпионате мира 2008 года решено посвятить памяти одного из основоположников российских соревнований по программированию, старейшего тренера студенческих команд России, основателя и директора Открытого Кубка по программированию, тренера и руководителя команд МГУ Евгения Васильевича Панкратьева, трагически погибшего в январе 2008 года.

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

Команда Петрозаводского Государственного Университета в составе Вячеслава Медведева, Максима Спиричева и Ивана Архипова показала лучший результат среди команд, решивших 6 задач, заняла 10 место и была удостоена бронзовой медали. Это уже вторая подряд медаль Петрозаводского университета: в прошлом году команда ПетрГУ получила бронзовую медаль и 13 место, так что сделан — пусть даже небольшой — шаг вперёд. Интересно отметить, что прошлогодний бронзовый призёр, сильнейшая по результатам сезона команда Петрозаводского ГУ, составленная из студентов 2 и 3 курсов, решила полностью пропустить чемпионат мира-2008 года — и получилось так, что их результат оказался превзойдён их старшими товарищами.

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

Занявшая одиннадцатое место команда СПбГУ в составе Сергея Копелиовича, Олега Давыдова и Юрия Петрова в начале соревнований лидировала, но в дальнейшем потратила много времени и штрафных попыток на одну из задач и смогла завоевать только бронзовые медали. Учитывая достижения участников команды — золотые медали Международной олимпиады школьников по информатике 2005 и 2006 года у Сергея Копелиовича, титул победителя TopCoder High School Tournament — 2007 (чемпионата мира по программированию среди школьников, проводимого компанией TopCoder) у Юрия Петрова — можно было рассчитывать на более высокий результат, тем более, что команда СПбГУ рассматривалась специалистами как один из фаворитов чемпионата. Впрочем, у команды есть впереди ещё одно выступление в финале, чтобы сделать соответствующие выводы и постараться улучшить результат. Тренер команды — Андрей Сергеевич Лопатин — будучи участником чемпионата мира по программированию, добился уникального результата, став в 2000 и 2001 годах двукратным чемпионом мира. Сейчас А.С. Лопатин не только руководит подготовкой студенческих команд, но и играет ключевую роль в проведении учебно-тренировочных сборов к Международным олимпиадам школьников по информатике, возглавляет команду России на этих олимпиадах.

На двенадцатом месте — команда Белорусского государственного университета в составе Павел Иржавский, Никита Лесников и Владимир Керус. Для команды это уже второй финал — в первом выступление было менее удачным. Никита Лесников и Владимир Керус в разные годы представляли Беларусь на Международной олимпиаде школьников по информатике: Никита Лесников выигрывал бронзовую медаль на олимпиаде 2005 года и золотую — на олимпиаде 2006 года, Владимир Керус — «серебро» на IOI-2003 и 2004, «бронзу» на IOI-2005. Так что к медалям, завоёванным в школьном возрасте, добавилась и медаль 32-го чемпионата мира. Тренером команды является профессор Владимир Михайлович Котов, один из ведущих организатор соревнований по программированию в Беларуси.

Результаты других команд, представлявших Россию и СНГ, таковы:
Команды Алтайского государственного технического университета и Винницкого национального технического университета решили по 4 задачи и заняли соответственно 31 и 32 место, команды Уральского государственного университета и Новосибирского государственного университета решили по 5 задач и заняли соответственно 23 и 25 место, команды Московского физико-технического института, Орловского государственного технического университета и Ставропольского государственного университета решили по 6 задач и заняли соответственно 13, 16 и 18 место.

Результат, показанный командами России и СНГ в финале тем более ценен, что в финале были обыграны фавориты соревнований, чемпионы Мира и Европы 2007 года — команда Варшавского университета, занявшая в итоге 14 место и проигравшая, кроме команд-медалистов, ещё и занявшей 13 место команде впервые представленного в финале Московского физико-технического института (Даниил Швед, Михаил Костин, Игорь Квасов, тренер команды — Евгений Яковлевич Барский).
Возможно, что участие в зимних сборах 2008 года в Петрозаводске вместе с командой Варшавы, ставшей победителем в общем зачёте сборов, помогло российским командам реально оценить свой текущий уровень подготовки и внести за оставшееся до финала время необходимые коррективы. Таким образом, совместные тренировки с участием сильных зарубежными команд могут оказаться очень существенной помощью при подготовке к крупным соревнованиям по программированию.

Чемпионаты мира по программированию по версии 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 года были сформированы первые четвертьфинальные подрегионы с центрами во Владивостоке, Екатеринбурге, Минске, Рыбинске, Санкт-Петербурге, Саратове. В этом году четвертьфиналы проходили уже в 15 подрегионах (центры — Алматы, Баку, Бишкек, Владивосток, Екатеринбург, Ереван, Минск, Москва, Красноярск, Новосибирск, Рыбинск, Санкт-Петербург, Саратов, Ташкент, Тбилиси), при этом полуфинал NEERC проходил одновременно в Барнауле, Батуми, Санкт-Петербурге и Ташкенте, а квота от региона на финал составила 12 команд.

В прошедшие годы команды из постсоветских государств и особенно — из России показывали высокие результаты в финалах: в 2000 и 2001 годах команда СПбГУ становилась чемпионом мира и Европы, в 2004 году чемпионом мира и Европы стала команда СПб ГУ ИТМО, а в 2006 — команда Саратовского ГУ.
Команды Саратовского ГУ в 2002 году и МГУ в 2005 году становились чемпионами Европы.
Второе место (и золотые медали) завоёвывали команда СПбГУ в 1998 году, команда МГУ в 2003 и 2005 годах. Третье место (также отмечаемое золотыми медалями) завоёвывали команды СПб ГУ ИТМО в 1999, 2001, 2003, 2005 и 2007 годах, Алтайского ГУ в 2006 году, команда Белорусского ГУ в 2004 году.

Команда Пермского ГУ в 2004 году заняла четвёртое место и получила золотые медали, а команда СПбГУ ИТМО в 2000 году за четвёртое место получила только серебряные медали в силу того, что в то время действовали другие правила присуждения медалей.

Серебряные медали также получали команды Саратовского ГУ в 2002, 2003 и 2007 годах, Ижевского ГТУ в 2004 году, СПбГУ в 2006 году, НГУ в 2007 году, бронзовые — команды СПбГУ в 1997 и 1999 году, МГУ в 2001, 2002, 2006 и 2007 году, Киевского НУ в 2003 году, Ижевского ГТУ в 2005 году, Уфимского ГАТУ в 2006 году, Петрозаводского ГУ в 2007 году.

Чаще всего из российских вузов в финалах участвовали команды МГУ и СПб ГУ ИТМО — 13 финалов в 1996-2008 годах. В 11 финалах (1997-2001 и 2003-2008) участвовали команды СПбГУ. В общей сложности за 1995-2006 годы в финалах принимали участие команды из 20 российских, 4 украинских, 1 белорусского, 2 казахских, 1 киргизского и 1 эстонского университетов.

Источник
Tags:
Hubs:
Total votes 51: ↑46 and ↓5+41
Comments43

Articles