eSci.Ru logo
Данный ресурс создан для поддержания извечного стремления человека к сияющим вершинам разума
Главная > Статьи > Пламя сетевых олимпиад. TopCoder
Пламя сетевых олимпиад. TopCoder

Пламя сетевых олимпиад. TopCoder

Автор: Остапенко Денис aka Sharp

E-mail: sharp-c@yandex.ru

В конце весны — начале лета 2006 года сетевая общественность гудела, обсуждая радостную новость — россиянин Петр Митричев, студент мехмата МГУ, выиграл на TopCoder Open, ежегодном состязании, которое неофициально считается Чемпионатом Мира по программированию. Что же собой представляет TopCoder и почему он так популярен в мире? Из этой статьи вы узнаете об этом.

TopCoder?

Что такое TopCoder (http://www.topcoder.com)? Это сообщество программистов (а в последнее время еще и дизайнеров), образованное в 2001 году и в настоящее время насчитывающее уже более 100 тысяч участников, которые регулярно соревнуются в разных отраслях своих профессий. К примеру, это Component Design & Development Competitions, целью которых является проектирование и написание программных компонентов для различных фирм, использующих аутсорсинг в своих разработках, обычно на языке Java или .NET, за вознаграждение, предоставляемое этими фирмами. Это так же и TopCoder Studio, которая предлагает дизайнерам принять участие в соревновании на самый лучший дизайн, логотип и т.п., разумеется, с солидными призами. В этой статье мы рассмотрим Algorithm Competitions, которые наследуют традиции школьных олимпиад по информатике и, в особенности, ACM (Association of Computer Machinery) — студенческих олимпиад по программированию. Такие олимпиады проверяют умение логически и алгоритмически мыслить, предъявляют серьезные требования к профессиональной и математической подготовке.

Посмотреть на график соревнований этого месяца всегда можно по ссылке http://www.topcoder.com/tc?module=Static&d1=calendar&d2=thisMonth. Обычно каждый месяц TopCoder проводит около 20 соревнований, из которых примерно половина по алгоритмическому программированию.

ACM?

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

Система TopCoder похожа на систему ACM с несколькими модификациями, которые лучше подходят к небольшому комплекту задач, который можно предложить на коротких соревнованиях, устраивающихся часто. Во-первых, число правильно решенных задач не является определяющим — можно быстро сдать только одну задачу, за которую дают больше баллов и выиграть тех, кто будет решать пусть даже большее число задач, но, допустим, дольше, отчего и наберут меньше баллов. Вместо начисления штрафного времени, из баллов участника за пересдаваемую задачу вычитается 10%.

Рейтинг

Из баллов участника и его многочисленных конкурентов во многих соревнованиях по очень сложной зависимости строится его рейтинг. Нынешний чемпион TopCoder Петр Митричев 2 февраля 2007 года имел рейтинг 3524. Участники с разным рейтингом имеют цветовую дифференциацию, подобную системе цветов штанов в фильме «Кин-дза-дза». Участники с нулевым рейтингом (которые не участвовали ни в одном соревновании) имеют белый цвет; обладающие рейтингом от 1 до 899 — серый; от 900 до 1199 идет зеленый цвет; от 1200 до 1499 — синий, от 1500 до 2199 — желтый, а выше 2200 баллов расположен красный цвет, заветная мечта любого топкодеровца. Причем те, кто его не имеют, мечтают его получить, а те, кто имеет — не потерять. Участников с рейтингом выше 3000 единицы. Это самые сильные программисты в мире и красный кружочек напротив их ника светится счастьем из-за своего месторасположения. Здесь изображена табличка цветов, которая постоянно висит перед участниками во время соревнований, как вечный знак стремления к самосовершенствованию :).

При таком большом количестве участников новичкам и слабо подготовленным участникам, скорее всего, пришлось бы туго, но на TopCoder действует деление на категории участников, которые называются Division. Всего существует 2 дивизиона: Div1 предназначен для сильных и опытных участников, имеющих рейтинг от 1200 и выше, т.е. для синих, желтых и красных, и Div2 для новичков или участников, которые не смогли справиться с конкуренцией в Div1, с рейтингом ниже 1200.

Международные отношения

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

Говоря о международных отношениях, нельзя не упомянуть рейтинг стран на TopCoder (http://www.topcoder.com/stat?c=country_avg_rating). TOP10 выглядит так (по состоянию на 2 февраля 2007 года):

МестоСтранаУчастниковРейтинг
1 Россия 396 2769.63
2 Китай 786 2699.31
3 Польша 312 2674.79
4 США 683 2503.04
5 Канада 144 2443.14
6 Украина 122 2245.79
7 Словакия 63 2189.14
8 Нидерланды 28 2163.83
9 Германия 76 2149.74
10 Хорватия 43 2085.71
12 Беларусь 56 2004.29

Кроме рейтинга стран подводится рейтинг вузов (http://www.topcoder.com/stat?c=school_avg_rating). TOP10 (по состоянию на 2 февраля 2007 года):

МестоНазвание УчастниковРейтинг
1 Варшавский университет 57 2416.61
2 TsingHua University 42 2246.20
3 СПбГУ ИТМО 24 2239.84
4 Московский государственный университет 32 2238.30
5 University of Waterloo 33 2067.18
6 Саратовский государственный университет 14 2050.13
7 Stanford University 10 2041.30
8 Санкт-Петербургский государственный университет 15 2008.05
9 Comenius University 25 1986.38
10 FER Zagreb 11 1971.64
16 Киевский национальный университет 21 1772.45
17 Белорусский государственный университет 20 1746.44
18 Уфимский государственный авиационный технический университет 10 1725.35
19 Уральский государственный университет 11 1711.85

Арена для программистов

Основой, делающей возможным проведение соревнований по программированию на TopCoder, является TopCoder Arena, программа, написанная на языке Java, и в силу этого имеющая возможность запускаться под любой операционной системой, для которой реализована JVM (Java Virtual Machine). Для ее запуска вам потребуется либо возможность загружать Java-апплеты в вашем браузере, либо Java Web Start (http://java.sun.com/products/javawebstart/index.html), которая может запускать Java-программы в отдельном окне. Я использую второй вариант, поскольку он удобнее.

Регистрация и вход

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

Ниже окна для ввода пароля есть флажок "Use HTTP Tunneling". Ей следует воспользоваться, если ваш провайдер запрещает обмен трафиком по порту 5001, который использует Арена, либо, например, если вы участвуете из Интернет-клуба (проверено в московском клубе Cafemax).

Ход соревнования

SRM (Single Round Match) — это соревнования по алгоритмическому программированию, проходящие каждую неделю (а школьники могут участвовать еще и в THSC SRM — TopCoder High School Competition Single Round Match). Он состоит из нескольких стадий.

Регистрация

За 3 часа до начала соревнования открывается регистрация. Для нее следует войти в Арену и выбрать пункт меню Active Contests — выбрать текущее соревнование — Register. Арена сообщит о том, что регистрация прошла успешно, и участник появится в списке Registrants. В это время в чатах идет бурная полемика на тему того, кто из «великих» сегодня будет принимать участие, а кто нет, и каковы шансы каждого.

За 5 минут до начала соревнования регистрация завершается, участники желают друг другу успеха (с разной степенью искренности :)) и заходят в комнаты, распределяемые сервером так, чтобы у всех в одной комнате были примерно равные рейтинги. В каждой комнате находится около 20 человек, но не больше 25.

Coding Phase

Заветный таймер доходит до 0:00:00 и начинается фаза кодирования. В SRM участникам предлагается 3 задачи, идущих по возрастанию баллов и, обычно, по возрастанию сложности. Участник выбирает желаемую задачу из списка и приступает к ее решению. Таймер начинает обратный отсчет 1 часа 15 минут. После выбора задачи появляется новое окно, разделенное на части: верхняя содержит текстовое условие задачи, иногда с иллюстрациями, нижняя является редактором кода. В последних версиях Арены в редакторе появилась подсветка синтаксиса, что не может не радовать. Осталось еще реализовать IntelliSense, отладку и большую кнопку TZ.doc to Soft.exe (как вариант — большую кнопку «Выиграть» :)), но, организаторы неохотно идут на поводу у участников. Здесь же можно выбрать язык программирования, который будет использоваться для решения этой задачи.

Набрав решение, вы можете его сохранить на сервере кнопкой Save на случай дисконнекта или падения Арены, ОС или компьютера. После нажатия на Compile, код отправится на сервер, где будет скомпилирован. Если попытка компиляции была неудачна, Арена покажет окно с ошибками и номерами строк, в которых эти ошибки произошли. Таким образом, их можно оперативно исправить, даже если у вас нет компилятора под рукой. Учтите — только скомпилированный код будет проверяться или тестироваться на сервере, написать решение в редакторе недостаточно!

Если решение удачно скомпилировано, пора приступить к отладке. Арена позволяет согласно типам аргументов создать произвольный вход для вашего метода, а так же выбрать один из нескольких тестов, представленных в условии задачи. Нажав кнопку OK, сервер начнет тест и выдаст вам результат, возвращенный методом, то, что было выведено в стандартный поток вывода (это и позволяет использовать силовую отладку), а, начиная с последних версий, и то, верно ли возвращенное методом значение. Разумеется, только для тестов из условия. Итак, если решение проходит все тесты из условия, придуманные участником тесты, а уверенность в правильности кода для всех корректных тестов не проходит, настало время жать кнопку Submit. И поскорее! Время-то уходит, а с ним и драгоценные баллы!

После отправки решения напротив вашего ника в Summary комнаты появятся баллы, зависящие от времени решения согласно следующей функции:

b = b_0 \left( {0.3 + \frac{{0.7t^2 }}{{10x^2  + t^2 }}} \right)

Здесь t — общее время соревнования, а x — время, потраченное на решение данной задачи, считая от запроса на получение задачи до принятия сервером кода. Для SRM это выглядит так:

Сейчас, на Coding Phase решения не тестируются, поэтому узнать, прошло ли решение все тесты, нельзя. Но соперники, конечно, начнут ощутимо нервничать, увидев резко подросшего во временном рейтинге участника :).

Вы решили все три задачи или не успели? Не важно, ведь как только таймер доходит до 0:00:00, выдается окно с сообщением, что Coding Phase окончена. Это значит, что больше решения не принимаются. Наступает новая фаза.

Intermission

Скорее всего, эта фаза предназначена для того, чтобы присланные решения были переписаны из оперативной памяти в БД, а нервы участников пришли в порядок от скоростного дописывания и тестирования решений, позволяет им ненадолго отлучиться от компьютера, другими словами «отойти». А ведь это важно, потому что всего через 3 минуты начинается…

Challenging Phase

Эта фаза не имеет аналогов в других соревнованиях. Основная идея challenging заключается в том, что участники ищут ошибки в решениях других участников. На ней можно открыть и просмотреть решение любого из вашей комнаты. И не только просмотреть — вспомните, как вы пытались завалить свое решение на хитроумном тесте? Теперь это же можно сделать с другими! А они были настолько внимательными, чтобы заметить эту возможную ошибку? Ощущения при challenging неописуемы, жаль, мне не удалось ни разу их испытать — все мои challenges провалились :).

Если вы составили корректный тест, на котором проверяющая программа и программа выбранного участника дают разные ответы, поздравляю. И обратите внимание на увеличение ваших баллов на 50. А за надпись Challenge Succeded и 0 баллов за задачу ваш соперник тоже должен быть благодарен вам. Ну, или не благодарен. Но в любом случае, набор системных тестов, которые составляют авторы задач, достаточно полон, чтобы его решение все равно упало на System Test Phase. Впрочем, если теста, на котором вы кого-нибудь успешно завалили, в системных тестах не было, его туда добавят, и будут прогонять на нем решения всех участников. Но не пытайтесь завалить кого-нибудь необоснованно — за неудачную попытку challenging отнимается 25 баллов.

И вот, все точки над i в работе участников расставлены. Пришла пора потрудиться серверу. Ведь наступает…

System Test Phase

На этой стадии все решения всех участников прогоняются на заранее подготовленном авторами большом количестве тестов и тестах, добавленных на Challenging Phase. В маленьком окошке таймера лениво ползет к заветным 100% процент проведенных тестов, отображается их общее астрономическое число (обычно порядка 100 тысяч), а участники, согласно завету незабываемого БГ, откидываются на спинки кресел и начинают приходить в себя после полутора часов напряженного мозгового штурма. В чате появляются первые сообщения после долгой тишины, прерываемой лишь системными сообщениями о компиляции, тестировании или сдаче задач участниками из вашей комнаты.

— Is 500's solution greedy?

— No, I know contrexample

— SharpC's solution is clear greedy

— Yeah, I know, I mistaked

Тем временем цифра 99,78% сменяется сообщением System Test Phase Ended, и все участники жадно прикипают к окнам Summary и Division Summary. Petr и tomek смотрят, кто из них сегодня самый первый на TopCoder, я смотрю, удалось ли мне сегодня войти в первую десятку комнаты :, и эти окна, ничуть ни кривя душой, нам всем об этом сообщают. Фраза Failed System Test сообщает о том, что какой-то хитрый тест решение не прошло, позже, когда задачи этого соревнования будут добавлены в Practice Room, можно будет посмотреть, какой именно тест.

Еще через несколько минут пересчитывается рейтинг, и объявляются, сколько зеленых президентов получат победители. В Div1 президентов получают первые три человека в каждой комнате, в Div2 — двое. Поэтому, как видите, переходить в Div1 смысл есть :). Обычно призовой фонд SRM составляет 5000$, поэтому каждому победителю достается от 50$ до 100$. Некоторые участники, благодаря TopCoder скоро наверняка станут миллионерами. Томек Чайка aka tomek заработал за 5 лет соревнований почти 120000$, Петру Митричеву aka Petr пока не так везет, всего 51000$. Реальный пример того, что олимпиады и конкурсы могут приносить не только моральное удовлетворение.

Однако чувствуется, что TopCoder — все-таки американская организация. Так, получить приз нельзя жителям Кубы, Ирана, Ирака, Ливии, Северной Кореи, Судана, Сирии и канадской провинции Квебек :).

Языки программирования

Для участия в соревнованиях участникам разрешено использовать 4 языка: C++, Java, C# и VB.NET. Большинство участников (и ваш покорный слуга в том числе) использует C++ ввиду его невероятной гибкости и наилучшей скорости, которая, по заверениям опытных топкодеровцев, позволяет иногда сдавать задачи с худшим алгоритмом за счет более высокой скорости его исполнения и, таким образом, укладываться в Time Limit, равный две секунды на один тест. Петр Митричев и многие другие используют C#, видимо, вследствие удобной среды программирования Visual Studio .NET, большой библиотеки классов .NET Framework Class Library (FCL), из которой особую ценность имеют классы регекспов и некоторые другие, и давно завоевавшего весь мир Си-синтаксиса. Также немало участников используют Java, в основном, профессиональные программисты, среди которых этот язык очень популярен. Ее библиотека классов так же неплохо помогает в решении задач, к примеру, класс StringTokenizer решает задачи, для которых C++-программистам порой приходится писать код самостоятельно. Незначительное число участников использует язык VB.NET, который очень похож на C#, но использует более читабельный, хотя и менее компактный и красивый синтаксис языка Basic.

Приготовьтесь к тому, что для участия вам придется показать довольно существенные знания выбранного языка. Покажем это на примере C++.

Во-первых, задача участника заключается в том, чтобы написать не просто программу, а класс с заданным именем, реализующий функцию с заданным прототипом. Таким образом, вы должны хотя бы на начальном уровне владеть парадигмой объектно-ориентированного программирования. В частности, вас не должно ставить в тупик сообщение, помещающееся в текст каждой задачи: "be sure your method is public". Ну а если все-таки ставит, ознакомьтесь с понятием модификатор доступа. Все дело в том, что проверяющая программа вставляет ваш класс в код тестирования, который просто объявляет объект заданного типа и вызывает у него заданный метод. Если модификатор доступа заданного метода protected, или тем более private, компилятор не сможет собрать вашу программу. Следует использовать public, причем не забыть его указать явно, так как по умолчанию C++ использует модификатор доступа private. Во-вторых, во многих, если не в большинстве задач, аргументы передаются и/или возвращаются с использованием стандартной библиотеки C++ STL (Standard Template Library). Наиболее популярными классами STL, встречающимися в задачах, являются классы vector и string, которые будут вкратце описаны ниже. Кроме того, если вы хотите писать красивые объектно-ориентированные решения, которые не будут грешить указателями, массивами фиксированного размера, Си-строками, вам придется многое заменить в своем программистском лексиконе. Например, функции типа sprintf классом stringstream, массивы типа char классом string, функцию qsort, работающую с указателями, на функцию sort из библиотеки <algorithm>, которая использует итераторы — интересное понятие STL, с которым непременно стоит ознакомиться.

В-третьих, большинство участников использует операционную систему Windows, а компиляция и тестирование программ на C++ происходит на Unix-платформе с использованием GCC. Поэтому вам придется доказать, что вы знаете, что такое кроссплатформенность и забыть, по крайней мере, на время соревнований, что такое __int64, DWORD и ExitProcess :).

Необходимый минимум STL

Все стандартные классы и шаблоны STL определены в пространстве имен std, поэтому, если вы не хотите писать бесконечные std::vector<std::string>, следует писать после многочисленных #include перед многочисленными вызовами классов STL следующую строку:

  1. using namespace std;

Не стоит забывать о том, что все используемые вами файлы (библиотеки C++ и т.п.) вы должны включать с помощью #include самостоятельно, тестирующая программа не будет это делать за вас.

vector

Класс vector определен в файле с тем же именем, включите его в программу с помощью следующей директивы:

  1. #include <vector>

Класс vector — почти то же самое, что и массив, только намного удобнее. Тип его элементов указывается при объявлении в угловых скобках, (это называется инстанцирование шаблона, если вы понимаете, о чем я :) например, так:

  1. vector<int> v;

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

  1. vector<vector<int>> v;

пишите

  1. vector< vector<int> > v;

Это может показаться тривиальным, но только не тогда, когда вы используете макросы вида

  1. #define VI vector<int>

Написав

  1. vector<VI> v;

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

Для добавления элемента в конец массива (при этом он изменяет свой размер автоматически) используется метод push_back:

  1. v.push_back(123);

Подобно массиву, vector можно использовать с оператором [], если элемент, указанный в квадратных скобках, существует. Если мы добавили методом push_back элемент 123 в vector, то сможем получить его, написав, например:

  1. cout << v[0];

Как и положено порядочному Си-массиву, vector нумерует свои элементы, начиная с нуля.

Чтобы узнать, сколько элементов в массиве, следует использовать метод size. Теперь, написав

  1. cout << v.size();

мы увидим 1. И верно, элемент в vector всего один.

Так же полезным, особенно при инициализации, является метод assign. Он позволяет быстро создать нужное количество элементов с нужным значением. Хотим сделать в vector 50 нулевых элементов? Кто сказал

  1. int a[50];
  2. for(int i = 0; i < 50; i++){
  3.     a[i] = 0;
  4. }

такую чушь? Отставить. Пишем

  1. vector<int> v;
  2. v.assign(50, 0);

или просто в конструкторе

  1. vector<int> v(50, 0);

и радуемся возросшей ООПшности, читабельности и компактности нашего кода.

string

В свое время мне очень сильно не нравился язык C++, особенно после Basic, своими строками, доставшимися в тяжелое наследие от языка Си. Мое искреннее мнение, что тогда, что сейчас, состояло и состоит в том, что писать бесконечные strcat, strchr, strtok и strstr, выделять для них память, а потом не забывать ее освобождать — все это убивает творческое начало программиста. Кроме того, это еще и опасно. В подавляющем большинстве туториалов по написанию шелл-кодов и эксплоитов, которыми пользуются нехорошие дядьки, в качестве самого первого примера приводятся именно подобные функции, которые что-то пытаются куда-то вставить, но выделенного размера строки оказывается недостаточно. Происходит затирание стекового фрейма, и программа в лучшем случае вылетает. А в худшем у вас на компьютере появляется замечательный сосед, который не только способен играть роль всевидящего Большого Брата, но и испортить вам все, начиная от информации и компьютера, заканчивая жизнью, в зависимости от ценности хранимой информации.

И вот — на сцену выходит он! Великолепный, удобный и стандартный класс string, входящий в состав STL. Чем же он так удобен?

  1. string s = "hello, world!";
  2. // Присваиваем ей обычную строку, как ни в чем не бывало
  3.  
  4. cout << s.length() << endl;
  5. // И длину (13) получить не проблема
  6.  
  7. char c = s[6];
  8. // Получаем из нее 6-й символ, какой? Правильно, пробел :)
  9.  
  10. cout << s << endl;
  11. // Спокойно ее выводим
  12.  
  13. cout << s.substr(0, 5) << endl;
  14. // Или ее подстроку - hello, 5 символов, начиная с 0-го
  15.  
  16. cout << s.find("wo", 0) << endl;
  17. // Ищем начало подстроки, т.е. 7
  18.  
  19. bool has = (s.find("hi", 0) != string::npos);
  20. // А вдруг ее там нет?
  21.  
  22. s += c; s += s;
  23. // Конкатенация исключительно интуитивно понятна. "hello, world! hello, world! "
  24.  
  25. s.clear();
  26. // Очистить? Можно, конечно, и s = "", но нехорошо :)

Книги

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

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

  • Бьерн Страуструп «Язык программирования C++». Эта книга, без всякого сомнения, библия программистов на C++, в которой детально и педантично описаны все его особенности и ООП. http://www.ozon.ru/context/detail/id/85559/?partner=esci
  • Николай Джосьютис «C++. Стандартная библиотека». Подробный и хорошо написанный учебник по STL, который расскажет вам и о важности, и об использовании, и о тонкостях этого замечательного элемента C++. http://www.ozon.ru/context/detail/id/1556395/?partner=esci
  • Скотт Мейерс «Эффективное использование STL». Книга для профессионалов, которая позволит вам не только с бОльшим знанием дела применять стандартную библиотеку на Арене, но и писать более качественный код. http://www.ozon.ru/context/detail/id/1253685/?partner=esci

В качестве справки по STL удобно применять MSDN и мануал, находящийся по адресу http://www.sgi.com/tech/stl.

Книг по алгоритмам много не бывает, даже несмотря на то, что SRM ввиду своей кратковременности и ориентации на одного участника, не использует, даже в Div1, каких-то крайне сложных алгоритмов, знания, полученные из них, очень пригодятся вам на соревнованиях типа TopCoder Open, ACM и т.п. Из известных можно назвать следующие книги:

  • Дональд Кнут «Искусство программирования». Подобно тому, как Страустрап является библией программиста на C++, эту книгу следует прочитать всем, кто интересуется алгоритмами, математическим программированием и математикой вообще. Книга имеет ряд особенностей, например, все примеры Профессор Кнут (подобно Толкину, Кнута называют Профессором с большой буквы) пишет на придуманном им самим языке MIX, который представляет собой некий аналог языка ассемблера для придуманной Кнутом архитектуры. http://www.ozon.ru/context/detail/id/1335648/?partner=esci, http://www.ozon.ru/context/detail/id/2527041/?partner=esci, http://www.ozon.ru/context/detail/id/2527036/?partner=esci.
  • Роберт Седжвик «Фундаментальные алгоритмы на C++». Очень талантливо написанная книга, описывающая большое количество алгоритмов, да еще и использующая в качестве основного языка примеров именно C++. http://www.ozon.ru/context/detail/id/1425748/?partner=esci, http://www.ozon.ru/context/detail/id/1425747/?partner=esci.
  • Альфред Ахо, Джон Хопкрофт, Джеффри Ульман «Структуры данных и алгоритмы». Хорошо структурированная и понятная книга, описывающая фундаментальные структуры данных и алгоритмы обработки данных. В качестве языка используется Pascal. http://www.ozon.ru/context/detail/id/114200/?partner=esci
  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест «Структуры данных и алгоритмы». Рекомендуемый опытными олимпиадниками международного уровня замечательный учебник по алгоритмам. В нем описываются почти все основные алгоритмы и структуры данных, используемые на олимпиадах. http://www.ozon.ru/context/detail/id/2429691/?partner=esci
  • Стивен Скиена, Мигель Ревилла «Олимпиадные задачи по программированию. Руководство по подготовке к соревнованиям». Замечательная книга, написанная создателями одного из крупнейших серверов задач по программированию http://acm.uva.es. Помимо собственно задач в ней находится почти весь теоретический минимум для их решения. http://www.ozon.ru/context/detail/id/2363462/?partner=esci

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

Домашние заготовки

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

Макросы

Пример:

  1. #define REPSZ(i, a) for(int i = 0; i < (a).size(); i++)

Эта очень популярная заготовка позволяет сильно сократить время на написание циклов, перебирающих все элементы vector или string. Сравните, что удобнее, писать

  1. for(int i = 0; i < a.size(); i++){
  2.     for(int j = 0; j < a[i].size(); j++){
  3.         res += a[i][j];
  4.     }
  5. }

или

  1. REPSZ(i,a) REPSZ(j,a[i]) res += a[i][j];

А что удобнее для понимания другими участниками? В этом и заключается важное преимущество заранее заготовленных макросов — они увеличивают читабельность кода для вас лично и уменьшают для остальных участников, а второе немаловажно на стадии challenging.

Операторы

Многие задачи удобнее решать и отлаживать в Арене, чтобы не тратить времени на копирование-вставку кода, запуск IDE и написание тестирующего кода (для этого есть специальные плагины, но о них ниже). Поскольку Арена не имеет встроенного отладчика, приходится использовать так называемую «силовую отладку»: вывод некоторых интересующих переменных в определенных местах. Но для вывода, например vector, оператор << класса cout не перегружен. Но это можно сделать самостоятельно и активно использовать для отладки. Рассмотрим пример.

  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4.  
  5. using namespace std;
  6.  
  7. template<class T>
  8. ostream& operator<<(ostream& out, const vector<T> a){
  9.     out << "{";
  10.     for(int i = 0; i < (int)a.size(); i++){
  11.         if(i != 0) out << ", ";
  12.         out << a[i];
  13.     }
  14.     out << "}";
  15.     return out;
  16. }
  17.  
  18. template<>
  19. ostream& operator<<(ostream& out, const vector<string> a){
  20.     out << "{";
  21.     for(int i = 0; i < (int)a.size(); i++){
  22.         if(i != 0) out << ", ";
  23.         out << "\"" << a[i] << "\"";
  24.     }
  25.     out << "}";
  26.     return out;
  27. }
  28.  
  29.  
  30. int main(){
  31.     vector<string> arg;
  32.     arg.push_back("hello");
  33.     arg.push_back("world");
  34.     arg.push_back("of");
  35.     arg.push_back("operators");
  36.  
  37.     cout << arg << endl;
  38.  
  39.     return 0;
  40. }

Эта программа нам выведет {"hello", "world", "of", "operators"} так, как будто программисты iostream позаботились о нас. Следует отметить, что на строки в кавычках смотреть приятнее, чем без них, поэтому шаблонный оператор << частично специализирован для T = string. Идея данного примера была позаимствована из кода венгерского программиста misof, долгое время бывшего третьим в рейтинге TopCoder.

Классы

Их используют не так много участников ввиду того, что в настоящее время на TopCoder действует правило Extra Code Rule, согласно которому решение не должно содержать лишнего неиспользуемого кода, кроме #include и комментариев, непосредственно связанных с решением задачи или используемыми плагинами. Скажем, за лишнюю процедуру с вас снимут баллы. Но в некоторых задачах целесообразно использовать крупные домашние заготовки наподобие библиотеки Boost.Graph, удобно реализующей работу с графами.

Функции

Мелкие удобные функции довольно часто используются участниками. Это могут быть функции для деления строки на части (удобный аналог strtok):

  1. vector<string> SPLIT(string s, string del = " ", bool f = false){
  2.     s += del[0];
  3.     string w = "";
  4.     vector<string> res;
  5.     for(string::iterator it = s.begin(); it != s.end(); ++it){
  6.         if(find(del.begin(), del.end(), *it) == del.end()){
  7.             w += *it;
  8.         } else if(f || w != ""){
  9.             res.push_back(w);
  10.             w = "";
  11.         }
  12.     }
  13.     return res;
  14. }

Функции для нахождения НОД и НОК:

  1. int GCD(int a, int b){
  2.     while(a&&b){
  3.         if(a>b) a %= b;
  4.         else b %= a;
  5.     }
  6.     return a + b;
  7. }
  8.  
  9. int LCM(int a, int b){
  10.     return a / GCD(a, b) * b;
  11. }

Функции для проверки числа на простоту:

  1. bool ISPRIME(int n){
  2.     if(n % 2 == 0) return false;
  3.     for(int i = 3; i * i <= n; i += 2){
  4.         if(n % i == 0) return false;
  5.     }
  6.     return true;
  7. }

И тому подобные часто употребляющиеся маленькие функции.

Примочки

Процесс использования сторонних компиляторов и сред разработки, например, Microsoft Visual Studio, на Арене усложнен тем, что участнику нужно писать самостоятельно тестирующий код, переписывать из условия тесты для того, чтобы быстро проверять свое решение на корректность. Поэтому разработчики Арены сделали возможным расширение ее функционала с помощью плагинов на Java. Список плагинов (http://www.topcoder.com/tc?module=Static&d1=applet&d2=plugins) довольно обширен и включает в себя автогенерацию тестирующего кода (TzTester), вставку объявления класса, описанного в условии (CodeProcessor), более удобный редактор кода (FileEdit) и многие другие.

Попробуем силы?

И, наконец, в качестве примера задач рассмотрим проходивший 19 августа 2006 года SRM 316, ввиду того, что он был первый, в котором я победил и решил все три задачи :). Эти задачи предлагались участникам из Division 2.

Задача 250

Условие

Здесь и далее условие приводится здесь исключительно в целях цитирования, в размерах, соответствующих цели цитирования. Информация об авторских правах сохранена. http://www.topcoder.com/stat?c=problem_statement&pm=6618&rd=9996&rm=249431&cr=21355006

Problem Statement

Some texts contain hidden messages. In the context of this problem, the hidden message of a text is composed of the first letter from each word in the text, in the order they appear.
Given a string text, consisting of only lowercase letters and spaces, return the hidden message. A word is a maximal sequence of consecutive letters. There may be multiple spaces between words. Also, text may contain only spaces.

Definition

Class: HiddenMessage
Method: getMessage
Parameters: string
Returns: string
Method signature: string getMessage(string text)
(be sure your method is public)

Constraints

- text will contain between 1 and 50 characters, inclusive.
- Each character of text will be either a lowercase letter ('a'-'z'), or a space (' ').

Examples

0)
"compete online design event rating"
Returns: "coder"
Taking the first letter from each word yields the return "coder".

1)
"  c    o d     e      r    "
Returns: "coder"
Watch out for the leading spaces.

2)
"round  elimination during  onsite  contest"
Returns: "redoc"
"coder" written backwards.

3)
" "
Returns: ""
Since there are no words here, the empty string must be returned.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.

Сокращенный перевод

Здесь требуется разбить предложение, состоящее из 1-50 букв от a до z и пробела, на слова, содержащие только буквы a-z, и вывести слово, составленное из первых букв этих слов.

Решение

Задача 250 Div2, как ей и положено быть, совсем несложная. И, как ей и положено, она может решаться большим количеством способов, начиная от конечного автомата, который добавляет в искомую строку все символы, заканчивая читерскими решениями, использующими стандартные классы используемого языка программирования. Вот компактное решение, использующее домашние заготовки (предложено shuffle):

  1. VS kde=SPLIT(text); string ret;
  2. _repsz(i,kde) ret+=kde[i][0];
  3. return ret;

Мое решение несколько сложнее ввиду того, что на момент состязания функции SPLIT или аналога в моей «коллекции» не было:

  1. #include <string>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. class HiddenMessage {
  7. public:
  8.   vector<string> split(string text){
  9.     vector<string> res;
  10.     string s;
  11.     for(int i = 0; i < text.length(); i++){
  12.       if(text[i] == ' '){
  13.         if(s != ""){
  14.           res.push_back(s);
  15.           s = "";
  16.         }
  17.       } else{
  18.         s += text[i];
  19.       }
  20.     }
  21.     if(s != "") res.push_back(s);
  22.     return res;
  23.   }
  24.    
  25.   string getMessage(string text){
  26.     string res;
  27.     vector<string> vs = split(text);
  28.     for(int i = 0; i < vs.size(); i++) res += vs[i][0];
  29.     return res;
  30.   }
  31. };

А многие участники предложили читерское решение с использованием стандартного класса stringstream (#include <sstream>):

  1. stringstream ss;
  2. ss.str(text);
  3. string res, w;
  4. do{
  5.     w = "";
  6.     ss >> w;
  7.     res += w[0];
  8. } while(w != "");
  9. return res;

Задача 500

Вторая задача Div2 обычно является первой задачей Div1, поэтому она, хотя и разрешима опытным участником за 5-10 минут, но представляет собой серьезное испытание для новичка.

Условие

http://www.topcoder.com/stat?c=problem_statement&pm=6619&rd=9996&rm=249431&cr=21355006

Problem Statement

When returning from vacation, you have to delete some unwanted email messages in your inbox, like spam or other unimportant messages. Your inbox consists of several pages that each contain the same number of messages (except possibly the last page). Each message has two corresponding buttons that allow you to:
- add the message to the current selection
- remove the message from the current selection
In addition, each page has three buttons with the following functions:
- select all messages on the current page
- delete all selected messages on the current page
- advance to the next page of messages (unless you're already on the last page)
Selections do not extend across pages, and advancing to the next page deselects everything that is currently selected. Also, deleting messages will not cause later messages in the inbox to scroll up to the current page.
For example if you have four email messages on one page and you would like to delete the second one, you could select it and then click on delete for a total of two clicks. An alternative is to select all messages, then deselect all other messages except the second, and then click delete, for a total of five clicks.
Naturally, you would like to clean up your inbox with as few clicks as possible. Furthermore, you are allowed to choose the number of emails to display per page. If you decide to display K messages per page, the first K messages will be on the first page, the next K messages will be on the second one, and so on. Obviously, the last page might contain less than K messages. Note that you need to check all pages of messages, even if they do not contain any messages that must be deleted.
You will be given a String messages containing a description of email messages in the order they appear in your inbox. The 'D' character denotes a message that should be deleted, while a '.' character denotes an email that should be kept. You will also be given two ints, low and high, denoting the inclusive lower and upper bounds of the number of messages on each page. You should choose how many emails to display per page such that the number of clicks needed is minimal, and then return the number of clicks.

Definition

Class: InboxCleanup
Method: fewestClicks
Parameters: string, int, int
Returns: int
Method signature: int fewestClicks(string messages, int low, int high)
(be sure your method is public)

Constraints

- messages will contain between 1 and 50 characters, inclusive.
- Each character of messages will be either 'D' or '.'.
- low will be between 1 and the number of characters in messages, inclusive.
- high will be between low and the number of characters in messages, inclusive.
 
Examples

0)
".........."
5
10
Returns: 0
No messages to delete here. Since we can display all messages in one page, there is no need to click any button.

1)  
".D.D.DD.D."
5
5
Returns: 8
Your only choice here is to display 5 messages per page. Select the two messages from the first page and then click delete for a total of three clicks. One more click is needed for advancing to the next page. For the second page, you have two options: first select all messages and then deselect the third and fifth ones, or select each of the three 'D' messages individually. Both options require three clicks. After the selection is made, click delete.

2)  
"...D..DDDDDD...D.DD.."
3
10
Returns: 12
Display 6 messages per page.

3)  
"D.D..D..DD.DDDD.D.DDD.DDDD.."
3
11
Returns: 17

4)  
"DDD........................."
1
3
Returns: 11
Remember that you need to check all pages.

Сокращенный перевод

Здесь требуется найти минимальное число кликов, которым можно удалить весь спам из почтового ящика, если список писем разбит на страницы одинакового размера от low до high писем на страницу. Список писем задается строкой, где D означает спам, а . — нормальное письмо. При этом доступны следующие действия, на каждое из которых тратится один клик:

  • Переход на следующую страницу
  • Выделение всех писем на текущей странице
  • Добавление одного письма в выделение
  • Удаление одного письма из выделения
  • Удаление всех выделенных писем

При этом требуется просмотреть все страницы.

Решение

Сразу заметим, что ввиду необходимости просмотреть все страницы в результат автоматически добавляется число N-1, где N - число страниц. Число страниц определяется исходя из числа писем на страницу и общего числа писем, но вот в чем загвоздка — мы не можем точно сказать, при каком p, входящем в интервал [low; high] число кликов будет наименьшим. Поэтому нам надо перебрать все возможные p, найти для них число страниц, и просуммировать числа кликов, нужные для удаления спама на каждой странице с числом страниц минус один. Количество кликов, необходимых для удаления спама с одной страницы, определяется по следующим 3 правилам:

  • Если количество спама равно 0, то нужно 0 кликов.
  • Если количество спама d меньше или равно числу нормальных писем p, то необходимо и достаточно d+1 кликов: выделить каждое из d нехороших писем и нажать кнопку «удалить».
  • Если же d > p, то понадобится p+2 кликов: выделить все письма, снять выделение с p нормальных писем и нажать кнопку «удалить».

Реализацию этого на C++ вы можете видеть ниже.

  1. #include <iostream>
  2. #include <string>
  3.  
  4. using namespace std;
  5.  
  6. class InboxCleanup {
  7. public:
  8.   int f(int a, int b){
  9.     if(a%b) return a / b + 1;
  10.     return a / b;
  11.   }
  12.    
  13.   int fewclick(string s){
  14.     int d = 0, p = 0;
  15.     for(int i = 0; i < s.length(); i++){
  16.       if(s[i] == 'D') d++;
  17.       else p++;
  18.     }
  19.     if(d == 0) return 0;
  20.     if(p < d) return p + 2;
  21.     else return d + 1;
  22.   }
  23.  
  24.   int fewestClicks(string messages, int low, int high){
  25.     int res, min = 100000, np;
  26.     for(int onpage = low; onpage <= high; onpage++){
  27.       np = f(messages.length(), onpage);
  28.       res = np - 1;
  29.       for(int p = 0; p < np; p++){
  30.         res += fewclick(messages.substr(p * onpage, onpage));
  31.       }
  32.       if(res < min) min = res;
  33.     }
  34.     return min;
  35.   }
  36. };

Обратите внимание на функцию f — по невнимательности легко ошибиться в том, как вычисляется число страниц.

Задача 900

Эта задача, как правило, достаточно сложна для того, чтобы из всего Div2 ее могли решить от силы 10% участников — она требует уверенного знания базовых алгоритмов и сносной математической подготовки.

Условие

http://www.topcoder.com/stat?c=problem_statement&pm=6538&rd=9996&rm=249431&cr=21355006

Problem Statement

You are the manager of a company, and you want all of your employees to be notified of an important news item as quickly as possible. Your company is organized in a tree-like structure: each employee has exactly one direct supervisor, no employee is his own direct or indirect supervisor, and every employee is your direct or indirect subordinate. You will make a phone call to each of your direct subordinates, one at a time. After hearing the news, each subordinate must notify each of his direct subordinates, one at a time. The process continues this way until everyone has heard the news. Each person may only call direct subordinates, and each phone call takes exactly one minute. Note that there may be multiple phone calls taking place simultaneously. Return the minimum amount of time, in minutes, required for this process to be completed.
Employees will be numbered starting from 1, while you will be numbered 0. Furthermore, every supervisor is numbered lower than his or her direct subordinates. You are given a int[] supervisors, the ith element of which is the direct supervisor of employee i. The first element of supervisors will be -1, since the manager has no supervisors.

Definition

Class: SpreadingNews
Method: minTime
Parameters: int[]
Returns: int
Method signature: int minTime(int[] supervisors)
(be sure your method is public)

Constraints

- supervisors will contain between 1 and 50 elements, inclusive.
- Element i of supervisors will be between 0 and i-1, inclusive, except for the first element which will be -1.

Examples

0)
{-1, 0, 0}
Returns: 2
Call subordinate 1 at time 0 and then subordinate 2 at time 1. By time 2, both subordinates will have heard the news.

1)
{-1, 0, 0, 2, 2}
Returns: 3
This time call employee 2 first, and then employee 1 at time 1. After hearing the news, employee 2 will call employee 3 at time 1 and employee 4 at time 2. It takes 3 minutes for everybody to hear the news.

2)
{-1, 0, 1, 2, 3}
Returns: 4
Everyone in the company has only one subordinate, resulting in a chain of phone calls.

3)
{-1, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 12, 13, 14, 16, 16, 16}
Returns: 7

Сокращенный перевод

Здесь нам дана иерархическая структура, в самый верх которой прибывает новость, которую нужно передать всем элементам структуры. Новость передается ровно 1 минуту и только непосредственному потомку элемента. Нужно узнать, за какое минимальное время новость может быть сообщена всем.

Решение

Сама древовидная структура иерархии указывает на то, что мы должны использовать аппарат теории графов. А именно — у нас есть корневое дерево, каждой вершине которого можно сопоставить целое неотрицательное число. Это число будет являться временем, нужным для сообщения этой вершиной новости всему поддереву, корнем которого она является. Очевидно, что если у вершины нет потомков, то это время равно 0. Рассмотрим более сложный случай: вершина имеет n потомков, со временем Ai. Как тогда определить, чему равно время корневой вершины?

Пусть мы сообщаем новость потомку i на минуте Bi < n. Тогда время вершины будет равно max{Ai+Bi}. Мы стремимся минимизировать это число и поэтому должны сообщить самому «медлительному» потомку новость как можно раньше. Поэтому отсортируем время потомков по убыванию и добавим время от начала обмена информацией, через которое мы сообщим им новость, в порядке возрастания. Таким образом, если потомки имеют времена {4, 8, 1, 5, 8}, то самой грамотной тактикой была бы та, которая дает {8+1, 8+2, 5+3, 4+4, 1+5}. Максимум здесь 8+2=10, следовательно, время вершины с такими потомками — 10.

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

  1. vector<int> sv;
  2.  
  3. int calcTime(int you){
  4.     vector<int> vt;
  5.     for(int i = 0; i < sv.size(); i++){
  6.         if(sv[i] == you) vt.push_back(calcTime(i));
  7.     }
  8.     if(vt.size() == 0) return 0;
  9.     sort(vt.begin(), vt.end());
  10.     int r = vt.size();
  11.     for(int i = 0; i < vt.size(); i++){
  12.         vt[i] += r--;
  13.     }
  14.     sort(vt.begin(), vt.end());
  15.     return vt[vt.size() - 1];
  16. }

Обратите внимание — здесь используется функция sort из библиотеки <algorithm>, в качестве аргументов ей переданы итераторы начала и конца vector, то есть, сортируется весь вектор. По умолчанию это происходит по возрастанию, что учтено в коде.

Следовательно, теперь задача метода minTime чисто утилитарная, скопировать аргумент, вызвать calcTime с аргументом 0 (корень всего дерева) и вернуть результат:

  1. int minTime(vector <int> supervisors){
  2.     sv = supervisors;
  3.     return calcTime(0);
  4. }

Эпилог

Вот и остался позади разбор задач одного из сотен SRM, проходивших на TopCoder. Пишите мне, если что-нибудь неясно. Регистрируйтесь, играйте и, конечно же, выигрывайте. Встретимся на Арене, мой ник — SharpC.

Копирование материалов сайта допускается только с указанием ссылки