Привет, я dAFTc0d3r. Я хочу немного рассказать про то, как участвовать в соревнованиях TopCoder Algorithm.


Что же такое TopCoder в принципе?
TopCoder is a company which administers contests in computer programming (Wiki).
Да, TopCoder проводит соревнования, причём совершенно различных видов: Algorithms, Design, Development, Marathon Matches, Studio, Architecture, Assembly, Testing, Bug Races.

Первое, с чем мы сталкиваемся, когда заходим на сайт топкодера (topcoder.com)  - что делать? Куда дальше идти? Когда я регистрировался (что было в 2007 году) такой проблемы вроде не было. Если честно, я до сих пор не знаю, как сейчас самому дойти до правильного ответа - topcoder.com/tc.

Вторая проблема – регистрация. Хотя, в принципе, она вполне решаемая с помощью хорошего переводчика.

Третья проблема – запуск арены, через которую производится участие в соревнованиях Algorithm.
Насколько я помню, решение – установка Java Web Start.
Сама же ссылка на арену скрывается под текстом O(n) в левом верхнем углу сайта.

Когда мы решили первые три проблемы, запустили арену, вошли под своим пользователем, мы можем потренироваться. Это будет очень полезным.
Пусть наш язык – C++. Откроем одну из тренировочных комнат: Practice Rooms --> SRMs --> 609-624 --> 614 - SRM 448 DIV 2.


Далее мы попадаем в окно комнаты соревнований.
Выбираем задачу, пусть это будет 250я задача


Открывается окно Coding Phase (аа! сколько окон!). Сверху справа выбираем плагин и язык. В поле Problem Statement находится условие задачи. Понимаем условие задачи, читаем Defenition (в каком виде требуется отправить решение), обязательно читаем Constraints – ограничения, и смотрим Examples.


Мы должны посчитать сумму карт для игры Блэк Джек. Карта задаётся двумя символами – рангом и мастью. От нас требуют написать класс TheBlackJackDivTwo, содержащий public метод int score(vector <string> cards).

Пишем решение задачи:
http://codepad.org/EMkgXA2X

Пытаемся его скомпилировать. Успешно.
Далее проверяем свой код на тестах из условия (Test). Так же можно ввести свой тест, который будет соответствовать ограничениям, и увидеть, какой результат выдала программа.
Завершаем работу с задачей нажатием на кнопку Submit и закрытием окна Coding Phase.

Так как это комната для тренировок – решение можно сразу протестировать, выбрав Practice Options --> Run System Test.
При верном решении цифры 250 загорятся зелёным, при неверном можно будет увидеть тест, на котором программа отработала некорректно.

Теперь поговорим о формате соревнований TopCoder Algorithm.
Соревнование называется SRM - Single Round Match. Расписание SRMов можно увидеть здесь, или, например, используя различные готовые календари (пример). Матч длится 1 час 35 минут. На решение задач (Coding Phase) даётся 1 час и 15 минут, 5 минут (Intermission) даётся на передышку и подготовку тестов для третей части - Challenging Phase.

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

За успешную попытку челленджа вам начисляется 50 дополнительных очков, за неуспешную – снимается 25. Челленджить с отрицательным количеством очков нельзя!

На контесте предлагается три задачи, которые обычно стоят 250, 500 и 1000 очков. Очки, которые вы получите за задачу, определяются разностью времени открытия задачи и посылки её (Submit). Существует возможность повторной отправки задачи – в этом случае время пересчитывается, относительно времени последней посылки, и снимается 10% очков за каждую повторную посылку, но вы получите как минимум 30% очков задачи.

После Challenging Phase происходит System Testing Phase, где все выдержавшие челлендж решения тестируются на заранее приготовленных тестах + тестах, которые успешно уронили чужие решения в предыдущей фазе. Если задача была решена верно – вы сохраняете свои очки по ней, в противном случае вы получаете 0 очков за неё.

Затем все участники сортируются по количеству очков, набранных за контест, и идёт пересчёт общего рейтинга участников. Все участники разбиты на 2 дивизиона: 1200 и больше очков рейтинга – I Дивизион, меньше 1200 – второй.

Надеюсь эта статья поможет кому-либо испытать новые ощущения от решения задач.


Искренне ваш, пока ещё жоолтый,

dAFTc0d3r.

UPD. Часть #2: Плагины для C++ и внешней среды разработки (MS Visual Studio)