К истории чемпионатов мира ACM по программированию

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

Чемпионат мира по программированию среди сборных команд высших учебных заведений (ACM International Collegiate Programming Contest) проводится c 1977 г. Его организатор, Международная ассоциация ACM (Association for Computing Machinery, http://www.acm.org), наряду с IEEE Computer Society и British Computer Society входит в тройку наиболее авторитетных ассоциаций ИТ-профессионалов в мире. Генеральным спонсором чемпионатов мира 1990—1993 гг. была корпорация AT&T, 1994—1997 гг. — Microsoft, 1998—2004 гг. — IBM. Схема проведения чемпионата мира по программированию включает три этапа: четвертьфиналы (зональный), полуфиналы (региональный) и финальный. Команды-победительницы региональных групп (полуфиналов) выходят в финал и разыгрывают звания чемпионов мира и чемпионов разных регионов — Европы, Северной Америки, Азии, Латинской Америки, Тихоокеанского региона, Африки и Ближнего Востока.

В первых чемпионатах участвовали преимущественно команды вузов США и Канады. Начиная с 1990 г. возрастает интерес к этим состязаниям, и появляются новые региональные группы, прежде всего из Европы. Впервые европейская команда завоевала титул чемпионов мира в 1995 г. Этого успеха удалось добиться студентам университета Альберта Людвига (Фрайбург, Германия). Затем два года на вершине Олимпа были команды из Северной Америки (University of California, Berkeley; Harvey Mudd College). В 1998 г. на верхнюю ступень пьедестала почета поднялась команда Charles University (Прага, Чехия), а в 1999 г. чемпионом мира стала команда University of Waterloo (Канада). Последние пять финалов (2000—2004 гг.) прошли под знаком явного превосходства европейской школы: ни разу за это время команды Северной Америки не завоевывали высший титул. Лишь однажды (2002) команда Shanghai JiaoTong University (Китай) сумела прервать гегемонию Европы. Более того, три из четырех победных финалов для Старого Света принесли заветный титул командам из России (СПбГУ в 2000 и 2001 гг. и СПбГУ ИТМО в 2004 г.). В 2003 г. специалисты также прочили победу российской команде (МГУ), но ее на самом финише обошла сборная Варшавского университета (Польша).

За более чем 25-летнюю историю соревнований (в 2004 г. финал проводился в 28-й раз) окончательно сформировались правила проведения: команде из трех человек предоставляется один компьютер и предлагается в течение 5 ч решить максимальное количество из предложенных задач (от 8 до 10). Побеждает команда, решившая наибольшее число задач, а в случае равенства этого показателя — затратившая меньшее время. Задачи составляются таким образом, чтобы участники смогли продемонстрировать свое умение как в компьютерной алгоритмизации задач, так и в составлении эффективных программ, реализующих алгоритмы, выбранные для решения. При подготовке задач преимущество отдается таким областям, как теория графов, комбинаторика и геометрия.

Российские команды впервые приняли участие в соревнованиях с сезона 1993—1994 гг., когда был образован новый Восточно-Европейский регион. От России выступала только команда СПбГУ (С.-Петербургский государственный университет), которая решила 3 из 6 задач и заняла 5-е место среди 22 команд (в финале 2004 г. было 73 команды из 31 страны). По нынешним правилам это принесло бы питерцам серебряные награды. К сожалению, организаторы чемпионата из года в год вносят сумятицу не только в распределение медалей, но и в само понятие «места». Так, например, в смысле результатов финала чемпионата мира 2000 г. команда СПбГИТМО находится на 5-й строчке таблицы, при этом рядом с ней указано число 4, соответствующее занимаемому положению (ranking). Во избежание путаницы все подобные ранги в этой статье приведены в соответствие реальным местам, а сам термин «ранг» далее не используется.

В сезоне 1994—1995 гг. от России выступали уже три команды: МГУ, СПбГУ и СПбГИТМО. В полуфинале команды ИТМО и МГУ решили по 5 из 6 задач и заняли соответственно 3-е и 5-е места. Поскольку квота от региона была установлена в две команды, то в финал российские сборные не попали. Первые два места в полуфинале заняли студенты Бухарестского политехнического института и Киевского ГУ (обе решили по 6 задач), но в финале они выступили неудачно — румыны решили 2 задачи из 8, а киевляне — ни одной.

В сезоне 1995—1996 гг. команды СПбГИТМО и МГУ впервые вышли в финал чемпионата мира. Он прошел в Филадельфии (США) параллельно с первым историческим матчем Гарри Каспарова с шахматной системой IBM Deep Blue. Выступление российских команд в роли дебютантов было вполне достойным (решили по 4 задачи, на 2 меньше чемпионов) и заняли 17—26-е места. Среди причин, не позволивших выступить лучше, — отсутствие опыта и пробелы в знании английского языка, повлиявшие на понимание условий задач.

В 1997 г. финал проходил в самом сердце Кремниевой долины — в Сан-Хосе (США). Он был знаменателен тем, что чемпионат мира, приуроченный по традиции к компьютерной неделе ACM (ACM Computing Week), проводился в год 50-летия ассоциации ACM. Впервые наши команды (СПбГИТМО, СПбГУ) имели реальный шанс завоевать титул чемпионов мира. Результат в 6 решенных задач показали сразу шесть команд, среди которых оказались новые чемпионы мира — Harvey Mudd College (США) и вице-чемпионы — Umea University (Швеция). Команда СПбГУ (8-е место) решила 5 задач. При этом она оставила позади себя участников из таких прославленных вузов, как Массачусетский технологический институт, университеты Стэнфорда, Принстона и Карнеги-Меллона. Команда СПбГИТМО также решила 5 задач (11—15-е места), но могла всерьез поспорить за «золото», поскольку потеряла 40 мин из-за ошибки жюри, которое сначала не приняло одну из решенных задач, а затем подтвердило ее принятие. Протест нашей команды, требующей хотя бы уменьшить ее штрафное время, так и не был удовлетворен. Третья российская команда (МГУ) решила лишь 3 задачи и оказалась в неранжированном списке финалистов (Honorable Mention).

Финал чемпионата мира сезона 1997—1998 гг. состоялся в Атланте (США). От России были представлены уже четыре команды: СПбГУ, МГУ, УрГТУ и СПбГИТМО. Титул чемпиона мира (6 решенных задач) выиграла команда Charles University (Прага, Чехия), а команда СПбГУ (2-е место, 6 задач) стала вице-чемпионом мира и впервые в истории участия команд из бывшего СССР взошла на пьедестал почета. Победителям она проиграла лишь по времени. В составе команды СПбГУ были Виктор Баргачев и Илья Миронов (золотые медалисты Международной олимпиады школьников по информатике 1994 г. и 1993 г. соответственно) и Олег Семенов. Команда СПбГИТМО решила 5 задач и заняла 11—16-е места. Команды МГУ и УрГТУ решили по 4 задачи и обосновались на 17—23-м местах турнирной таблицы.

В Эйндховене (Нидерланды) в финале сезона 1998—1999 гг. самую большую по числу участвующих команд Северо-Восточную Европейскую полуфинальную группу представляли пять команд: МГУ, СПбГУ, СПбГИТМО, Уральского и Белорусского ГУ. Команда СПбГИТМО в результате заняла 3-е место (6 решенных задач), пропустив вперед чемпионов — University of Waterloo (Канада) и вице-чемпионов — Albert-Ludwigs Universitet Freiburg (Германия) только из-за худшего показателя времени решения задач. Команда СПбГУ заняла высокое 9-е место (5 задач). Команда МГУ (4 задачи) — 18—27-е места, команда БГУ (3 задачи) поделила 28—38-е места. Сборная Уральского ГУ оказалась в неранжированном списке финалистов (Honorable Mention). За команду СПбГИТМО выступали Матвей Казаков, Владимир Лёвкин, Александр Волков (тренер — Марк Сандлер).

Начиная с сезона 1999—2000 гг. были внесены изменения в правила: наряду с определением абсолютных мест стали присуждаться и медали. Команды, решившие одинаковое с чемпионом мира число задач, стали также получать золотые медали, решившие на 1 задачу меньше — серебряные, на 2 — бронзовые. В финале нашу группу представляли команды СПбГУ, Белорусского ГУ, МГУ, Новосибирского ГУ, Южно-Уральского ГУ (Челябинск) и СПбГИТМО. Финал проходил в Орландо (США) и впервые принес России триумфальную победу: чемпионами мира и Европы стала команда СПбГУ, за которую выступали Николай Дуров и Андрей Лопатин (победители международных олимпиад по информатике), а также Олег Етеревский. Она великолепно стартовала, решив 5 задач из 8 немногим более чем за 2 ч, но забуксовала на задаче G, условия которой, как потом выяснилось, были сформулированы так, что их могли понять только носители английского языка. В итоге команда СПбГУ решила 7 задач, опередив всех своих соперников — команды университетов Мельбурна (Австралия) и Ватерлоо (Канада). Серебряные награды завоевала команда СПбГИТМО (4-е место), в которую входили Андрей Станкевич (тренер чемпионов мира 2004 г.), Денис Кузнецов, Георгий Корнеев. Команда МГУ заняла в итоговом протоколе 13—19-е места. Другие команды из бывшего СССР выступили так: НГУ и Южно-Уральский ГУ — 20—26-е места), БГУ — 27—43-е места.

Финал чемпионата сезона 2000—2001 гг. прошел в Ванкувере (Канада) и ознаменовался новым успехом отечественных команд. Решив 6 задач, вновь чемпионами мира и Европы стала команда СПбГУ (Николай Дуров, Андрей Лопатин, Виктор Петров). Команда СПбГИТМО, немного уступив по времени вице-чемпионам мира из Virginia Tech, заняла 3-е место (6 задач) и также получила золотые медали. За команду СПбГИТМО выступали Андрей Станкевич, Денис Кузнецов, Георгий Корнеев. Позади петербургских студентов оказались команды известнейших университетов мира — Гарварда, Стэнфорда, Беркли, Принстона, Карнеги-Меллона, Массачусетского технологического института, Варшавского и Пражского университетов. Бронзовые медали (разделили 14—28-е места) завоевали команды Уральского ГУ и МГУ, решившие по 4 задачи. Студенты Южно-Уральского университета поделили 29—47-е места. По правилам соревнований одни и те же участники команд не могут выступать более чем в двух финалах, поэтому на следующий год блестящей команде СПбГУ требовалось кардинально обновлять свой победный состав.

Финал чемпионата мира сезона 2001—2002 гг. в Гонолулу на Гавайях был ознаменован победой студентов Шанхайского университета (Китай). В этом финале слегка претерпели изменения правила награждения: золотые медали стали вручаться первым трем командам, серебряные — второй тройке, а бронзовые — командам с 7-го по 10-е места. Несмотря на относительную неудачу питерских команд, хорошо выступили команды Саратовского ГУ и МГУ. Команда Саратова завоевала звание чемпионов Европы и получила серебряные медали чемпионата мира (заняла 6-е место). При этом она всех держала в напряжении до последнего момента, поскольку имела лучшие показатели по затраченному времени и в случае решения 6-й задачи обошла бы шанхайских студентов и стала бы чемпионом мира. Команда МГУ получила бронзовые медали (9-е место). Остальные команды из бывшего СССР выступили так: СПбГИТМО — 11—17-е места; Белорусский ГУ, Новосибирский, и Петрозаводский университеты — 18—26-е места; Орловский ГУ — 27—40-е места.

Финал сезона 2002—2003 гг. проходил в Лос-Анджелесе (США). Очень высоко оценивались шансы на победу чемпионов России 2002 г. — команды МГУ (Петр Митричев, Евгений Черепанов, Максим Бабенко). К сожалению, в последний момент победа была упущена, и чемпионами мира стала команда Варшавского университета (9 решенных задач), которая в течение последнего часа соревнований сумела решить сразу 3 задачи. Команда МГУ одолела в итоге 8 задач, заняла 2-е место и завоевала золотые медали. «Золото» было вручено и команде СПбГИТМО (7 задач), занявшей третью строчку итогового протокола (Александр Штучкин, Евгений Южаков, Тимофей Бородин. Тренер — Андрей Станкевич). В этом году вновь изменились правила награждения: золотые медали стали вручаться первой четверке команд, серебряные — второй четверке, а бронзовые — командам с 7-го по 12-е места. Серебряные медали получили студенты Саратовского университета (7-е место). Бронзовые награды достались команде Киевского национального университета им. Тараса Шевченко. Остальные команды из регионов бывшего СССР выступили так: Белорусский ГУ, Самарский ГУ — 21—29-е места; Нижегородский ГУ, СПбГУ — 30—42-е места.

Финал чемпионата мира 2004 г., который прошел в Праге (Чехия), завершился настоящим триумфом: чемпионом мира (7 решенных задач из 10) стала команда СПбГУ ИТМО (Дмитрий Павлов, Павел Маврин, Сергей Оршанский, тренер — Андрей Станкевич). Дмитрий Павлов и Сергей Оршанский заканчивали в С.-Петербурге физико-математический лицей № 239, а Павел Маврин приехал учиться в С.-Петербург из Тольятти. Дмитрий и Павел завоевали в 11-м классе серебряные медали на Международной олимпиаде школьников по информатике в Сеуле. Им за это была присуждена премия Президента Российской Федерации. Готовил команду Андрей Станкевич — один из самых успешных российских тренеров, обладатель золотой медали чемпионата мира 2001 г. и серебряной медали чемпионата мира 2000 г., магистрант кафедры компьютерных технологий СПбГУ ИТМО. На чемпионате 2004 г. был награжден призом за наибольший вклад в олимпиадное движение в Европе.

Команда С.-Петербургского государственного университета информационных технологий, механики и оптики была победителем и полуфинала в своей группе (чемпион России 2003 г). Решив 6 задач, 2-е место на чемпионате мира заняла команда из Королевского технологического института KTH — Royal Institute of Technology (Швеция), третье завоевала команда Белорусского государственного университета (БГУ). За нее выступали Виктория Лебедь, Максим Осипов и Иван Метельский. На пьедестал почета попали еще две российские команды — Пермского государственного университета (4-е место, золотые медали) и Ижевского государственного технического университета (8-е место, серебряные медали). Прошлогодние чемпионы мира (команда Варшавского университета) заняли 10-е место. В итоге Россия и Белоруссия выиграли 3 золотых и 1 серебряную медали, опередив фаворитов из США, Канады, Польши и Китая. В десятке сильнейших оказались пять европейских команд, при этом североамериканские команды поправили свое пошатнувшееся реноме: Массачусетский и Калифорнийский технологические институты завоевали серебряные награды (5-е и 7-е места соответственно). Студенты Гарвардского университета получили бронзовые медали (9-е место). Что касается других команд из стран бывшего СССР, то они выступили так: Нижегородский и Киргизско-Славянский ГУ — 15 — 26-е места; Новосибирский, Петрозаводский ГУ, СПбГУ и университет Тарту — 27 — 43-е места. Команда МГУ оказалась в неранжированном списке финалистов (Honorable Mention).

Таким образом, высшими достижениями в чемпионатах мира ACM различных команд из стран бывшего СССР являются (см. также таблицу):

• чемпионы мира — СПбГУ (2000, 2001), СПбГУ ИТМО (2004);
• чемпионы Европы — СПбГУ (2000, 2001), Саратовский ГУ (2002), СПбГУ ИТМО (2004);
• золотые медали — СПбГИТМО (2001, 2003), МГУ (2003), Пермский ГУ (2004), Белорусский ГУ (2004);
• серебряные медали — СПбГИТМО (2000), Саратовский ГУ (2002, 2003), Ижевский ГУ (2004);
• бронзовые медали — СПбГИТМО (1999), Уральский ГУ (2001), МГУ (2001, 2002), Киевский национальный университет (2003).

Подводя итоги выступления студенческих команд из стран бывшего СССР на последних чемпионатах мира ACM по программированию, следует отметить явную тенденцию роста качества их подготовки и великолепные спортивные результаты. За последние пять лет команды из России, Белоруссии и Украины завоевали 3 из 5 возможных титулов чемпионов мира, 4 — чемпионов Европы; получили 8 золотых и по 5 серебряных и бронзовых медалей.

Полуфиналы самой большой по численности Северо-Восточной Европейской группы (директор проведения чемпионата в группе — доктор технических наук, профессор В. Г. Парфенов из СПбГУ ИТМО), делегирующей в финал команды из России, Белоруссии, стран Балтии, Закавказья и Средней Азии, превратились фактически в малые чемпионаты мира.

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

Спонсорами последнего полуфинала Северо-Восточной Европейской группы, собравшего 555 команд из 218 университетов, стали корпорация IBM, профессиональные ИТ-ассоциации ФОРТ-РОСС и РУССОФТ, российское представительство корпорации Intel, а также компании «Рестэк» и «Интерра». Спонсором золотых медалистов 2004 г. — команды Белорусского ГУ — является компания EPAM Systems.