АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

Программисткое многоборье

• Все журналы \ Номер 30/253 `2003 от 21.07.2003 \ Программисткое многоборье

Владимир ТКАЧУК vova.tkachuk@ua.fm

Среди любителей программирования часто встречаются люди, которым хотелось бы сравнить себя с другими программерами и в честном соревновании продемонстрировать свое мастерство. Следует отметить, что это куда лучше, чем самовыражаться написанием троянов и прочих вирусов. К сожалению, для многих школьные годы уже миновали, а с ними миновала и возможность участия в IOI (International Olympiads in Informatics). Но не стоит сильно расстраиваться, ведь кроме школьных есть еще и студенческие олимпиады (см. статью «Информатики всех стран, соревнуйтесь!», МК № 40 (211)). О них и пойдет речь в этой статье.

Довольно часто от бывалых олимпиадников мне доводилось слышать: «Да ну его, в ВУЗе это совсем не то…». Верно, все немного по-другому, но это вовсе не означает, что студенческие олимпиады хуже школьных. Просто основной акцент смещен в сторону практического программирования: если школьники основную часть олимпиадного времени тратили на решение сложных идеолгических задач по информатике, то, например, на открытой олимпиаде Национального Технического Университета Украины «КПІ» одной из задач было написание игры «Теннис». И еще одно различие. Школьными олимпиадами занимается непосредственно Министерство образования, тогда как проведение студенческих олимпиад берут на себя отдельные университеты и организации. Соответственно, и представление о том, каким должно быть соревнование, у каждого организатора свое. Некоторые пытаются сделать олимпиаду как можно более общей, для чего сознательно дают задачи из совершенно разных областей программирования. Такой подход иногда вызывает нарекания участников, так как не совсем понятно, как готовиться к такой олимпиаде, ведь всего, как известно, знать нельзя. Но чаще организаторы делают акцент на определенной теме, так, на ICP олимпиадах (International Competition in Programming), которые до недавнего времени проводились в чешском городе Брно, от участников требовалось в короткие сроки создать готовый программный продукт, отвечающий определенным критериям. В принципе, подобных олимпиад довольно много, и их тематическая направленность варьируется от программирования компьютерной графики до реализации технологий защиты информации. Но все же на данный момент самыми престижными и массовыми олимпиадами по программированию являются соревнования, проводимые организацией ACM (Association of Computer Management). Обычно, говоря про студенческие олимпиады, чаще всего подразумевают именно эти соревнования. Соответственно, они заслуживают более внимательного рассмотрения.

Играем по правилам

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

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

Наиболее интересным является принцип интерактивности судейства. Если в большинстве олимпиад участник сначала какое-то время решал поставленные задачи, затем все наработанное им проверялось и, наконец, сообщался его результат, то в варианте ACM программа проверяется сразу же, как только команда заявляет о ее готовности. Результат сообщается участникам немедленно после проверки (проверка одной такой программы редко длится дольше нескольких минут). А результаты могут быть следующими: Accepted — программа прошла все тесты в отведенное время, Wrong result — на каком-то из тестов программа выдала неправильный ответ, Time limit — на каком-то тесте программа работала слишком долго, Run-time error — программа дала сбой во время работы, Compilation error — жюри не удалось откомпилировать программу (на проверку команда подает исходный код, написанный на одном из заявленных языков программирования). Разумеется, хорошим результатом является лишь Accepted, остальные сообщения призваны помочь участникам найти ошибку в их решении.

Победителем считается та команда, которая решила больше всего задач. Если же несколько команд решили одинаковое количество задач, то роль играет количество набранных за игру штрафных очков. Штраф команде насчитывается следующим образом: как только она удачно сдала какую-то задачу, к ее штрафу прибавляется время, что прошло от начала олимпиады до момента сдачи программы. Если до этого команда сделала несколько неудачных попыток сдать эту же задачу, то за каждую неудачу команду дополнительно штрафуют на 20 минут. То есть, если команда сдала две задачи: одну со второй попытки на 25-ой минуте, а другую на 50-ой минуте олимпиады, то ее штраф будет равен 25+20+50 = 95. Среди команд с одинаковым количеством решенных задач победителем считается та команда, суммарный штраф которой меньше. Для минимизации своего штрафа участники должны решать задачи как можно быстрее и без ошибок.

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

Региональное деление

Система ACM олимпиад — глобальная, она охватывает все континенты и страны мира. Разберемся с ее иерархией последовательно, снизу вверх. Так как олимпиада является студенческой, то и команды выступают не от имени конкретных городов или стран, а от имени своих учебных заведений.

Итак, первый, необязательный этап соревнований — внутриуниверситетская олимпиада. На этом этапе высшее учебное заведение определяет, какая команда будет представлять ее на последующих олимпиадах. Как ни странно, но для команд некоторых традиционно сильных вузов (например, Московского Государственного Университета), это первое соревнование является чуть ли не самым сложным. Далее следует олимпиада с участием команд от университетов определенного региона страны: Украина поделена на четыре таких региона.

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

В принципе, все вышеописанные этапы непосредственно ACM не курируются, эта организация занимается проведением международных соревнований: региональных олимпиад и мирового финала. Украина вместе с такими странами, как Румыния, Болгария, Молдова и Греция принадлежит к Юго-восточному Европейскому региону, финал которого проходит в Бухаресте. Для того, чтобы попасть на это соревнование, даже не обязательно принимать участие в украинских олимпиадах, свою команду может прислать любой вуз данного региона. Но лучшим трем командам украинского чемпионата Министерство образования нашей страны оплачивает участие в финале региона, за остальных желающих должны заплатить их университеты.

По результатам регионального соревнования несколько команд попадают на финал мира (количество команд, прошедших в финал, зависит от размера региона: если из Юго-восточной Европы едет максимум две, то регион, в который входит Россия, посылает на финал аж восемь команд). На финальном соревновании мира сильнейшие команды со всех континентов борются за обладание главным призом — серебряным кубком ACM, а также за солидные денежные вознаграждения. Место проведения финала постоянно меняется: так, в прошлом году это был Гонолулу (Гавайи), в этом — Голливуд, в следующем году финал пройдет в Праге (Чехия).

Наши достижения

До недавнего времени, несмотря на активность украинских команд на региональных соревнованиях, случаи участия наших команд в финале мира были крайне редкими. Каждый год до десяти вузов Украины присылали своих участников в Румынию, и только одна команда факультета Кибернетики Киевского Национального Университета единственный раз прошла на финал. В этом году ситуация кардинально изменилась: четыре наши команды попали в призовую десятку соревнования региона, причем команды от КНУ и КПИ заняли соответственно первое и второе место. Для нас это очень значительный успех, ведь, обыграв традиционных победителей румын и болгар, на мировой финал попали команды двух украинских вузов. Итак, в Голливуде нашу страну представляли участники от факультета Кибернетики КНУ им. Тараса Шевченко и от Физико-технического института при НТУУ «КПІ».

Несколько слов об уровне проведения соревнования. Основным спонсором финалов мира является корпорация IBM, а значит, все было сделано по высшему классу. Участники проживали в престижном отеле Beverly Hilton, где, кстати, в это же время жили такие звезды американского кино, как Арнольд Шварцнегер и Антонио Бандерас.

Компьютеры участников (которые, к слову, были оснащены 19” TFT мониторами) работали под управлением операционной системы Linux, а программировать разрешалась на следующих языках: Pascal, C++ (в качестве среды разработки предлагался Borland Kylix) и Java.

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

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

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

Если вы хотите больше узнать про ACM систему и посмотреть условия задач, рекомендую вам посетить официальный сайт олимпиады http://acm.baylor.edu.

Идёт загрузка...

Данную страницу никто не комментировал. Вы можете стать первым.

Ваше имя:
Ваша почта:
Комментарий:
Введите символы или вычислите пример: * Обновить