Книжная полка
Версия для печати

Финальные соревнования чемпионата мира по программированию

В.Г. Парфенов

Ежегодный студенческий командный чемпионат мира по программированию среди сборных команд высших учебных заведений (ACM International Collegiate Programming Contest ) проводится наиболее авторитетной в компьютерном мире международной организацией ACM - Assoсiation for Computing Machinary ("the First Society in Computing"), начиная с 1977 года. Эти соревнования являются самыми престижными в мировом компьютерном сообществе интеллектуальными состязаниями молодой программистской элиты. Соревнования рассматриваются ведущими компьютерными фирмами как источник их пополнения наиболее квалифицированными кадрами и традиционно поддерживаются крупнейшими компьютерными корпорациями. В последние годы четыре сезона подряд генеральным спонсором чемпионата была корпорация Microsoft, вложившая в организацию соревнований 27 миллионов долларов. Начиная с сезона 1997/98гг., генеральным спонсором стал главный конкурент Microsoft - корпорация IBM, вступившая с ней в жесткую борьбу за лучшие головы планеты. В последние годы чемпионат мира получает все большую популярность и известность. В сезоне 1999/2000 гг. в 23-м чемпионате приняли участие около 2000 команд из более 1000 ведущих вузов 70 стран мира.

Согласно выработанным за более чем двадцатилетнюю историю правилам проведения соревнований команде, состоящей из трех участников, предоставляется один компьютер и предлагается в течение пяти часов решить максимальное число из предложенных задач, число которых обычно лежит в диапазоне от 6 до 8. Побеждает команда, решившая наибольшее число задач, а в случае равенства числа решенных задач - команда, затратившая меньше времени.

Схема организации чемпионата мира включает три этапа: четвертьфинальный, полуфинальный и финальный. На полуфинальных этапах команды соревновались в сезоне 1999/2000 гг. в 28 региональных группах, среди которых были распределены вузы стран всех континентов. Команды - победительницы полуфинальных состязаний выступили в финале, который в этом сезоне состоялся 18 марта 2000г. в Орландо (Флорида, США). В финале приняли участие 60 команды из ведущих университетов мира. По результатам финальных соревнований определился команда - чемпион мира, а также команды - чемпионы континентов.

Россия впервые получила право на организацию собственной полуфинальной Северо-Восточной Европейской группы в сезоне 1996/97 гг. Организацию соревнований Директорат чемпионата поручил Санкт-Петербургскому государственному институту точной механики и оптики (техническому университету), студенты которого успешно выступают в чемпионате. Северо-Восточный Европейский регион включает страны бывшего СССР. Профессор СПбГИТМО (ТУ) В.Г.Парфенов является региональным директором полуфинальных состязаний. В прошлом году полуфинальные соревнования прошли в Санкт-Петербурге уже в четвертый раз.

С самого начала в качестве генерального регионального спонсора полуфинальных состязаний выступает крупнейшая петербургская выставочная компания "Рестэк", предоставившая молодым российским программистам весомую материальную поддержку при организации их поездок на финал. Полуфинальные соревнования являются важной частью научно-образовательной программы известной компьютерной выставки "Инвеком", проводимой компанией "Рестэк". В этом году спонсором полуфинальных состязаний выступила также софтверная компания Astrive, Inc.

В декабре прошлого года решение о поддержке поездки команд-победительниц на финал приняло московское представительство корпорации Microsoft, выделившее часть средств на приобретение авиабилетов для членов команд.

Итоги закончившихся отборочных четвертьфинальных состязаний сезона 1999/2000 гг. показали огромный интерес вузов к этим соревнованиям. В частности в этом году было организовано семь четвертьфинальных региональных групп, охвативших всю теppитоpию России и стран ближнего зарубежья: Дальневосточная (вуз-организатор - Дальневосточный ГУ), Уральская (Уральский ГУ), Южная-Поволжская (Саратовский ГУ), Центральная (Рыбинская авиационная технологическая академия), Северо-Западная (СПбГИТМО (ТУ) и СПбГУ), Западная (Белорусский ГУ) и Сибирская (Новосибиpский ГТУ). Всего в четвертьфинальных и полуфинальных соревнованиях приняли участие 237 команды из 118 вузов, представлявших практически все ведущие классические и технические университеты России, а также университеты Белоруссии, Грузии, Киргизии и Эстонии. Отметим, что в этом полуфинале впервые выступили две команды из Грузии. В будущем сезоне предполагается создать третью (дополнительно к петербургской и барнаульской) полуфинальную группу, включающую вузы Грузии, Армении и Азербайджана.

Таким образом к настоящему времени эти соревнования превратились в крупнейший за последние десятилетия по географии и числу участников студенческий форум России и стран ближнего зарубежья. Состязания явились хорошим стимулом для формирования региональных центров подготовки способных молодых программистов, нередко поддерживаемых местными компьютерными фирмами. По результатам соревнований стали составлять своеобразный рейтинг вузов по уровню обеспечиваемого в них профессионального компьютерного образования. Способность вуза выявить, собрать и подготовить несколько команд сообразительных ребят свидетельствует об общем уровне всей компьютерной образовательной инфраструктуры, престиже и кадровом потенциале данного вуза.

Северо-Восточная Европейская региональная полуфинальная группа стала самой большой в чемпионате мира по числу участвующих команд, что позволило после определенных дипломатических усилий увеличить число мест в финале для этой группы с двух в 1996 году до шести в 1999 году. По сравнению с 1998 годом было добавлено одно место в финале.

Как и в предыдущие годы, в рамках соревнований было обеспечено участие в состязаниях в реальном масштабе времени команд сибирских вузов с использованием сети RUNNet. Команды ведущих вузов Барнаула, Новосибирска, Томска, Омска, Владивостока и других городов Сибири и Дальнего Востока (28 команд) разместились во время проведения петербургского тура (в Аничковом дворце собрались 56 команд) в узле федеральной университетской компьютерной сети RUNNet, расположенном в Алтайском государственном техническом университете, и соревновались под наблюдением представителей жюри, которые специально прибыли в Барнаул.

Напомним, что в 1996 и 1997 гг. чемпионами России становились петербургские команды: государственного университета и государственного института точной механики и оптики (технического университета). Эти же команды имели лучшие достижения в финалах мирового первенства: 1998 - СПбГУ - второе абсолютное место в мире, 1999 – СПбГИТМО (ТУ) - третье абсолютное место в мире. Только они в последние три года неизменно входили в число 15 сильнейших команд мира, решавших в финале более половины предложенных задач. В 1998 г. чемпионом России и стала команда МГУ, а в 1999 - команда СПбГУ.

За последние четыре года соревнования финала стали гораздо более интересными, напряженными, подчас приносящими результаты, сильно расходящиеся с ожидаемыми. Огромное значение приобрел морально-писхологический фактор и сильно возросла цена ошибки или заминки, допущенной в ходе соревнований. Резко возросла плотность результатов команд в финале. В связи с этим, начиная с финала 2000 года, был изменен порядок награждения команд. Наряду с определением абсолютных мест, стали присуждаться и медали: команды, решившие одинаковое с чемпионом мира число задач, получали золотые медали, решившие на одну задачу меньше - серебряные, на две меньше - бронзовые. Кроме того, как обычно командам, попавшим в первую десятку, выдавались денежные призы и почетные доски с указанием занятого места.

В финале 2000 года нашу группу представляли команды МГУ, СПбГУ, СПбГИТМО (ТУ), Новосибирского ГУ, Белорусского ГУ и Южно-Уральского ГУ (Челябинск).

В финале блестяще выступили петербургские студенты. Студенты СПбГУ лидировали на протяжении всех соревнований, причем их отрыв от второй команды доходил в ходе соревнований до трех задач (!). Все были уверены, что они решат все восемь задач до истечения контрольных 5 часов. Команда СПбГИТМО первые три часа шла в первой пятерке, а в начале четвертого часа с пятью решенными задачами вышла на второе место, отставая от СПбГУ на одну задачу. Такое развитие событий вызвало настоящий шок у тренеров и болельщиков других команд, поскольку в финале ни один город в мире, кроме Санкт-Петербурга, не был представлен двумя командами, которые к тому же вели борьбу между собой за первое место. В начале заключительного пятого часа борьбы лидировавшие команды СПбГУ и СПбГИТМО решили соответственно седьмую и шестую задачи и приступили к решению одной и той же задачи G. К сожалению, в английском тексте ее условия содержалась фраза, которая могла быть однозначно понята только "носителем английского языка". Обе петербургские команды, перепробовав различные варианты перевода, так и не добились успеха. В результате команде СПбГУ не удалось решить все восемь задач, а команда СПбГИТМО пропустила вперед команды канадского университета Waterloo и немецкую команду университета Альберта Эйнштейна из города Ульм.

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

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

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

В обстановке крайней нервозности неплохо проявили себя и другие российские команды, вошедшие в группу команд, для которых организаторы указали занятые места - МГУ (17 место, 3 решенные задачи), НГУ (26 место, 2 решенные задачи), Южно-Уральского ГУ (27 место, 2 решенные задачи). Весьма неудачно выступила команда БГУ, не выдержавшая колоссального нервного напряжения соревнований и попавшая с одной решенной задачей в группу команд, записанных в протоколе в алфавитном порядке.

Отметим, что команда МГУ заняла почетное второе место на проходившем за день до основных соревнований конкурсе по решению специальных задач при помощи продукта Visial Age, разработанного корпорацией IBM.

Небывалым провалом закончилось выступление американских команд, лучшая из которых - команда Калифорнийского технологического института, заняла лишь 12 место. Очень мощно выступили китайские команды, три из которых попали в первую десятку.

Дополнительную информацию можно получить у Директора полуфинальных соревнований Северо-Восточного Европейского региона профессора СПбГИТМО (ТУ) Парфенова Владимира Глебовича: р.т. (812) 233-42-98, ф. (812) 232-43-18, e-mail: parfenov@mail.ifmo.ru

Фотографии победителей можно посмотреть на сервере http://acm.baylor.edu/acmicpc/finals.