Незадолго до начала Чемпионата мира по спортивному программированию среди студенческих команд по версии ACM мы побеседовали с Александром Скидановым - лидером наших программистов. Беседа касалась не столько наших шансов на финал - зачем искушать судьбу произнесенными вслух словами? - сколько других нюансов, связанных со спортивным программированием.
- Саша, а где работают лучшие спортсмены-программисты нашей страны после завершения спортивной карьеры?
- А у тебя в перспективе тоже такие планы?
- В целом, да. Если не Google, то центральный офис MicroSoft. Просто хотелось бы работать профессионально и без переучивания. А, скажем, в Samsung я буду такой же как все начинающие.
Но это, конечно, потом. А в этом сезоне я поставил себе сверхзадачу - "выжать" максимум из спортивных соревнований по программированию - и финал ACM в Канаде, и Topcoder Open и Imagine Cup (см. комментарий). Это решение пришло ко мне год назад. Тогда, после неудачи в полуфинале ACM, команда фактически распалась. И я долго делал для себя выбор: продолжать тренировки или согласиться на предложение поступать в магистратуру ИТМО (С.-Петербург). Они как раз набирали олимпиадников и с жильем проблемы обещали решить вполне нормально. С нашего потока тогда Кирилл Тимофеев уехал. А я вот остался - решил еще раз попытаться пробиться на финал ACM. Получилось.
Правда, я подозреваю, что после Канады наступит депрессия, но это еще впереди.
- ?!
- А как Вы думали? Конечно, не сразу, месяца через два. Просто окончание спортивной карьеры сразу лишит меня цели нескольких последних лет жизни. А без цели как вообще жить?
- А какие шансы у команд ИжГТУ на следующий сезон?
- В первую очередь пока это будет зависеть от Жени. Если он не "забьет" на тренировки и будет дисциплинирован (как в свое время Руслан, когда ушел Коля) или найдет себе достойного нового спаринг-партнера, результат будет.
А вот что касается остальных наших команд, то их еще надо "разбудить". Сегодня они, обладая очень неплохими способностями, как-то вяло тренируются. Отсюда и результат. Точнее, его отсутствие.
- Чемоданы уже собраны?
- Почти. Кстати, в Канаду мы едем сразу же после Екатеринбурга, где планируем выступить на Чемпионате Урала (29-30 марта). Хорошо бы еще доехать на финал Российского Imagine Cup в Москву в середине апреля (совсем недавно мы с Витей Камашевым получили это право) и на TopCoder Open в Лас-Вегас в мае (12-16). Так что попутешествовать придется.
- А что, можно не доехать?
- Можно. Что касается Лас-Вегаса, то все будет зависеть от того, пройду ли я, как это шутят в СП-тусовке, 5-й отбор в Американском посольстве и сколько времени на это понадобиться. Сами понимаете, что для оформления визы нужно сдать все документы, включая загранпаспорт, но без него поехать на финал в Канаду я, конечно, не смогу.
А что касается Москвы, то здесь все будет зависеть от организаторов. Дело в том, что из 6 финалистов Российского Imagine Cup четверо (кроме нас с Витей еще Иван Попелышев из МГУ и Иван Красильников из Ставрополя) едут в Канаду, а сроки проведения финала ACM и Российского Imagine Cup Algorithm в Москве частично перекрываются. Так что если организаторы не решат этой проблемы, мы, разумеется, туда не попадаем.
- Как готовишься к поездке в Лас-Вегас? Скажем, режим дня "тренируешь" или стратегию поведения в казино?
- Никак не готовлюсь, если не считать, что приходится оформлять визу. А режим дня, по-моему, и менять не придется - там, если верить слухам, жизнь кипит ночью. А то, что у них ночь, у нас день. Так что можно сказать, к смене часового пояса даже и подстраиваться не придется.
А если честно, то до сих пор отхожу от напряжения последнего отбора. Накануне два дня старался не думать о программировании вообще, занимался только физическими работами. За несколько часов до начала просто морозило - пришлось даже одеться потеплее. Во время турнира ребята из моей команды (Е. Кузяков и В. Камашев) были "на связи" - в любой момент готовы были помочь через "аську", но во время матча я даже об этом забыл. Минут за 20 до окончания понял, что один блок в моей программе с ошибкой. Оставшееся время потратил исключительно для анализа этого "открытия" - то мне казалось, что эту ошибка обнаружится на первом же тесте, а то казалось, что к этому куску кода и перехода-то не будет никогда... В общем, нервов потрепал изрядно, но результат меня вполне радует - 14 место в мировом рейтинге. Интересно, что бы мне сейчас сказал Коля?
- А что, Imagine Cup легче прошел?
- Прошел, если быть точным, только Российский полуфинал. Задачи были довольно сложные, жалко только, что вспомнили о турнире только мы с Витей (все-таки 9 марта это все еще праздник), а вот Женя пропустил. Что качается международного полуфинала, то он еще не закончился - там правила немного другие. Знакомые ребята из других команд постоянно предлагают встретиться в Париже летом на финале, но пока даже подхода к прохождению этого этапа не вижу. Может быть, когда немного освобожусь от нахлынувшей суеты, что-нибудь придет в голову. Но в это даже поверить просто невероятно - участвовать во всех финалах сезона.
- Твоя самая нелепая мечта?
- Посмотреть со стороны на наши тренировки перед финалом: я даже сценарий этого видеосюжета придумал: вот крупным планом клавиатура, по ней в бешеном темпе движутся руки программиста-виртуоза. Их сменяет экран монитора. Убегающие вверх строчки и вот уже желанное сообщение (показать по буквам!) - "Accepted". Финальная сцена - взмывающие вверх руки, осиротевшая клавиатура, на экране - "The end".
- Что же, надо добавить только рекламное "Так и будет!". Мы верим в тебя, Саша. Успехов тебе и нашей команде.
- Спасибо, мы постараемся.
--------------------------------------------------------------------------
Наибольшей популярностью сегодня пользуются индивидуальные профессиональные турниры по спортивному программированию, организуемые компаниями TopCoder и MicroSoft. Их привлекательность еще и в том, что практически никаких ограничений к участникам, в отличие от ACM, они не предъявляют. Поэтому те, кто только пробует свои силы в спортивном программировании, или наоборот, уже завершил свою карьеру в ACM на пике формы (П. Митричев, А. Станкевич, да и наш Н. Пермяков), вполне могут принимать там участие.
В конкурсе алгоритмов TopCoder приблизительно раз в неделю проводит турнир SRM - Single Round Match. Кроме того, ежегодно проходит турнир TopCoder Open (TCO), который считается неофициальным чемпионатом мира по программированию среди профессионалов. Ежегодно в турнире принимают участие около четырех тысяч программистов со всего мира. Финал этих соревнований (онсайт-раунд) проходит весной в США (в 2008 году это Лас-Вегас). Для участников ТСО нет никаких ограничений, кроме одной - в онсайд-раунд допускаются лица старше 18 лет. Также ежегодно проводятся подобные турниры для студентов - TopCoder Collegiate Challenge и старших школьников (10-11 классы) - TopCoder High School Tournament.
Общая схема всех соревнований на TopCoder одинакова. Для участия в любом матче необходимо зарегистрироваться хотя бы за 5 минут до его старта. Все зарегистрированные на матч участники разбиваются на виртуальные "комнаты" по 21-22 человека. Соревнование идет между членами одной комнаты. Турнир проводится на базе специализированной программы ARENA, а средства разработки программ допускается использовать практически любые.
Каждый матч состоит из 2 фаз. В первой продолжительностью 1 час 15 минут предлагается написать программный код к 3-м задачам. Отправленное решение системой не комментируется и за него в зависимости от сложности и времени написания кода начисляются некоторые баллы. Во 2-й фазе матча длительностью 15 минут членам одной "комнаты" становятся доступны все отправленные решения с целью найти ошибки в программах соперников. Для иллюстрации ошибки нужно предложить тест, на котором эта ошибка проявится. Каждая удачная попытка "завалить" чужую программу премируется, а неудачная - штрафуется. Интрига сохраняется до последней минуты турнира - набранная итоговая сумма баллов с учетом проверки на системных тестах и тестах других участников становится известна только после завершения соревнования. Хотя считается, что разбираться в чужом коде - занятие не из приятных, такие мастера как П. Митричев за отведенные 15 минут могут найти ошибку и "завалить" 10-11 чужих программ, за что получают неплохие премиальные баллы в матче.
Для всех зарегистрированных участников TopCoder формирует рейтинговые баллы (не путать с баллами отдельного матча!). Они пересчитываются после любого соревнования по достаточно сложной формуле. Для наглядности разработана специальная цветовая шкала рейтинга: белый (начинающие), дальше серый, зеленый, синий, желтый, красный (от 2200). Те, чей рейтинг выше 3000 баллов, имеет специальный статус "TARGET". В последние годы число TARGETов около 10, первое место надежно удерживает москвич П. Митричев.
За высокие результаты в некоторых (спонсорских) матчах начисляются не только условные баллы, но и реальные денежные суммы. Чтобы получить право распоряжаться ими нужно оформить кое-какие бумаги непосредственно в Посольстве или Консульстве США.
Схема турнира TopCoder Open следующая. Сначала проводятся 3 квалификационных тура, из которых на 1 отборочный тур проходит 1800 человек. Затем последовательно этап за этапом это число сокращается: 900-300-150. По результатам последнего отборочного тура остается 72 человека, попадающие в финальную часть соревнований (онсайт-раунд). Программисты шутят, есть еще и 5-й "отбор" - в Посольстве США, по результатам которого и определяется окончательный состав участников итогового турнира TCO.
Онсайд-раунд состоит из полуфинала и финала. На полуфинале участники разбиваются на 3 "комнаты" по 24 человека, по 3 победителя из каждой "комнаты" попадают в финал. А участники, занявшие 4-5 места в "комнате" (всего 6 человек), разыгрывают 1 дополнительную путевку в финал. Там из этих 10 человек и определяется чемпион мира, который получает денежный приз в 25000 USD. За последние годы чемпионом всегда, когда участвовал, становился все тот же П.Митричев. Из ижевских ребят в 2005 году в полуфинале 15 место занял тоже не менее легендарный Н.Пермяков. И вот сейчас в Лас-Вегас собирается А.Скиданов, имея на сегодняшний день 14-й рейтинг среди всех приглашенных. В предстоящем онсайт-раунде 14 участников представляют Россию, 6 - Украину, по одному - Грузию и Латвию. Окончательный список участников будет сформирован после решения визовых вопросов.
MicroSoft Imagine Cup - соревнование по программированию под эгидой компании MicroSoft для продвижения и рекламы ее программных продуктов.
Существует международный чемпионат серии Microsoft Imagine Cup Algorithm и Российский. Различаются они, естественно, списком участников и схемой проведения полуфинала.
Первый отборочный тур это - проект Herbert (программирование робота). Проводится он в 4 раунда, участвовать можно в любом из них. Проходной рейтинг формируется по лучшим результатам всех раундов, а в следующую стадию переходят 50 первых для Российского и 200 - для международного чемпионата. В этом сезоне отборочный тур в Российском Imagine Cup прошли все три члена нашей первой сборной команды - А. Скиданов, В. Камашев и Е. Кузяков. А вот для продолжения участия в международном чемпионате последнему баллов не хватило.
Далее для Российского Imagine Cup проходит полуфинал в форме контеста аналогичного ACM. Правда, задачи там формулируются строго математически без всякой "сказочной" атрибутики. Из наших программистов этот этап с успехом (1 и 6 места) прошли А. Скиданов и В. Камашев. Теперь им предложено участвовать на финале в Москве (очная стадия).
Полуфинал международного чемпионата Imagine Cup проводится по другой схеме. Участникам предлагается за 2 месяца решить задачу, которую в ACM принято считать "гробом" - т.е. имеющую крайне сложное решение. В этом сезоне решения можно представлять до 4 мая. А дальше 6 счастливчиков едут на финал в Париж.
На финале (как Российском, так и международном) предлагается за 24 часа решить несколько задач в формате школьной олимпиады - т.е. каждое предложенное решение проходит проверку на ряде тестов. За каждый пройденный тест начисляются некоторые баллы. Не обязательно пройти все тесты. Победитель определяется по наибольшему числу набранных баллов. А дальше награждение и подарки от спонсоров.