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

Немного истории

Командные чемпионаты мира по программированию (ICPC, International Collegiate Programming Contest) проводятся ежегодно под эгидой американской Ассоциации по вычислительной технике (ACM, www.acm.org ), которая наряду с IEEE Computer Society и British Computer Society входит в тройку ведущих профессиональных компьютерных ассоциаций мира и объединяет в своих рядах свыше 80 тысяч ИТ специалистов из разных стран мира. С 1977 года по 1989 год эти состязания были внутриамериканскими, с 1990 года в них стали принимать участие европейские команды, а затем и представители других континентов, что позволило повысить статус соревнований и называть их чемпионатами мира ACM-ICPC World Championship (icpc.baylor.edu/icpc/). Российские команды получили возможность участия в региональных полуфиналах с 1993 года. Программисты ИжГТУ включились в эти соревнования в 1996 году, заняв  в полуфинале 30 место среди 52 команд-участников.

Выход в финальную стадию для команд России и некоторых стран ближнего зарубежья лежит через успешное выступление в полуфинале Северо-Восточной региональной группы NEERC. В разные годы представительство на финал составляло  от 10 до 12 команд, причем каждый вуз может быть представлен только одной командой.

Высшими достижениями ИжГТУ в полуфиналах были 10 место (сезон 2003-2004) и 13 место (сезон 2004-2005), что обеспечило нашим студентам поездку в Прагу и Шанхай, откуда оба раза они вернулись с медалями, заняв соответственно 8 и 9 места: на чемпионате мира с 2003 года за 1-4 места команда награждается золотыми медалями,  за 5-8 места  - серебряными и 9-12 - бронзовыми.

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

Тренер

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

В системе спортивного программирования Владимир Георгиевич последовательно поднимается со ступеньки на ступеньку. Успехи его воспитанников привели к тому, что его уже в лицо знает Билл  Пучер (главный организатор финальных турниров). С 2005 года В.Г. Тарасов зарегистрирован как руководитель регионального центра для проведения on-line этапов Открытого Кубка России по программированию ACM, в соответствии с чем на базе ИжГТУ проведены этапы сезона 2006-2007, а сейчас проходят этапы сезона 2007-2008 с участием команд ИжГТУ и УдГУ.

Под руководством Владимира Георгиевича силами нескольких поколений программистов-олимпиадников  разработано собственное специализированное программное обеспечение для проведения разнообразных турниров (тренировочных, отборочных и пр.). Ныне действующая система BACS, созданная в первую очередь благодаря Руслану Ковычеву и Алексею Кузякову (оба в прошлом медалисты чемпионатов мира) - вполне конкурентоспособная и удобная программная среда, на базе которой в 2006 году осуществилась давняя мечта нашего тренера - провести школу-семинар по программированию, куда были приглашены команды нескольких факультетов и филиалов университета. Как развитие этой идеи, сегодня в планах Владимира Георгиевича - проведение на базе ИжГТУ тренировочных сборов сильнейших команд Уральского региона (подобные сборы, проходящие в Петрозаводске, стали традиционными и включены в официальный календарь ACM ICPC).

Результаты

Оценивая результаты последнего полуфинала, всегда скромный на похвалы своим воспитанникам Владимир Георгиевич сказал: "Турнир для нас сложился удачно. Ребята правильно определили порядок задач. Хорошо отработали и не "провалили" последнюю половину".

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

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

Вообще, задача на соревнованиях формулируется в форме детективной истории с популярными в студенческой среде персонажами книг, кинофильмов или игр. Занимает это описание 1-2 машинописных листа и выполнено на английском (!) языке. Поэтому первый этап - отсечь лишнее и свести все к понятно сформулированным математическим классам задач. Кстати, именно этот этап крайне напрягал даже такого непревзойденного лидера наших программистов, как Руслан Ковычев.

Определенным подспорьем при выборе задачи может служить такая косвенная информация, как анализ текущих результатов других участников. Эти сведения команды, как и зрители, в том числе пользователи Internet, получают через оперативно меняющуюся турнирную таблицу ("монитор"). Правда, в последний час состязаний информация на нем остается неизменной ("замораживается"), и участникам остается надеяться либо только на себя, либо (как это принято на финалах) - на визуальное сопровождение: за каждую решенную задачу к столу команды организаторами вывешивается воздушный шарик определенного цвета. И тогда, когда монитор заморожен, по количеству и цветам привязанных шариков можно получить сведения о решенных командой задачах. Правда, шарики появляются у столов команд с определенной задержкой и не отражают информации о неудачных попытках решения той или иной задачи.

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

О команде

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

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

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

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

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

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

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

Интересно, что недавно, подобно многим другим командам, и наша, помимо официального названия, "обзавелась" неофициальным именем - сейчас полное наименование звучит Izhevsk STU # 1 GodLike Team.  Для сравнения ­- названия некоторых команд-участниц финала текущего сезона: Белорусский ГУ - Belarussian SU 3AbEVI,  С-Петербургский ГУ - SPb SU # 1 Burunduchki, МГУ - Moscow SU # 2 Crazy SEx13, Орловский ГТУ - Orel STU # 1 Encore,  Уральский ГУ - Ural SU # 1 Fusion). Знающие английский язык понимают, что такое название, несмотря на его шутливую тональность, накладывает на ребят некоторые обязательства перед своими болельщиками.

Прогнозы на финал

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

Несколько лет назад наш университет, если честно, оказался немного не готов и растерян, когда из Праги программисты вернулись с первыми медалями - их успех в тот год по достоинству оценили, пожалуй, только в Кремле, куда команда была приглашена на встречу с В.В. Путиным. Там всем участникам встречи подарили по ноутбуку, а накануне в Минвузе - по цифровому фотоаппарату. Год спустя вернувшиеся из Шанхая ребята уже стали пристальным объектом внимания как внутри вуза, так и в республике. Затем внимание распространилось на нынешнюю команду. Это приятно и в то же время ко многому обязывает: слишком уж нам всем хочется, чтобы каждая поездка на финал Чемпионата мира заканчивалась медалями. Хотя уже сам факт - быть в числе лучших  80-и команд вузов всего мира -  уже большой успех.

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

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

А на предстоящем финале ребят ждет еще одна техническая новинка. Буквально на днях команда познакомилась со средой разработки, которая будет предложена на финале - Eclipse, тогда как на всех предыдущих этапах чемпионата этого сезона использовалась более привычная для участников Microsoft Visual Studio 2007. По общему мнению команды, Eclipse не слишком удобен и не очень привычен, поэтому часть оставшегося до начала соревнований времени придется посвятить привыканию к новой среде.

По традиции финал проходит в начале апреля. В Шанхае Саша Скиданов в подарок на свой день рождения (6 апреля) преподнес бронзовую медаль. Предстоящий финал в Канаде тоже совпадает с личным праздником Александра. Посмотрим, как все сложится в этот раз.

Мечты тренера

Когда Владимир Георгиевич показывает фотографии с финала в Праге (2004 год), он каждый раз оправдывается - руки почему-то (?) дрожали. Фотографии, сделанные тренером год спустя в Шанхае, уже разнообразнее и довольно четкие - вероятно, признак повышения уверенности тренера в силе своей команды.

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

Пожелаем ему и команде успехов в осуществлении как перспективных, так и ближайших планов!

 

Ссылки по теме:

Сайты кафедры "Программное обеспечение" ИжГТУ:  http://cs.istu.ru и http://bacs.cs.istu.ru

Сайты чемпионата мира по программированию:  http://icpc.baylor.edu/icpc,  http://neerc.ifmo.ru/information,   http://acm.usu.ru

Командный чемпионат мира по программированию ACM 2004-2005. Северо-Восточный Европейский регион. /Под ред. проф. В.Н.Васильева и проф. В.Г.Парфенова - Санкт-Петербург: СПбГУ ИТМО, 2004.

Руслан Богатырев. Нас не догонят? // Мир ПК, 2005 г. ? 5