group-telegram.com/cxx95/31
Last Update:
Как готовятся задачи к олимпиадам по программированию? (Часть 2/2)
Подготовка задачи ведется на сайте polygon.codeforces.com. Это самая продвинутая платформа, долгое время была практически единственной. Другие платформы (Яндекс.Контест, CodeChef, etc.) со временем потырили у нее фичи - валидацию, встроенную систему контроля версий, и прочее.
Для программок (генераторы, чекеры, etc.) используется библиотека testlib.h.
Процесс подготовки задачи состоит из этих пунктов (могут идти в произвольном порядке, кроме п.1):
(1) Придумывается не-баянистая идея для задачи в краткой формулировке.
(2) Создается художественное описание задачи в LaTeX - пример, это называется "легенда".
(3) Пишутся генераторы тестов, таких программок может быть несколько - пример 1, пример 2. Они могут запускаться с разными параметрами.
(4) Пишется валидатор, он нужен для проверки, что сгенерированные тесты имеют правильный формат и удовлетворяют ограничениям из условия задачи - пример.
(5) Список тестов создается через движок шаблонов Freemarker. Можно написать скрипт, который потом преобразуется в список запусков генераторов - пример из документации. В нашей задаче 100 тестов - список.
(6) Надо написать решение задачи. Есть одно эталонное правильное решение - пример, но надо также выдумать и написать все возможные неправильные решения, чтобы смотреть, смогут ли они пройти все (или почти все) тесты, и скорректировать тесты от этого.
(7) Чекер проверяет решение участника на правильность. На polygon есть дефолтные чекеры для простых задач, но если в задаче может быть несколько правильных ответов, то нужен свой чекер - пример.
Это дело достаточно серьезное, поэтому проводится перекрёстное код-ревью задач вместе с коллегами-проблемсеттерами и вычитка легенды.
Также примерно 5-15 человек разных рейтингов прорешивают задачу, не зная заранее решения. Они могут придумать неожиданное решение попроще, или заслать неправильное решение - все эти кейсы рассматриваются отдельно.
По закону больших чисел, на одну из десятков задач могут происходить факапы такого рода:
(1) Много участников додумались до решения проще авторского и реальная сложность задачи преувеличена
(2) Задача имеет слабые тесты, из-за чего проходит много "плохих" решений.
(3) Авторское решение неправильное.
Первые два типа факапов это еще ничего, а третий тип это полный треш, и на codeforces контест из-за этого просто отменяют (точнее, делают "нерейтинговым", и участвовать в нем нет смысла).
BY C++95
Share with your friend now:
group-telegram.com/cxx95/31