13.03.2008 17:10 Елена Шевякова
Печать PDF
ImageВ аналитическом материале Елены Шевяковой рассматриваются тонкости спортивного программирования: помимо интервью с лидером команды Izhevsk STU #1 Александром Скидановым, он содержит подробные комментарии о соревнованиях по программированию всех видов.

Незадолго до начала Чемпионата мира по спортивному программированию среди студенческих команд по версии ACM мы побеседовали с Александром Скидановым - лидером наших программистов. Беседа касалась не столько наших шансов на финал - зачем искушать судьбу произнесенными вслух словами? - сколько других нюансов, связанных со спортивным программированием.

- Саша, а где работают лучшие спортсмены-программисты нашей страны после завершения спортивной карьеры?

- Мечта многих - работа в компании Google. Там есть сложные алгоритмические задачи, похожие на те, которые нам предлагают на наших соревнованиях. Конечно, можно в Яndex или mail.ru, но это наши российские компании, a Google - мировая марка. Там, кстати, и Петя Митричев работает. И многие другие ребята тоже.

- А у тебя в перспективе тоже такие планы?

- В целом, да. Если не Google, то центральный офис MicroSoft. Просто хотелось бы работать профессионально и без переучивания. А, скажем, в Samsung я буду такой же как все начинающие.

Но это, конечно, потом. А в этом сезоне я поставил себе сверхзадачу - "выжать" максимум из спортивных соревнований по программированию - и финал ACM в Канаде, и Topcoder Open и Imagine Cup (см. комментарий). Это решение пришло ко мне год назад. Тогда, после неудачи в полуфинале ACM, команда фактически распалась. И я долго делал для себя выбор: продолжать тренировки или согласиться на предложение поступать в магистратуру ИТМО (С.-Петербург). Они как раз набирали олимпиадников и с жильем проблемы обещали решить вполне нормально. С нашего потока тогда Кирилл Тимофеев уехал. А я вот остался - решил еще раз попытаться пробиться на финал ACM. Получилось.

Правда, я подозреваю, что после Канады наступит депрессия, но это еще впереди.

- ?!

- А как Вы думали? Конечно, не сразу, месяца через два. Просто окончание спортивной карьеры сразу лишит меня цели нескольких последних лет жизни. А без цели как вообще жить?

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

А когда финал ACM пройдет, тренироваться по 5 часов 6 раз в неделю будет уже не надо, да и с Женей соревноваться тоже - что останется? Одна надежда - на финалы TopCoder Open и Imagine Cup Algorithm (это, между прочим, Лас-Вегас и Париж).

- А какие шансы у команд ИжГТУ на следующий сезон?

- В первую очередь пока это будет зависеть от Жени. Если он не "забьет" на тренировки и будет дисциплинирован (как в свое время Руслан, когда ушел Коля) или найдет себе достойного нового спаринг-партнера, результат будет.

А вот что касается остальных наших команд, то их еще надо "разбудить". Сегодня они, обладая очень неплохими способностями, как-то вяло тренируются. Отсюда и результат. Точнее, его отсутствие.

- Чемоданы уже собраны?

- Почти. Кстати, в Канаду мы едем сразу же после Екатеринбурга, где планируем выступить на Чемпионате Урала (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 проводит несколько турниров в различных областях программирования, по итогам которых формируется мировой рейтинг стран и отдельных личностей. Сегодня среди 20 лучших разработчиков ПО 18 мест принадлежат китайцам. А вот в алгоритмическом рейтинге картина для нас более благоприятная - возглавляют его представители России (П. Митричев, Е. Куликов, А. Станкевич) и Польши (среди которых один из участников предстоящего финала ACM и чемпион мира-2007 Marek Cygan).

В конкурсе алгоритмов 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 часа решить несколько задач в формате школьной олимпиады - т.е. каждое предложенное решение проходит проверку на ряде тестов. За каждый пройденный тест начисляются некоторые баллы. Не обязательно пройти все тесты. Победитель определяется по наибольшему числу набранных баллов. А дальше награждение и подарки от спонсоров.

Российским программистам повезло на международных Microsoft Imagine Cup Algorithm дважды, причем оба раза (в разные годы!) это были ребята из Иваново, причем из разных вузов. Как это возможно - понять трудно, но факт остается фактом. Легенда спортивного программирования нашего времени П. Митричев пока желания участвовать в этих соревнованиях никак не обозначал, как и другие российские знаменитости (А.Станкевич, например).
Обновлено 13.03.2008 17:40
You are here:   ГлавнаяРазделы сайтаЭкспертизаЭкспертизаЗвездный сезон Александра Скиданова
| + -

Наши партнеры

Ижевский государственный технический университет Бизнес-инкубатор ИжГТУ имени М.Т. Калашникова Нанотехнологии в Удмуртской Республике Факультет  информатики Кубанского государственного аграрного университета Мир инноваций ВЫПУСКНИКИ ИМИ-ИжГТУ Джаз-оркестр ИМИ-ИжГТУ Спортлагерь ИМИ-ИжГТУ «Галево» Литературное объединение (ЛИТО) ИжГТУ «Прикосновение»