Добрый день, Codeforces!

Сегодня я расскажу вам о новой функции системы Polygon, в которой готовятся все задачи для раундов Codeforces. Конечно, система открыта для любых пользователей — в ней подготавливается большое количество контестов для других соревнований или сборов.

Двумя ключевыми элементами задачи, помимо авторского решения, тестов и условия, являются две программы: валидатор и чекер.

Валидатор (англ. Validator) — это программа, которая считывает тест и сообщает, соответствует ли он условию задачи или нет. Валидаторы необходимо писать абсолютно формально — валидатор пропускает тест тогда и только тогда, когда он соответствует условию задачи и может быть спокойно добавлен в набор тестов. Валидаторы удобно писать с помощью библиотеки testlib.h. Иногда авторы пренебрегают валидаторами (на соревнованиях Codeforces такого не случается), что ставит под угрозу корректность тестов. Так как в соревнованиях Codeforces присутствуют взломы, важность правильности валидатора значительно возрастает. Естественно, все взломы перед тем, как попасть к решению участника, проходят валидацию. В большинстве задач валидаторы относительно простые, но когда в задаче появляются дополнительные условия (например, что решение для теста существует), то сложность валидатора значительно возрастает.

Чекер (англ. Checker) — это программа, которая на вход получает тест, вывод программы участника и вывод программы жюри и определяет правильность вывода участника. К сожалению, ошибки в чекерах часто приводят к тяжелым последствиям. Далеко не во всех задачах можно просто сравнить ответы на равенство. Например, в задаче 234H - Слияние двух колод в чекере используется декартово дерево. Если по условию задачи требуется сертификат, то чекер лучше всего писать в концепции readAnswer(ans)/readAnswer(ouf). Это концепция и многое другое по теме разработки чекеров описано в древнем посте Чекеры, testlib.h и просто по теме. Чекеры удобно писать с помощью библиотеки testlib.h.

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

В обновленной версии Polygon всё стало значительно лучще! Мы сделали удобные средства для тестирования валидатора и чекера.  

Тесты для валидатора тестов

Такое средство теперь доступно в системе Polygon. Тесты отображаются на странице Validator. Вы легко можете добавить за раз много тестов, разделяя их специальным маркером. Для каждого добавленного теста укажите ожидаемый вердикт валидатора (valid или invalid). Там же можно запустить эти тесты на проверку. Тесты валидатора являются полноценной частью задачи и попадают в пакет задачи. По этой причине обновлен формат problem.xml, вот пример расширенного описания валидатора (элементы binary и testset — опциональны):

<validator>
    <source path="files/v.cpp" type="cpp.g++"/>
    <binary path="files/v.exe" type="exe.win32"/>
    <testset>
        <test-count>2</test-count>
        <input-path-pattern>validator-tests/%02d</input-path-pattern>
        <tests>
            <test verdict="valid"/>
            <test verdict="invalid"/>
        </tests>
    </testset>
</validator>

Если у валидатора нет тестов, то вы получите традиционное полигонное предупреждение.

Тесты для чекера

Здесь всё аналогично. Такие тесты создавать чуть сложнее, так как необходимо ввести не только input, но и output (вроде как вывод участника) и answer (вроде как ответ, вывод авторского решения). Для стандартных чекеров тесты создавать не нужно. Вот пример обновленного описания чекера из problem.xml (элементы binary, copy, testset — опциональны):

<checker name="std::wcmp.cpp" type="testlib">
    <source path="files/check.cpp" type="cpp.g++"/>
    <binary path="check.exe" type="exe.win32"/>
    <copy path="check.cpp" type="cpp.g++"/>
    <testset>
        <test-count>4</test-count>
        <input-path-pattern>checker-tests/%02d</input-path-pattern>
        <output-path-pattern>checker-tests/%02d.o</output-path-pattern>
        <answer-path-pattern>checker-tests/%02d.a</answer-path-pattern>
        <tests>
            <test verdict="ok"/>
            <test verdict="wrong-answer"/>
            <test verdict="wrong-answer"/>
            <test verdict="presentation-error"/>
        </tests>
    </testset>
</checker>

Если у нестандартного чекера нет тестов, то вы получите традиционное полигонное предупреждение.

Напоследок

Как вы видите, все изменения problem.xml обратно совместимы. Проверка тестов встроена в скрипты развертывания задачи doall.bat/doall.sh. При импорте задачи вы вручную или автоматизировано можете проверить прохождение тестов, так как они формально описаны в problem.xml и содержатся в пакете задачи.

Я уверен, что наличие такого инструмента позволит облегчить жизнь авторов задач и уменьшит вероятность ошибок.

С уважением, Иван.