В этом посте речь пойдёт о тестировании еще одного типа нестандартных задач. Они иногда встречаются на Всероссийских сборах школьников, а также на каждом Codechef Long Contest. Я говорю о неточных задачах, в которых участник оценивается относительно лучшего в некотором смысле решения среди жюри и всех участников. Обычно тесты оцениваются независимо, а оценка за тест — некая функция от "хорошести" решения участника и лучшего результата на этом тесте.
На данный момент поддержка таких задач в известных мне системах (Testsys, PCMS2, eJudge) возможна лишь костылём. Например, используется ровно один judge/invoker и на нём же в специальных файликах хранятся текущие лучшие результаты по каждому из тестов. После конца контеста требуется перетестировать все посылки, чтобы каждая была оценена исходя из глобально лучшего ответа, а не лучшего на момент посылки. Конечно, вместо этого можно скриптами подправить логи тестирования, но этот костыль тоже не блещет красотой.
Так как в существующих условиях нормально реализовать поддержку таких задач не представляется возможным (например, отсутствует хоть какая-то возможность влияния одних решений на результат других), я предлагаю разработать общий "стандарт" для написания и тестирования таких задач.
Итак, предложения (спасибо Gassa за помощь при формулировке и разработке):
Можно считать, что для выставления оценки за тест достаточно некоторой информации об ответе, меньшей, чем сам ответ (назовём её целевой функцией). Я не видел ни одной задачи, где это не было бы числом (например, длина пути коммивояжёра). Тем не менее, "с заделом на будущее" можно считать эту информацию последовательностью чисел и строк (сравниваются лексикографически). Последовательности также сравниваются лексикографически. Что при этом считать лучшим ответом — параметр задачи (например, надо минимизировать первый элемент, а при равенстве — максимизировать второй и т.д.). Погрешности сравнения вещественных чисел выставляются как параметры задачи, возможно, с некоторыми умолчаниями.
Хочется избавиться от необходимости перетестирования/ручной правки логов в конце/процессе контеста. Для этого предлагается отделить функциональность выставления баллов за тест от чекера. На чекер ложится обязанность выставить WA/PE/OK (вердикт PC/Partially Correct убирается) и выдать в комментарии значение целевой функции. Разумеется, не хочется терять комментарий в его стандартном смысле, поэтому предлагаю выводить в формате <комментарий><перевод строки><значение целевой функции>. Например:
Looks good\n123 abacaba 44.5При этом чекеру совершенно незачем знать текущий лучший ответ, и пропадает необходимость передавать его на тестирующую машину.Таким образом, тестирующая система для получения фактического балла за тест (мне кажется, лучше выдавать процент от максимально возможного балла за тест, нежели сами баллы) должна запустить программу выставления баллов (назову её valuer по аналогии с ejudge) и передать ей на вход значение целевой функции участника и лучшее значение целевой функции.
Также тестирующая система для каждого теста (тесты стоит различать по хэшу, а не по номеру и дате изменения файла) хранит лучшее значение целевой функции и файл с ответом, на котором это значение было достигнуто. Последнее рекомендуется на случай проверки руками.
Исчезает необходимость перетестирования в конце контеста: достаточно еще раз запустить valuer для каждой посылки.
Впрочем, у меня остались некоторые неразрешённые вопросы:
Для выставления баллов за решение в текущей модели требуется довольно дорогостоящий запуск отдельного процесса. Мне не хочется запускать "чужой код" вне песочницы, поэтому тратится еще и время тестирующей машины. Возможное решение: использовать для написания valuer'а некоторого популярного/простого скриптового языка (например, EcmaScript/JavaScript или Lua), который легко проинтерпретировать и ограничить в правах. Тогда можно будет запускать его хоть после каждого сабмита и показывать результаты онлайн.
Если брать скриптовой язык — то какой? Хотелось бы выбрать один на всех. EcmaScript, как мне кажется, более известен и больше похож на C/C++/Java. С другой стороны, существующие интерпретаторы EcmaScript довольно громоздки. Lua же предоставляет легковесный интерпретатор с привязками ко многим языкам (C++, Delphi, Java, Python), однако он не слишком популярен и использует другой синтаксис (например, end вместо фигурных скобок, комментарии двойными дефисами и прочее). В остальном языки довольно схожи.
Прошу высказаться всех интересующихся, в особенности разработчиков тестирующих систем. Надеюсь на продуктивное обсуждение.
UPD: выложил пример чекера и valuer'а на C++ для задачи о коммивояжёре. Также есть пример valuer'а на javascript.
В конфиг testsys'а для такой задачи могут добавиться такие строчки:
# Целевая функция состоит ровно из одного токена, который надо минимизировать
# В случае большего количества токенов строка может выглядеть как "<<><"
DynamicScoringComparator = "<";
# DynamicScoringAbsoluteEps = 0.000000001; # По умолчанию
# DynamicScoringRelativeEps = 0.000000001; # По умолчанию
DynamicScoringValuer = $probdir\valuer.exe
Comments (0)
