Этот текст я пишу в основном для ребят младших курсов своего университета, чтобы они наконец начали участвовать в соревнованиях Topcoder. Так получилось, что на Codeforces это сделать мне наиболее удобно. Может быть, кому-то еще пригодится.

Что вообще такое Topcoder

Topcoder — это как Codeforces, только менее удобный. На самом деле, помимо соревнований по спортивному программированию там проводится еще куча мероприятий, которым аналогов в мире нет, так что многим деваться просто некуда :) А для тех, кто занимается именно спортивным программированием, это просто еще три-четыре неплохих контеста в месяц.

Если кликнуть на сайте на ссылку Events, а далее — Event Calendar, можно увидеть расписание этих контестов. Время там указано какое-то американское, чтобы получить московское, нужно в разное время года прибавлять либо 8 часов, либо 9. Кроме того, можно кликнуть на конкретный SRM (раунды здесь именно так называются — Single Round Match), и там будет ссылка на timeanddate.com, показывающая, во сколько начнется этот раунд.

Точно так же, как на Codeforces, на Topcoder есть рейтинг, есть красные и серые, есть комнаты и взломы, но устроено это немного по-другому. О правилах — в следующем разделе.

Правила Topcoder SRM

Раунд начинается с регистрации. За три часа до начала открывается регистрация, за пять минут до начала — закрывается.

Раунд состоит из двух частей. Сначала 1 час и 15 минут длится Coding Phase — тут надо решать задачи. Затем следует пятиминутный перерыв, и после него 15 минут идет Challenge Phase — здесь вы можете взламывать решения своих соперников по комнате. В отличие от Codeforces, решение задач и взломы на Topcoder разделены.

В раунде три задачи, обычно они стоят 250, 500 и 1000 баллов, иногда эти числа могут различаться. Изначально все задачи закрыты, но можно открыть некоторые из них и начать решать. Со временем стоимость открытых задач убывает, но нельзя получить за задачу менее 30% от начальной стоимости. Понятно, что пока не решишь одну задачу, невыгодно открывать другие — за них стоимость также начнет убывать. За ресабмит участник получает штраф в 10% от чего-то там, не помню, чего именно. Лучше сразу писать правильно и не ресабмитить.

Успешный взлом дает +50, неудачный дает -25. Затем прогоняются систесты, задачи падают, и участники узнают свои финальные результаты, после чего открывают Codeforces и начинают спрашивать, как решать 500.

Собственно, из правил это все, и дальше пойдет рассказ о конкретной IDE и конкретном языке программирования применительно к Topcoder. Вообще, писать там можно на Basic, C++, C#, Java и Python. Я расскажу про Java и Eclipse.

Arena, или как разработчикам Topcoder удобно кодить

По дефолту контесты пишутся в Арене. Ее можно запустить, протыкав на сайте ссылки Competitions — Algorithm — Single Round Matches — Launch Arena. Это Java-апплет, в котором вы типа должны писать контесты. Но мы не будем этого делать. Большинство людей все-таки используют нормальные среды разработки. Здесь будет рассказано об Eclipse, на странице загрузки подойдет, например, Eclipse Standard, и о плагине EclipseCoder.

Главное меню Арены

Я умолчу о том, что чтобы писать контесты на Java, неплохо бы установить JDK, поэтому этот шаг будет пропущен :) Скачайте Eclipse, распакуйте его и запустите. Теперь пришла пора установить плагин. Нажимаем Help — Install New Software, в строчку впечатываем адрес http://fornwall.net/eclipsecoder/. Понимаем, что можем установить вот такие компоненты (см. картинку). Выбираем Core, Java Support и Problem Archive, принимаем лицензионное соглашение, устанавливаем, перезапускаем Eclipse. Теперь можно писать контесты.

Установка EclipseCoder: выбор компонентов

Добавим вьюшку, из которой можно запускать Арену прямо из Eclipse. Тыкаем Window — Show View — Other, там выбираем EclipseCoder — Problem Statement. У нас появляется еще одна вкладка, на которой есть иконка с логотипом топкодера. Эта кнопка запускает Арену.

Вкладка с кнопкой запуска Арены

Точнее, она смотрит, как версия находится у вас сейчас (необходимые jar-ники качаются в папку ~/.eclipsecoder, где ~ — папка пользователя), обновляет, если нужно, и запускает. Не надо лезть на сайт и искать там ссылку Launch Arena — все делается из IDE.

Обновление Арены из Eclipse при запуске

Посмотрим на настройки EclipseCoder: в Eclipse перейдите по Window — Preferences — EclipseCoder. Здесь, если не боитесь, можно сохранить логин и пароль от своего аккаунта, а в подменю Java можно написать шаблон, который будет у вас появляться автоматически при решении каждой задачи. Довольно несложно догадаться, что означает каждая из этих переменных с долларами.

Шаблон класса

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

Задача Div-2 250: полное прохождение

Давайте теперь для завершения решим какую-нибудь халяву из дорешивания. Процесс решения на контесте и в дорешивании ничем не отличается, так что — запускаем Арену из Eclipse(это важно!), тыкаем там Practice Rooms — SRMs — и я выбрал самый последний раунд: SRM 592 Div 2.

Главное меню SRM 592 в дорешивании

На самом деле по внешнему виду дорешивание не отличается от контеста. Выберем задачу. Нажимаем на Select one и тыкаем 250 — это самая легкая задача.

Окошко с условием задачи

Если бы вы не использовали никаких плагинов, вы бы сейчас кодили в табе Coding Area прямо в этом окошке. Потрясающе удобное времяпровождение. Но мы пойдем наиболее хардкорным путем и откроем Eclipse.

Тем временем в Eclipse

Условие можно читать в Eclipse. Кодить можно в Eclipse. Видим, что нам сгенерировался метод, который нас просили написать, но, к сожалению, return 0; — это неправильное решение и не проходит даже семплы. Слева вы видите результат прогона юнит-тестов: EclipseCoder парсит семплы в условии и создает юнит-тесты, которые можно запустить одним кликом и увидеть, что вернул ваш метод и что он должен был возвращать на самом деле.

Теперь давайте решим задачу. Задача следующая: дан массив чисел pages, надо выбрать из него number чисел так, чтоб сумма была не минимально возможная, но при этом как можно меньше. Еще и все элементы в массиве различны.

Первое, что пришло на ум: выбрать number-1 минимальных чисел, одно пропустить, и выбрать следующее. Давайте попробуем это написать. Пишем, нажимаем Ctrl+F11 (Run). При написании можно писать свои методы и свои вложенные классы, но в этой задаче такое не нужно. Eclipse предложит выбрать, как именно запускать наш проект. Запускаем его как юнит-тесты.

Диалог Run As

Видим, что все тесты зелененькие — значит, мы прошли семплы!

Семплы пройдены!

Давайте добавим какой-нибудь свой тест. Откроем Package Explorer и выберем там класс, название которого оканчивается на Test.

Класс с юнит-тестами

Собственно, тут мы вольны использовать все возможности Junit. Чтобы создать свой тест, надо объявить публичный метод и снабдить его аннотацией @Test. Если при выполнении такого метода не будет никаких исключений, тест будет зелененьким :)

На сгенерированных автоматически тестах есть параметр timeout для аннотации @Test — он поможет вам отловить TL. Если вы хотите подебажить один из тестов — поставьте там timeout = (int)1e9 или вообще удалите этот параметр, поставьте брейкпоинт на внутри тела соответствующего метода-теста и жмите Debug. Либо можно просто выводить что-нибудь в System.out или System.err — топкодер эти выводы игнорирует — ему важно только то, что метод вернул.

Допишем свой собственный тест.

Собственный тест

После запуска выясняется, что он тоже работает правильно! Ну теперь можно сабмитить. Открываем Арену, точнее, то ее окошко, где написано условие задачи, жмем Compile — нам говорят, что все круто. Жмем Test — и запускаем наш код на одном из семплов (в этом режиме код запускается на сервере, я рекомендую в каждой задаче хотя бы один семпл пройти по кнопке Test — ну просто чтоб убедиться, что на сервере все нормально).

Запуск первого семпла на сервере

Видим, что Correct Return Value: Yes. Ну, значит все хорошо. Жмем Sumbit. Так как я писал этот текст одновременно с решением задачи, нам дали 156.76 очков из 250. Это, конечно же, очень мало, и на настоящем контесте за подобные задачи надо получать в районе 240-245 баллов.

У нас приняли сабмит

Систесты, однако, мы не проходили. Это всего лишь сабмит приняли. На настоящем контесте вы по его окончании узнаете, прошла у вас задача или нет, а в Practice Mode можно это проверить. Тыкаем в главном окне Арены Practice Options — Run System Test.

Accepted!

Все, теперь мы умеем решать топкодер. Потренируйтесь немного в Practice Mode, а потом можно приступать к самим SRM.