Кубок И.Н. Векуа - 2012

Ilya N.Vekua
 

Правила личного турнира VI Кубка Векуа (Computable Problem Rating).

Проведение турнира

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

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

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

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

СообщениеНомер теста сообщается?Когда возникаетВозможная причина
OKнетрешение зачтенопрограмма на соответствующем наборе тестов работает верно
Compilation error нет компиляция программы завершилась с ошибкой 1. в программе допущена синтаксическая или семантическая ошибка
2. неправильно указан язык
Wrong answer да ответ не верен 1. ошибка в программе
2. неверный алгоритм
Presentation error да программа проверки не может проверить
выходные данные, так как их формат
не соответствует описанному
1. неверный формат вывода
2. программа не печатает результат
3. лишний вывод
Time-limit exceeded да программа превысила установленный
в условии лимит времени
1. ошибка в программе
2. неэффективное решение
Memory limit exceeded да программа превысила установленный
в условии лимит памяти
1. ошибка в программе (напр., бесконечная рекурсия)
2. неэффективное решение
Run-time error да программа завершила работу с ненулевым
кодом возврата
1. ошибка выполнения
2. программа на языке C/C++ не завершается оператором return 0
3. ненулевой код возврата указан явно

При возникновении ошибки Compilation error программа не запускается ни на одном тесте. При возникновении ошибок Run-time error, Memory limit exceeded, Time-limit exceeded вывод программы не проверяется.

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

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

Подсчёт промежуточных и окончательных результатов

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

Текущий балл каждого участника по каждой решённой задаче вычисляется как T*S*X(p),где

  • X(p) - сложность задачи (в течение контеста меняется в зависимости от числа p сдавших задачу на данный момент)
  • T - временной коэффициент, вычисляется в момент сдачи задачи и в течение контеста не меняется. В данном варианте правил T меняется линейно от 1 до 0.75.
  • S - "коэффициент чистоты", зависящий от числа попыток, затраченных на задачу. Определяется в момент сдачи задачи и в течение контеста не меняется.

За нерешённую задачу участник получает 0 баллов.

Временной коэффициент T вычисляется в момент успешной сдачи данной задачи участником по формуле
T=1-(время_с_начала_контеста)/(4*продолжительность_контеста).
Время от начала контеста и продолжительность контеста измеряются с точностью до секунды. Повторная успешная сдача одной и той же задачи на таблицу результатов не влияет.
Например, в момент старта контеста T=1, в момент завершения T=0.75, в середине контеста T=0.875.

"Коэффициент чистоты" S равен 1.2, если задача сдана с первой попытки, 1.1, если сдана со второй, 1.05, если с третьей. В остальных случаях S=1.

Сложность X(p) задачи рассчитывается так:
X(p)=k*(p+10)-2/3,
где p - количество участников, решивших соответствующую задачу на текущий момент, k=1000*(121)1/3 (примерно 4946.0874). Коэффициент подобран так, что сложность задачи, сданной единственным участником, оценивается в тысячу баллов.

Ниже приведена таблица, содержащая значения функции X для некоторых значений p:

Количество сдавших задачу участников, p Сложность задачи, X
11000.00
2943.64
3894.61
5813.21
10671.29
15578.50
25462.26
50322.72
100215.44

Например, пусть участник сдал со второй попытки задачу, которую до него сдали ещё 9 участников, на 1800 секунде при продолжительности контеста 7200 секунд. Тогда T=1-1800/(4*7200)=0.9375, S=1.1, T*S=1.03125. На момент сдачи задачи у участника будет T*S*X(10)=1.03125*671.29=692.27 балла. Пусть по окончании контеста эту задачу сдало 50 участников, тогда итоговый результат данного участника по задаче будет T*S*X(50)= 1.03125*322.72=332.80 баллов.

Итоговым результатом участника считается сумма баллов по каждой задаче, вычисленная с использования значений X на момент окончания контеста. Таблица результатов после проверки последнего сабмита объявляется итоговой.
При этом возможна заморозка текущих результатов соревнования по истечении 4/5 времени контеста.

Итоговым местом участника считается место в итоговой таблице результатов.