C++95

C++95

#story Как готовятся задачи к олимпиадам по программированию? (Часть 1/2) Наверное, много кто пробовал решать задачки: на codeforces.com, школьных олимпиадах, ACM ICPC, и в других местах. Большинство людей использует C++ для решения. Я раньше очень увлекался…

Как готовятся задачи к олимпиадам по программированию? (Часть 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 контест из-за этого просто отменяют (точнее, делают "нерейтинговым", и участвовать в нем нет смысла).

www.group-telegram.com/cn/cxx95.com/31

456 viewsMay 18, 2022 at 15:09

Как готовятся задачи к олимпиадам по программированию? (Часть 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