Logo

SnarkNews on Яндекс.Алгоритм - 2011

General Sponsor
 

Правила турниров, проводящихся по схеме Codeforces.

Перед началом соревнования участники разбиваются на комнаты, в каждой комнате от 20 до 50 участников. Разбиение по комнатам возможно как случайным образом, так и с учётом рейтинга.

Участникам предлагается для решения некоторое количество задач. Задачи обычно располагаются в порядке возрастания возрастания сложности и максимального балла (то есть при пяти задачах задача A - самая простая, задача E - самая сложная). В момент начала соревнования условия всех предложенных задач становятся доступны для просмотра. Решением задачи является исходный код, написанный на одном из установленных в тестирующей системе и открытах для участников данного соревнования языков программирования. Отправлять решения на проверку можно в течение фиксированного времени (определяемого правилами соревнования и называемого продолжительностью турнира), начиная с момента старта соревнования. Обычно на турнирах Codeforces количество задач равно 5, а продолжительность соревнования - 2 часа.

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

Во время соревнования задача проверяется только на предварительном наборе тестов, который недоступен участникам и является одинаковым для всех участников. Решение считается прошедшим некоторый претест или тест в том случае, если оно выдаёт верный ответ на данный претест или тест и не выходит за установленные правилами турнира ограничения (чаще всего - по времени работы и используемой памяти).

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

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

Участник, заблокировавший задачу, получает доступ на всё оставшееся время соревнования к исходным текстам решений этой задачи, отправляемым другими участниками из той же комнаты, и может попробовать провести взлом решения. В процессе взлома взламывающий участник предлагает тест (в виде файла или генератора), который, по его мнению, взламываемое решение не проходит. Взламывать можно только предварительно верную посылку данного участника по данной задаче; в частности, возможны случаи, когда автор решения успешно переотправил решение за небольшое время до взлома; при этом попытка взлома игнорируется. Также попытка взлома игнорируется в случае, если тест не соответствует условию, произошла ошибка при генерации теста или генератор теста нестабилен. Если попытка взлома не проигнорирована, то взламываемое решение запускается на предложенном тесте. В случае, если решение не прошло предложенный тест, взлом считается успешным, если прошло - взлом считается неуспешным. При успешном взломе взламываемая посылка объявляется неверной.

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

Участникам доступна таблица соревнований, в которой участники ранжируются по текущему результату (чем больше результат, тем лучше место). Текущим результатом участника является сумма баллов, полученных по всем условно сданным задачам, а также баллов, полученных за взломы задач. Если задача на данный момент не является условно сданной, участник получает за неё 0 баллов.
Для каждой условно сданной задачи баллы вычисляются по формуле

max ((Prob_score * (1 - Submit_time / 250) - 50 * Bad_submits), Prob_score * 0.3), где
  • Prob_score - изначальная цена задачи, определяемая авторами проблемсета (обычно кратна 500),
  • Submit_time - количество минут, прошедших с момента начала соревнования до времени отправки посылки, на данный момент являющейся предварительно верной,
  • Bad_submits - количество посылок, сделанных до посылки, на данный момент являющейся предварительно верной (в том числе взломанных посылок или ранее отправленных предварительно верных посылок).

За каждый успешный взлом результат увеличивается на 100 баллов, за каждый неуспешный взлом - уменьшается на 50 баллов.

После завершения времени соревнования происходит системное тестирование: все решения, являющиеся на данный момент предварительно верными, проверяются на полном наборе тестов, который недоступен участникам и является одинаковым для всех участников. Если предварительно верное решение не прошло полный набор тестов, за соответствующую задачу количество баллов уменьшается до 0, если прошло - сохраняется текущее количество баллов. Баллы, полученные в результате взлома, при системном тестировании не меняются.

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