Cоревнования по спортивному программированию

С программированием связано много приятного. Мастерство приносит свои маленькие радости — удовлетворение от того, что ты сделал что-то полезное и оно работает. Возбуждение, приходящее от внезапного озарения, позволившего решить упрямую задачу. Стремление к элегантности, которое превращает кодера в художника. Приятно выжимать последние капли производительности из умных алгоритмов и экономичного кода. Решение задач с международных состязаний по программированию — замечательный способ испытать все это, параллельно изучая новые алгоритмы и шлифуя свое умение писать программы [2].

В настоящее время «олимпиадное программирование» переживает настоящий бум среди студентов и школьников. Тому есть множество причин. Перечислим наиболее важные из них.

1. Программирование — чрезвычайно увлекательная сфера деятельности, в то же время обеспечивающая достойный уровень оплаты труда во всем мире, в том числе и в странах СНГ. Последнее связано со стремительной компьютеризацией всех сфер жизнедеятельности человека и открытием крупнейшими фирмами (Intel, IBM, Motorola и т. д.) центров исследований и коммерческих разразработок в области программного обеспечения на территории России, Беларуси и других стран СНГ.

2. При изучении программирования и других компьютерных наук молодой человек получает «конвертируемые» знания, позволяющие ему работать не только на родине, но и практически в любой стране мира.

3. Олимпиады по программированию для студентов и школьников имеют более чем двадцатилетнюю историю. При этом высокие результаты предыдущих поколений студентов и школьников стимулируют занятие олимпиадным программированием все новых и новых молодых людей.

Приведем только несколько цифр. С 1997 года Россия была представлена на Международной олимпиаде школьников по информатике (International Olympiad in Informatics, IOI) тридцатью двумя школьниками (восемь олимпиад, по 4 школьника в команде на каждой олимпиаде). Все эти школьники завоевали медали, причем подавляющее большинство — золотые или серебряные. Аналогичный результат имеет только одна страна в мире — Китай. С 1996 года вузы России и других стран СНГ начали принимать участие в командном студенческом первенстве мира по программированию, проводимом под патронажем ACM (Association for Computing Machinery) — одной из крупнейших и старейших ассоциаций компьютерных профессионалов. Результаты и здесь выглядят впечатляюще. В течение последних шести лет команды Санкт-Петербургских вузов (СПбГУ и СПбГУТМО) трижды становились чемпионами мира по программированию. При этом в финале 2005 года второе, третье и девятое места (а в финале 2004 года — первое, четвертое и восьмое) были заняты командами российских вузов. Такими стабильно высокими результатами своих студентов не может похвастаться ни одна страна в мире.

Понятно, что эти успехи достигнуты благодаря педагогическим кадрам Санкт-Петербурга, Москвы, Саратова, Нижнего Новгорода, Ижевска, Петрозаводска, Перми и других городов России. В них знания передаются «изустно» от ведущих преподавателей к олимпиадникам, а также от одного поколения олимпиадников к другому. В то же время во множестве городов России и других стран СНГ наблюдается острейшая нехватка как педагогических кадров, так и литературы по подготовке к олимпиадам и решению сложных олимпиадных задач по программированию для студентов и школьников, — и это на фоне огромного интереса к олимпиадам со стороны школьников, студентов и преподавателей. Достаточно сказать, что в 2004 году за право попасть в Северо-Восточный полуфинал студенческого первенства мира по программированию (NEERC) в четырнадцати (!!!) четвертьфиналах соревновалось более 630 команд более чем из 210 вузов. Сопоставимы по числу участников в олимпиадах и соревнования для школьников по информатике [1].

Зачем и что делают на этих олимпиадах?

Решают задачи. Все задачи по-настоящему интересны. Они связаны с увлекательными темами из теории вычислительных систем и математики, что нередко скрыто за забавной историей. Известно, что люди, практика которых состоит в прикладном программировании и разработке программного обеспечения, часто недооценивают мощь, предоставляемую алгоритмами. Аналогично теоретики обычно не понимают, что нужно для того, чтобы алгоритм стал программой, и насколько сильно грамотное программирование может облегчить решение сложной задачи [2].

ACM International Collegiate Programming Contest

ACM International Collegiate Programming Competition (ACM ICPC) — это мероприятие, где студенты, интересующиеся программированием, показывают, на что они способны. Число участников, интересность и престижность ICPC постоянно возрастали со времени его основания в 1976 году. Соревнование 2002 года собрало 3082 команды (из трех человек), представляющие более 1300 учебных заведений из 67 стран, плюс огромное число студентов, участвующих в аналогичных местных состязаниях и сетевых олимпиадах по программированию.

Формат состязания выглядит так. Каждая команда состоит из трех человек, которым предлагается решить от пяти до десяти задач по программированию. Команде предоставляется только один компьютер, так что координация и работа в команде жизненно важны.

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

Работа в команде

По правилам ICPC команды состоят из трех человек. Так как доступен всего один компьютер, командная работа играет основную роль. Команды, которые спорят из-за того, кто будет сидеть за машиной, никогда не выигрывают. Жу Ян из Shanghai Jiaotong University (чемпион мира 2002 года) формулирует это так: «Все, что вы делаете, должно быть подчинено одной цели — принести больше пользы команде, а не себе одному».

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

Конечно, по ходу соревнования студенты могут меняться ролями, да и сами роли от команды к команде могут сильно изменяться. Некоторые команды выбирают капитана, который решает, кто какой задачей занимается и кто в какое время работает с компьютером.

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

International Olympiad in Informatics

International Olympiad in Informatics (IOI) — это ежегодное соревнование по информатике для школьников среднего/старшего звена. С момента своего основания в 1989 году, оно выросло до второй по величине из пяти международных олимпиад по научным дисциплинам, уступая только математике. В 2002 году 78 стран отправили 276 участников на финал, проходивший в Корее, но эти финалисты выбирались буквально из сотен тысяч учеников, желающих попасть в команду своей страны. Цели IOI немного отличаются от целей ACM ICPC. Участники еще не выбрали свою карьеру; цель IOI — повысить их интерес к информатике (компьютеристике). На IOI собираются вместе талантливые школьники из разных стран, и там они могут поделиться культурным и научным опытом друг с другом.

Участие

IOI каждый год проводится в разных странах: Висконсин, США, в 2003 году; Греция в 2004 году и Польша в 2005 году. Каждая страна, принимающая участие, отправляет команду, состоящую из четырех учеников и двух тренеров. Школьники соревнуются по отдельности и пытаются набрать максимальное число очков, решая некоторое число задач по программированию на протяжении двух дней. Обычно им дается пять часов на три задания в каждый из двух дней.

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

USA Computing Olympiad поддерживает замечательную программу тренировки по адресу http://train.usaco.org и проводит соревнования по программированию через Интернет, в которых может принимать участие любой. Чтобы у вас была возможность попасть в команду США, вы должны принять участие в U.S. Open National Championship. Для этого требуется разрешение учителя в вашей школе. Участники, показавшие лучшие результаты, приглашаются на сборы для дополнительной тренировки и формирования команды. В Канаде примерно из 1000 кандидатов с помощью отборочных экзаменов выбираются 22 для дополнительной недельной тренировки на сборах.

Формат

В отличие от ACM ICPC на олимпиаде принимаются не полностью решенные задачи. Для каждой задачи обычно имеется десять наборов входных данных, и за каждый решенный верно вы получаете 10 очков. Если каждый день дается по три задачи, то максимальное количество очков равно 600.

Все задачи (называемые заданиями (tasks) на жаргоне IOI) предполагают вычисления алгоритмического плана. Даже в том случае, когда требуется алгоритмическая эффективность, организаторы стараются подобрать хотя бы один набор входных данных, на котором неэффективные программы смогли бы получить очки. Но член IOI Scientific Member Ян Манро (Ian Munro) говорит: «Тяжело придумывать такие задания, чтобы они оказались несложными для большинства участников, но при этом позволяли бы нам четко понимать, кто же все-таки победил».

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

На соревнованиях 2002 года участникам предлагалось выбрать Linux или Windows в качестве среды программирования. Из языков программирования можно было использовать Pascal или C/C++. Участникам не разрешается пользоваться любыми печатными или сетевыми материалами.

Результаты решений сообщаются после того, как закончилось время, отведенное на решение заданий, а не «в оперативном режиме», как принято на АСМ ICPC. Как и в обычном школьном экзамене, участники не знают количество набранных ими очков до момента объявления оценок.

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

Topcoder.com

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

Примерно так появилась TopCoder — компания, использующая соревнования по программированию для поиска многообещающих работников и предоставляющая эту информацию своим клиентам. Главная приманка соревнования — деньги. Состязание 2002 года TopCoder Collegiate Challenge спонсировалось Sun Microsystems, и призовой фонд был порядка 150 000$. Даниель Райт из Stanford University легко выиграл главный приз в 100 000$ и согласился поделиться с нами своими секретами.

TopCoder поддерживает отличный сайт (www.topcoder.com), на котором размещаются новости о последних соревнованиях, что делает его похожим на ленты спортивных новостей. Также на сайте проводятся тренировочные соревнования, помогающие готовиться к еженедельным турнирам, каждый из которых состоит из трех задач по программированию. Такие турниры начали проводиться с 2001 года, и с этого времени более 20 000 программистов зарегистрировалось в качестве их участников. На сегодняшний день TopCoder выплатил порядка 1 000 000$ призовых денег.

Формат соревнований TopCoder быстро меняется, так как они подбирают наиболее подходящую деловую модель. Предварительные раунды проводятся по сети, а финальные этапы больших соревнований проходят вживую.

В основе каждого из таких этапов лежит схожая структура. Программисты делятся на «комнаты», где они соревнуются с другими участниками. Каждый раунд начинается с фазы программирования (coding phase), длящейся 75-80 минут, в течение которых участники решают задачи. Количество очков за каждую задачу обратно пропорционально отрезку времени между получением задачей и ее отправкой. Далее следует 15-минутная фаза проверки (challengephase), в течение которой программисты могут просматривать решения других участников и искать в них ошибки. За отправку варианта входных данных, на которых валится чужая программа, участник получает дополнительные очки. Частично решенные задачи не засчитываются.

Большинство участников обычно решают задачи в порядке возрастания сложности, хотя Райт предпочитает делать сначала те задачи, за которые дают больше очков, если, по его мнению, времени на все три ему не хватит. На TopCoder разрешается повторная отправка, ценой временного наказания, так что есть определенная стратегия при принятии решений, когда отправлять задачу и когда тестировать. Временной фактор — самый важный на соревнованиях TopCoder. Чтобы работать быстрее, Райт рекомендует участникам изучать и эффективнее использовать стандартные библиотеки.

Фаза программирования обычно более важна, чем фаза проверки, потому что число очков, набираемых на чужих ошибках, недостаточно велико, чтобы компенсировать разницу в задачах. Чтобы спланировать свою работу в эту фазу, Райт бегло просматривает решения, чтобы понять, как работает предложенный алгоритм. Если он находит вариант, который он рассматривал, но отбросил, как неверный, то имеет смысл попробовать уронить эту программу. Чаще он находит опечатки и ошибки занижения/завышения на единицу [2].

О себе

К величайшему сожалению, я узнал о существовании чего-то подобного только под конец второго курса и начал интенсивное изучение с начала третьего курса (учебная программа, лишь вскользь касается некоторых из тем, знание которых необходимо). В период 2006-2007 наш университет был представлен двумя командами. О составе первой (она достигла значительных результатов) можно прочесть на странице Игоря Бабенко. Состав второй 2006: Иван Трофименко, Иван Машей, Иван Беликов; 2007: Иван Трофименко, Дмитрий Шкурский, Иван Беликов. Весной 2006 вторая команда заняла 20-е место в 1/8 финала. Весной 2007 вторая команда заняла 10-е место в 1/8 финала. Надеюсь, что будут приняты меры по устранению сложившейся ситуации (для достижения результатов, согласно [2] необходимы тренировки минимум три раза в неделю)

С чего начать

Надеюсь, я вас заинтересовал, и вы приступите к изучению этой интереснейшей области. Думаю, лучше всего начинать с книги [3]. Она поможет сдвинуться с мертвой точки. В книге содержатся задачи с решениями и проверяющей системой, что позволяет работать самостоятельно. Решив задачи, предложенные в [3], можно прочесть одну из книг [1,2,4] (в книгах описан базовый набор алгоритмов, знание которых необходимо для решения задач). Трехтомник Д. Кнута, который все напропалую предлагают прочесть, мне читать было трудно, так что начинать с него не рекомендую. В Интернет доступно множество сайтов с описанием различных алгоритмов. С их помощью можно быстро добиться результата, тем не менее, такие источники не дают понимания сути, которое необходимо для решения более сложных задач. С другой стороны, там можно почерпнуть много информации о том, какие алгоритмы существуют. Отличной книгой является [5]. В ней описан широкий спектр алгоритмов и рекомендации по дальнейшим направлениям движения.

Литература

1. Долинский М. С. Решение сложных и олимпиадных задач по программированию: Учебное пособие. — СПб.: Питер, 2006. — 366 с: ил.
2. Скиена С. С, Ревилла М. А. Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям / Пер. с англ. — М: КУДИЦ-ОБРАЗ, 2005. — 416 с.
3. Меньшиков Ф.В. Олимпиадные задачи по программированию. — СПб.:"Питер", 2006. — 315 с.
4. Ставровский А.Б., Порублев И.Н. Алгоритмы и программы. Решение олимпиадных задач. — Вильямс, 2006. — 480 c.
5. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ. — Вильямс, 2006. — 1296 с: ил.