Topcoder

Topcoder, Inc
Изображение логотипа
Тип Корпорация
Основание Апрель, 2001
Расположение Флаг США США, Коннектикут, Гластонбери
Отрасль Кадровое обеспечение в области информационных технологий
Разработка программного обеспечения
Услуги аутсорсинга
Число сотрудников 75 (2006)[1]
Сайт www.topcoder.com

Topcoder — корпорация, проводящая соревнования по спортивному программированию. В отличие от ACM International Collegiate Programming Contest, все соревнования являются индивидуальными.

Создан в апреле 2001 года. По состоянию на июль 2008 года насчитывал более 160 000 пользователей, из которых около 28 000 хоть раз участвовали в Algorithm Competition.

Разновидности соревнований

Алгоритмы (англ. Algorithm Competition)

Наиболее популярный вид турниров — соревнование по быстрому решению алгоритмических задач (аналогично школьным и студенческим олимпиадам по программированию). Он заключается в том что каждому участнику даётся 3 задачи, разные по сложности, классифицируемые на 3 уровня. Каждая задача имеет свою максимальную стоимость в баллах. Обычно 250, 500 и 1000. Баллы начисляются только за решения, признанные верными, частичные решения не учитываются. Перед началом соревнования участников распределяют по виртуальным комнатам (до 20 человек).

Такие матчи, называемые SRM (Single Round Match), проходят примерно раз в две недели. Кроме этого проводятся ежегодные турниры. Матч состоит из трёх основных фаз — Coding, Challenging и System Testing.

Этап программирования англ. Coding Phase

В первой фазе участники за отведённое время пытаются решить предложенные им три задачи, как правило оцениваемые в 250, 500 и 1000 баллов. Решением является создание указанного в условии класса и реализация указанного в условии метода, проходящая все заранее подготовленные тесты. Участникам разрешается писать решения на одном из следующих языков: C++, C#, Java, VB.NET или Python. Количество очков за решённую задачу нелинейно зависит от времени отправки окончательного решения: чем позже — тем меньше очков. За каждую повторную отправку снимается 10 % стоимости задачи. Количество очков не может быть меньше 30 % стоимости задачи.

Продолжительность тура в регулярных матчах (англ. Single Round Match, сокращенно SRM), а также отборочных соревнованиях турниров (англ. Online Elimination Rounds) составляет 75 минут. В очном финале (англ. Onsite Events) продолжительность первой фазы составляет 85 минут.

Этап соревновательного тестирования англ. Challenging Phase

Во второй фазе участники пытаются подобрать тест (вариант входных данных), на котором решения его конкурентов (которые находятся в той же виртуальной комнате) будут работать неверным образом. При этом разрешается смотреть исходный код, но невозможно (нельзя) запускать программы конкурентов. Каждый удачный подход даёт 50 очков, а неудачный отнимает 25 очков. Если подход был удачным, тест может быть добавлен в набор тестов, используемый на следующей фазе. Продолжительность этой фазы составляет 15 минут во всех матчах кроме очных финалов (10 минут). Участнику запрещается пробовать подбирать тест, на котором другие решения не работают, если количество его баллов не положительно.

Этап окончательного тестирования англ. System Testing Phase

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

Итоги

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

В случае, если в ходе соревнования не происходило никаких технических сбоев, для всех участников пересчитывается рейтинг.

Проектирование и разработка (англ. Design and Development Competition)

Это наиболее приближенный к промышленному программированию вид соревнований. В них участвуют пары программистов. Первый пишет подробную спецификацию для некоторого компонента, заказанного сторонней фирмой, а второй реализует её на .NET-языке или Java. Работа оценивается несколькими жюри, и по их оценке выставляется итоговый балл.

Марафоны (англ. Marathon Competition)

В марафонах участники решают более сложные и нестандартные задачи, чем на прочих видах соревнований по олимпиадному программированию. В марафонах нет разделения на дивизионы, и даётся лишь одна задача в каждом соревновании. В отличие от Algorithm, «правильный» или наилучший алгоритм неизвестен даже автору задачи. Часто для каждого набора входных данных существуют лучшие и худшие ответы, и программа, всегда находящая оптимальный ответ за разумное время, неизвестна автору задачи, а возможно, и не существует. Участник должен написать программу, находящую как можно лучший ответ за заданное время (в типичном случае 10 секунд). В некоторых случаях необходимо найти правильный ответ за минимальное время. Есть и другие варианты.

На решение задачи обычно отводится 1 или 2 недели.

Участникам разрешены:

  • Пробные тесты. Программа, посланная участником, тестируется на 10 заранее известных наборах данных. Участник получает результаты работы программы, её вывод и время работы для каждого набора данных. Другие участники могут узнать только о факте пробного теста. Пробный тест можно выполнять раз в 10 минут.
  • Полные тесты. Программа тестируется на 100 секретных, случайно сгенерированных до начала соревнования наборах данных, одинаковых для всех участников и постоянных на протяжении всего соревнования. Участнику сообщаются лишь суммарные баллы, набранные программой. Имя участника и набранные им в последнем полном тесте баллы заносятся в таблицу, доступную всем участникам. Полный тест можно выполнять раз в 1 час.

После завершения приёма решений программы, посланные на полный тест (от каждого участника берётся последняя его программа), тестируются на большом количестве (обычно 500) секретных, случайно сгенерированных наборов данных, одинаковых для всех участников. Участники получают места в зависимости от набранного ими количества баллов.

Краткое описание некоторых задач

Ниже даны примеры задач, предлагаемых в марафонах. В примерах опущены многие детали.

  • SubgraphIsomorphism. Даны граф G и граф H вершин, изоморфный подграфу графа G. Найти, какой вершине графа G соответствует каждая вершина графа H. Если граф H изоморфен двум или более подграфам графа G, принимается любой из изоморфизмов. Программа получает сначала граф G и граф H из 5 вершин, после правильного ответа другой граф H из 6 вершин, после правильного ответа новый граф H из 7 вершин и так далее. Баллы равны количеству подграфов, для которых программа успела найти изоморфизм. Время работы программы — не более 10 секунд.[1] Архивная копия от 13 апреля 2012 на Wayback Machine
  • CellularAutomaton. Даны правила поведения клеточного автомата в прямоугольной области, начальная позиция, N и K. Найти начальную позицию, отличающуюся от данной не более чем в N клетках, такую что через K шагов количество живых клеток будет как можно больше. Баллы равны отношению количества живых клеток к общей площади прямоугольника, в котором работает клеточный автомат.[2] Архивная копия от 25 мая 2014 на Wayback Machine
  • Planarity. Дан граф. Найти плоскую укладку графа, при которой вершины будут точками в целочисленной решётке 700×700, а рёбра — отрезками, соединяющими вершины, такую что количество пересечений рёбер будет как можно меньше. Баллы обратно пропорциональны количеству пересечений рёбер.[3] Архивная копия от 13 апреля 2012 на Wayback Machine

Рейтинг

Topcoder является первым и наиболее престижным видом спортивного программирования, в котором существует система рейтинга участников, зависящего от их выступлений в онлайн-соревнованиях. На его основе сделан закрывшийся белорусский сайт Test The Best и российский Codeforces.

Система рейтинга делит участников на следующие категории:

Цвет группы Рейтинг
Белые Ни разу не выступавшие участники
Серые менее 900 очков
Зеленые 900—1199 очков
Синие 1200—1499 очков
Желтые 1500—2199 очков
Красные 2200 очков и более
Лидеры (англ. target) 3000 очков и более

Участники Algorithm Competition, имеющие рейтинг не ниже 1200, выступают в первом дивизионе. Все остальные — во втором. На 18 января 2010, жёлтый рейтинг Algorithm Competition имеют примерно 800 сильнейших программистов, красный — около 200, «Target» — всего 17 человек в мире.[2]

В Design, Development и Marathon Matches уровень Target ещё не удавалось получить никому, а красную группу составляют не более 10 человек (в Development — всего двое).

Соревнования

Самые крупные из турниров — Topcoder Open (неофициальный чемпионат мира по программированию среди профессионалов) и Google Code Jam (до 2007 года, начиная с 2008 проводится компанией Google самостоятельно[3]).
Кроме них, до 2007 года включительно проводился турнир для студентов — TopCoder Collegiate Challenge.[4].
Начиная с 2006-07 гг проводятся отдельные матчи и годовой турнир для школьников — TopCoder High School.

Примечания

  1. ↑ Topcoder Jobs and Profile. Yahoo! HotJobs. Дата обращения: 29 ноября 2006. Архивировано 1 июня 2005 года.
  2. ↑ TopCoder Statistics — Top Ranked Algorithm Competitors. Дата обращения: 18 января 2010. Архивировано 17 января 2021 года.
  3. ↑ Правила Code Jam. Дата обращения: 25 июня 2008. Архивировано 22 июня 2008 года.
  4. ↑ The TCCC: A Difficult Decision. Дата обращения: 25 июня 2008. Архивировано 19 февраля 2011 года.

Ссылки