Россия — чемпион!

В начале марта, в славном канадском городе Ванкувере, прошел 25-й (юбилейный!) чемпионат мира по программированию среди студенческих команд, в том числе и 6 команд из Северо-Восточной Европейской полуфинальной зоны. Две из этих команд, ЮУрГУ (Челябинск) и УрГУ (Екатеринбург), представляли на “самом престижном мировом студенческом компьютерном форуме” (– пресс-релиз организаторов) Уральский четвертьфинальный подрегион этой зоны.

Запомнилась Люфтганза – домашним комфортом и обходительностью, неограниченным пивом и прочим вплоть до французского коньяка и помощью в любых вопросах. Остановка в Торонто – не сильно отличающемся на зимний, серый вид от Екатеринбурга, — только понатыкано везде небоскребов. Впрочем только в центре, дальше – одноэтажная Америка (ну то есть, конечно, Канада, но... даже международный телефонный код у них одинаковый – скромная единица. Дальше будем считать, что слово “Америка” – это сокращение для “Северная Америка”), где мы нашли себе домашний очаг на две ночи – везде наши люди. Героизм простых канадцев (в прошлом простых наших) – приютить на эти самые две ночи таких изрядных Бивисов как мы. Встреча с знакомым, который подарил здоровую бутылку канадского виски, 2 пинты объемом (у них и пинты есть, а на спидометре сверху нарисованы километры, снизу мили. В США еще хуже – километры подписаны снизу едва различимо). Так вот, усилиями злобной маленькой авиакомпании Royal, которая везла нас из Торонто в Ванкувер, эти самые две пинты равномерно распределились по всему моему чемодану. Пропитавшиеся должным образом вещи крепили (?) боевой дух во время соревнований...

Короче говоря, дорога нам понравилась. Только далеко. Если вонзить заточенную спицу в глобус в вертикальной плоскости, проходящей через центр глобуса и Екатеринбург, направив немного вниз – она вылезет в Ванкувере. Но мы так не делали. Глобус жалко.

Компания IBM в четвертый раз подряд выступил генеральным спонсором соревнований, которые проводились в просторных помещениях отеля Westin, расположенного на берегу живописной тихоокеанской гавани, около Stanley Park, в котором находится знаменитый Аквариум.

Приехали. Разместились. Wow. Да, это вам не Рио-де-Жанейро. Рио-де-Жанейро просто отдыхает. Сразу пошли гулять, сразу масса впечатлений. За окном гостиницы самолеты летают как мухи, а при посадке – прямо на водную гладь гавани – порой заполняют собой весь проем окна. Гуляем наугад, сразу находим несколько замечательных улиц, покрытых ресторанчиками и маленькими магазинами. Там кипит жизнь, в то время как в нескольких кварталах, в деловом центре, человека на улице можно встретить только в обеденный перерыв. Нам больше нравится ритм жизни этих улиц – Robson и Denman, который помогает от всего отвлечься. А отвлечься надо. По твердому нашему убеждению, мысли о предстоящем соревновании, прогнозирование, а тем паче тренировки должны совершенно исключаться за три-четыре дня до тура. Мы лучше займемся изучением кухни народов мира (а тот же Robson ею пестрит – здесь и китайские, и вьетнамские, и корейские, и тайские, и японские, и монгольские, итальянские, французские, венгерские, даже украинские рестораны) или, скажем, пойдем кормить уток, канадских гусей и настоящих лебедей на красивое озеро с соответствующим названием “Потерянная лагуна”.

Второй год подряд чемпионами мира стали студенты Санкт-Петербургского государственного университета, решившие 6 задач из 9 предложенных, показав наилучшее время. Также золотые медали и 3-е абсолютное место завоевала команда Института точной механики и оптики из того же замечательного города на Неве.

Впервые две команды одного города в тройке. Виват, Санкт-Петербург! В такой успех даже трудно поверить. Например, отечественной прессе. Забегу здесь вперед: легкий шок после возвращения домой вызвала статья в одном из уважаемых Интернет-изданий о том что “победила команда СПбГУ, а третье место занял СПбИТМО, но это уже из того Санкт-Петербурга, что в Америке” (! – в составе команды, по всей видимости, А.Станкевич, Т.Сойер и Г.Финн?). Еще менее приятно удивили уж совсем уважаемые “Известия” и “Общая газета”. Их куцые колонки о результатах соревнований пересекаются в фактическом материале с истиной примерно по 30% каждая (а между собой, что очень смешно в цифрах никак не пересекаются вообще). В статье из “Общей газеты” ровно одна цифра имеет отношение к действительности – 1-е место СПбГУ. Зато тур, по “ОГ”, длится 4 часа, а участвуют в нем несколько тысяч команд. Это смешно. Нам смешно, мы лучше журналистов знаем предметную область и только смеемся. А после этого читаем о предмете, в котором сами ничего не понимаем и верим. Ну, скажем, “заболеваемость туберкулезом возросла на 27%”. А может она упала на 27%? Или возросла на 127%? В финал ведь смогли как-то две тысячи команд собраться! Грустно это, совсем не смешно.

Николай Дуров и Андрей Лопатин стали двукратными чемпионами мира, Виктор Петров добился такого успеха в первый раз. Фавориты соревнований, питерцы, начали с решения одной из самых трудных задач, но, захватив лидерство в середине второго часа, соревнований более его не упускали.

Еще раз: Виват, Санкт-Петербург! Выступать в ранге фаворитов сложно. Но они не оставили никаких сомнений в закономерности своей второй победы. В том году они уже успели чрезвычайно перепугать организаторов, решив 7 задач из 8 задолго до конца. Поэтому нынче было впервые предложено 9 задач, из которых 3 были практически неподъемными. Зато на остальных 6-ти задачах Дуров, Лопатин и Петров были вне конкуренции.

Команда Уральского государственного университета с 4-мя решенными задачами разделила в официальном протоколе 14-е место, получив бронзовые медали.

Фортуна — хитрая тетка. Она дала нам время насладиться успехом. Мы думали, что мы молодцы. Она привела в мои руки толстого Кормена (то самое “Введение в алгоритмы”, которое лежало на столах у многих участников финала, и которое мы просто обязаны были знать наизусть) лишь уже после приезда. Голосом Саши Сомова указала она мне на страницу 588, где в теореме 28.2 излагалось решение задачи про компараторы, ставшей для нас камнем преткновения. Если б мы знали эту теорему... История не терпит сослагательного наклонения – избитая истина. Но черт возьми! Программа вбивалась за 15 минут... В Ванкувере мы еще не знали об этом, мы радовались. Ну что ж, будем мстить за недочитанного Кормена.

Позади команды УрГУ остались Стэнфорд, КалТех, Беркли, МГУ, команды многих других ведущих университетов мира.

Только никто об этом никогда не узнает. Мы идем третьими по штрафному времени в огромной бронзовой группе команд (15 команд получили медали этого достоинства) — и предпоследними в этой же группе в финальном протоколе измученных политкорректностью канадцев, расставивших команды по алфавиту. Вежливость — это хорошо, а все же очень хочется знать свой точный результат. Его мы вычислили с помощью монитора, который был выставлен на сайте университета Ватерлоо. Мы решили, что если попадем в финал еще когда-нибудь, то потребуем переименования университета таким образом, чтобы его название начиналось на букву А.

Финал чемпионата мира широко освещался в прессе, в частности телекомпанией CNN.

О моменте радости. По словам того же М.О.Асанова, он больше всего обрадовался, когда выяснилось, что продавец в одном из сувенирных магазинов Ванкувера знает, что в его городе проходит такой чемпионат – в новостях видел.

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

О самом туре. Что поражает – каждый судья проверяет тесты глазами (!). Легенда гласит, что самые продвинутые научились использовать команду diff или fc, кому как больше нравится... А так – система работает отлично, ответы приходят быстро, особенно быстро как всегда сообщения о неправильных ответах. Кормят, опять же хорошо. Никто не ест. Не до того. Идет таинство обретения шариков. Самый напряженный момент (так говорили потом в один голос тренеры и зрители) – служитель снимает шарик, соответствующий задаче I (которую никто и не пробовал решать) в критический момент времени – где-то за полчаса до конца тура. Медленно проносит его мимо коридора, где сидят команды СПбГУ, МГУ, СПбГИТМО... поворачивает мимо Ульма и Ватерлоо... проходит мимо Вирджинского технического... минует (еще бы!) УрГУ и ЮжГУ... гордо привязывает к силовому кабелю монитора команды Сеула – а у той это чуть ли не первая сданная задача! Эх, если бы нам! А больше никто не решил задачу I. И задачу G не трогали, и D. И без них хлопот хватало.

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

На “пенсию” уходят 12 из 15 россиян-финалистов - обе команды Санкт-Петербурга полностью, а из 3 других команд в каждой отыграли свое по 2 человека. Так и в нашей команде Никита Шамгунов и Саша Петров больше никогда не испытают радости слова ACCEPTED. Но им есть что вспомнить – бронза чемпионата мира, второе место в полуфинале 1998 года, три победы подряд 1998-2000 гг на чемпионатах Урала!

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

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

О тренировках. Мы так и не можем сойтись во мнениях по поводу тренировок. Почему-то в последнее время мы однозначно проваливали все (!) тренировки, собирая волю в железный кулак лишь на соревнованиях, имеющих отборочное значение. На всех таких соревнованиях – кроме, конечно, финала – мы решали задачу прохождения в следующий тур. Надо ли выигрывать тренировки? Все же да. Но важней всего именно умение собраться и нервная устойчивость. А нервная устойчивость – это опыт. А опыт – это тренировки. Причем пятичасовые, полноценные.

Стабильные успехи уральских команд, неизменное (уже в течение 4-х последних лет) их представительство в финалах чемпионатов мира позволяют говорить о том, что на Урале сложилась своя, уникальная, научная школа по спортивному программированию. Команды уральской школы уже можно отличить от других по стилю программирования, по стратегиям поведения во время тура. Пожалуй, основы этой школы были заложены еще в 1997 году, когда авторским коллективом под руководством Жени Штыкова была написана классическая книжка “Как стать чемпионом мира по программированию”, пытавшаяся обобщить опыт, накопленный в первом питерском полуфинале.

Так как же все-таки стать чемпионом мира по программированию? Вроде и не мне про это писать, а тем кто действительно знает... но все же накопились некоторые соображения. Именно эти соображения – о том, как тренироваться, как решать и даже как придумывать задачи и составляют единое целое, понимаемое здесь под термином “научная школа”. И это здорово, что есть такие соображения. Это, как мне кажется и означает, что уральские команды еще долго будут добиваться успехов на мировом уровне. Многие положения той книги кажутся актуальными и по сей день, многие представляются наивными и безнадежно устаревшими. Это естественно. Мы обязательно напишем новую книгу, и обязательно будем участвовать в новых соревнованиях.

Мораль

“А если вы меня спросите, где здесь мораль//Я направлю свой взгляд в туманную даль// Я скажу, ей-богу, как мне не жаль, я и правда не знаю, в чем здесь мораль...”. Читайте классиков.

P.S.

Никуда бы мы не ездили и ничего бы никогда не выигрывали (и даже не проигрывали), если бы не постоянная поддержка со стороны очень многих людей и организаций. Если я начну всех перечислять, я кого-нибудь забуду, и ему будет обидно. Спасибо всем!

Леонид Волков