Студенты Урала на соревнованиях по программированию

Евгений Штыков

(Статья опубликована в журнале МИФ N 3/1998-99)

Человеку свойственно состязаться. Спортивный азарт и стремление быть первым приводят к появлению новых видов спорта. С 1977 года начинают свою историю чемпионаты мира АСМ по программированию.

АСМ — Association for computing machinery — наиболее авторитетная в мире организация в области компьютеров, объединяющая более восьмидесяти тысяч ученых, инженеров, программистов, студентов, иными словами, специалистов, занимающихся проблемами современного компьютерного мира. Поле деятельности АСМ весьма широко. АСМ проводит конференции, издает журналы и книги, присуждает премии за достижения в области теоретической информатики и компьютерных технологий. Ежегодно АСМ проводит "компьютерную неделю" (ACM computing week), в программу которой входят конференции по основным направлениям информатики, выставки, демонстрации. Одним из основных событий недели является финал командного чемпионата мира по программированию.

Вплоть до 1990 года основную массу участников представляли команды североамериканских стран, а остальной мир был представлен одной европейской региональной группой. Однако в последующие годы интерес к соревнованиям значительно возрос, практически каждый год появлялись новые региональные группы. В 1998 году на соревнованиях впервые был представлен африканский континент.

За прошедшее время сформировались правила проведения соревнований. Команде из трех человек предоставляется один компьютер и предлагается за 5 часов решить максимальное количество задач из числа предложенных (обычно от 6 до 8 задач). Свои решения команды посредством локальной компьютерной сети сдают жюри на проверку. Проверка заключается в запуске программы на наборах тестов, подготовленных заранее и одинаковых для всех команд. Задача считается решенной, если программа успешно прошла все тесты. Если хотя бы один тест не пройден (выдан неверный ответ или программа аварийно завершилась), то задача не считается решенной. Победа присуждается команде, решившей большее число задач. Если таких команд несколько, то учитывается время решения задач. Учет времени решения происходит следующим образом. За каждую решенную задачу команде начисляется столько времени, сколько его прошло с момента начала соревнований до момента отсылки решенной задачи жюри на проверку. Если задача решена командой не с первой попытки, за каждую неудачную попытку решения задачи команде начисляется 20 дополнительных штрафных минут. За неудачные попытки сдачи тех задач, которые команда не смогла решить до конца соревнований, штрафное время не начисляется.

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

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

С 1994 года АСМ-подобные соревнования в Санкт-Петербурге приобрели массовый характер. Популярными стали городские олимпиады для школьников и студентов по АСМ-подобным правилам; это произошло во многом благодаря энтузиазму неоднократного победителя и призера российских олимпиад по информатике А.А. Суханова, будущего директора региональных российских соревнований АСМ В.Г. Парфенова и директора дворца творчества юных В.П. Тарасова. Участие в чемпионатах по программированию перестает быть уделом избранных.

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

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

Российские команды в финале первенства 1995 года (который проходил уже в феврале 1996 года) решили по 4 задачи из восьми и попали в третью группу классифицированных команд. Но это был очередной и очень большой шаг вперед. Россия была в финале!

Чудесным следствием успешного выступления российских команд в региональных первенствах и в финале чемпионата стало предложение Директората об учреждении специального Северо-восточного Европейского региона, охватывающего Россию и часть республик бывшего СССР. Благодаря в том числе и этому, с 1996 года в чемпионат мира включились уральские студенты.

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

В университете было сформировано 8 команд. В июне 1996 года прошли первые отборочные соревнования. В результате в Санкт-Петербург поехали команды в составе Станислав Васильев — Александр Клепинин — Марат Бакиров, и Станислав Скорб — Сергей Герштейн — Никита Шамгунов — Сергей Коган. Первоначально состав второй команды был несколько иным; но был изменен после совещаний с деканатом математико-механического факультета УрГУ. К моменту проведения этого соревнования, в университете еще не было понятия тренерства как такового, никто и не мечтал о собственном сетевом программном обеспечении, все было на дискетах (!). От другого ведущего ВУЗа города в компьютерной отрасли — Уральского государственного технического университета (УГТУ) — поехала команда в составе Тарас Юшков — Евгений Фролов — Павел Залецкий, впоследствии принявшая участие в финале чемпионата мира АСМ 1997/98 года в Алтанте (США).

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

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

Зато блистала команда УГТУ. Решив три задачи (победной стала организация нетривиального перебора на мультиграфе), она заняла четвертое (!!!) место в общем зачете и завоевала право на участие в финале первенства. Состав этой команды был тот же, что и в предыдущем году. Кроме нее, такое право завоевали команды СПбГУ, МГУ и СПбГИТМО. Первой за чертой призеров осталась команда Белорусского государственного университета (БГУ).

Остановимся немного на методике подготовки команды УГТУ, занявшей четвертое место. Отложив все остальные дела, включая учебу, команда готовилась к финалу. Был найден сервер в Испании, содержащий более 400 задач по программированию с наборами тестов, многие десятки этих задач — прорешаны. Изучались и прорешивались задачи с финалов и полуфиналов чемпионатов мира предыдущих лет. Члены команды полностью посвятили себя делу борьбы за мировой престиж.

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

В 1998 году интерес к соревнованиям и на Урале, и в Уральском университете вырос настолько, что для отдельной команды стало нешуточным делом получить хотя бы путевку на чемпионат Урала. Изначально о своем желании участвовать заявило 15 команд (это почти полста человек!), серия из двух отборочных туров допустила к участию 5 из них. Всего на чемпионат Урала приехало 27 команд. Чемпионом Урала становится команда Уральского университета в составе Александр Клепинин — Никита Шамгунов — Александр Петров. На втором месте — команда УГАТУ, на третьем — Пермский технический университет (ПГТУ). К чемпионату начинает проявлять внимание пресса и телевидение. Команда УГТУ, изменившая свой состав из-за возрастных ограничений (из участников финала остался только Павел Залецкий), занимает шестое место. Осенью началась подготовка к Санкт-Петербургу.

Эта подготовка запомнилась студентам надолго. Постоянные индивидуальные и командные занятия, жесткие спарринги УГТУ — УрГУ, чтение литературы и постоянное обдумывание одной, жестко заданной, темы поглощали все время участников. Группа поддержки из обоих вузов частенько не досыпала ночей, старательно выискивая наборы задач, готовя тесты к ним и переводя условия на английский язык.

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

Борьба во втором туре велась в основном между командами Волков — Гольдберг — Костоусов, Атнашев — Бакиров — Овечкина и Хлопин — Никитин — Латушкин и оказалась весьма драматичной. Первые две, априори считавшиеся сильными, объединяет фамилия тренера — Д.О. Филимоненков, преподаватель математики и информатики СУНЦ УрГУ. К слову, Шамгунов, Коган, Клепинин, Хлопин и автор этой статьи каждый в свое время также заканчивали Уральский лицей и учились программированию у Дмитрия Олеговича. Команда Атнашев — Бакиров — Овечкина выступила весьма успешно, и за десять минут до финиша располагалась на первой строчке турнирной таблицы. Но в последние минуты команда Хлопин — Никитин — Латушкин решает еще одну задачу и побеждает. Третье место заняла команда УГТУ, выступавшая вне конкурса (состав: Залецкий — Щекотилов — Яремко). В дальнейшем эта команда, и равная ей по силе команде Клепинин — Петров — Шамгунов, соревновались каждую неделю вплоть до отъезда. Вместе с ними тренировалась и команда Хлопин — Никитин — Латушкин.

Между тренировками, команда Клепинин — Петров — Шамгунов, приглашенная на кубок физтеха УГТУ, стала чемпионом этого соревнования, опередив ближайших преследователей на ДВЕ задачи. Кстати, такое случилось впервые на уральских студенческих соревнованиях по программированию.

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

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

Наступил 1999 год. 19-20 марта был проведен 3-й чемпионат Урала. Чемпионом стала команда УрГУ Шамгунов — Петров — Волков, тем самым обеспечив себе поездку в Санкт-Петербург следующей зимой. Отбор второй команды УрГУ для поездки будет проведен осенью.

Студенты, участвующие в соревнованиях, приходят из школ. Как уже было сказано выше, в Санкт-Петербурге проводятся соревнования школьников по АСМ-подобным правилам. Это дает возможность участникам проявить себя раньше, и достичь в результате большего. В декабре 1998 года команда СУНЦ УрГУ в составе Белов — Костоусов — Петров принимала участие в открытом чемпионате Санкт-Петербурга и заняла там достаточно высокое десятое место. Возможно, что такие правила проведения соревнований будут перенесены в ближайшем году и на всероссийскую олимпиаду школьников по информатике.

Но хотя достижения в спорте чрезвычайно важны, напоследок хочется сказать, что самая главная (если не единственная) составляющая успеха — это чтобы людям нравилось заниматься тем, чем они занимаются. В этом залог счастья.