В этом посте речь пойдёт о тестировании еще одного типа нестандартных задач. Они иногда встречаются на Всероссийских сборах школьников, а также на каждом 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
Небольшой оффтопик: Burunduk1, когда проводил сборы в Алма-Ате в КБТУ прошлой весной, каким-то образом ставил марафонские задачи на Testsys, причем баллы выставлялись онлайн. Тебе стоило бы обсудить эту тему с ним.
Возможно, там выставлялись баллы относительно жюри, а не всех участников. Такое TestSys поддерживает. Спрошу, спасибо.
Насколько я помню, все-таки относительно лучшего решения.
Выяснил. Использовался костыль, описанный в посте: результаты показывались в процессе, но оценка была относительно лучшего из уже посланных. В конце контеста был полный retest.
А точно бывают задачи, где надо поддерживать много токенов? Кажется, что тогда будет довольно сложно придумать правильную метрику для определения баллов относительно лучшего решения. Может даже, если ответ многокритериальный, его можно переводить в некоторое число на стадии чекера?
Просто в таком случае все значительно упрощается. Можно просто использовать quitp из testlib.h, DynamicScoringComparator превращается в булевый флажок, формат файлика с результатами для valuer становится статичным.
Идея использовать скриптовый язык — мне не очень. Окажется, что его знают единицы. При написании сложного valuer-а будут возникать грабли в связи со слабым знанием языка, низкой производительностью. Lua вообще плохой выбор — версия 5.1 не была совместима с 5.0. Нельзя писать инфраструктурный код для задач на языке без гарантированной обратной совместимости. Что делать потом будущим поколениям с такими исходниками? Мне кажется не надо ограничивать в целом выбор языка для valuer, а надо работать с ним так же как с checker/validator/interactor.
Я не видел. Но вдруг, например, захочется найти что-нибудь в стиле lexmin mincost maxflow? Или лексикографически минимальную строку, удовлетворяющую некоторым условиям (не обязательно минимальной длины)? Строк, меньших данной лексикографически бесконечно много.
Тогда, правда всё равно можно записать строку как вещественную часть числа. Но потребуется его очень точно хранить и сравнивать, например, в BigDecimal. Решение, но похоже на костыль.
А так жить стало бы действительно лучше.
Кстати, да, любое линейно упорядоченное множество изоморфно подмножеству [0, 1]. Так что можно считать значение целевой функции числом с точностью до того, что я указал выше.
Несколько несистематизированных комментариев.
(1.) Если утверждать что-то такое на уровне кросс-системного стандарта — конечно, хочется, чтобы была возможность полностью разделить логику checker-а (проверка правильности ответа) и scorer-а (баллы за ответ). Сейчас они живут в одном файле только потому, что scorer в текущем формате задачи некуда больше прицепить.
(2.) Название valuer может значить тысячу вещей. Хочется чего-то более конкретного, например, scorer.
(3.) Система оценки даже сейчас, когда надо делать костыли, бывает очень разная:
Есть задачи с потестовой оценкой, есть задачи с оценкой на группах тестов.
Бывает бинарная оценка теста (правильно или нет), бывает зависящая от какой-то заранее известной константы (теоретический оптимум), бывает зависящая от найденных ответов (соревновательная между участниками; возможно, включая жюри).
Зависимость баллов за тест от ответа тоже бывает разная (линейная, логарифмическая, степенная, ранг участника среди всех участников, ...).
И всё это может переплетаться. Например, на одной из недавних IOI была задача, где за всю группу тестов получались баллы, зависящие от худшего из результатов на тестах этой группы.
Если же фантазия автора задачи не будет ограничена тем, что очередную систему оценки надо несколько часов прикручивать к тестирующей системе — смогут появиться и новые интересные и полезные для конкретных задач системы оценки.
Так вот, если уж затевать общий стандарт оценки, логично покрыть все известные случаи оценки, а не какие-то специальные. То есть задачи с потестовой соревновательной оценкой — это хоть и сложная, но только часть того, что хочется уметь оценивать.
(4.) Поэтому хочется, чтобы scorer был хотя бы скриптом на настоящем языке программирования (C, Python, Lua, ...) и не врастал в системно-зависимые конфиги строчками вида DynamicScoringComparator = "<". Может быть, вообще получится использовать его так же, как сейчас используется чекер — писать на чём угодно, компилировать и запускать бинарник так же, как чекер. А он просто выдаст в стандартный поток вывода одно число — итоговый балл за посылку.
(5.) Формат, в котором хранится информация для оценки, тоже не хочется как-то сильно ограничивать. Это может быть, например, произвольный текстовый файл, начало которого — комментарий чекера о том, что всё хорошо. Или, например, файл, содержащий таблицу уже на языке Lua, которую осталось куда-нибудь присвоить и как-нибудь обработать.
(6.) Я вижу два пути, по которым из ответа участника может получиться оценка:
output -> (run checker) -> comment&scoring-info -> (run scorer) -> scoreили
output -> (run scorer) -> scoreнапрямую. Я пока не понимаю, какой вариант лучше.
С одной стороны, чекер может быть совершенно не связан с оценкой. Например, число, нужное для оценки, и так написано в первой строке output-а, а чекер лишь проверяет, что дальнейший output согласован с этим числом. И тогда вставлять в код чекера информацию для scorer-а нелогично.
С другой стороны, информация для выставления баллов может частично получаться в ходе работы чекера, и тогда этот код придётся (на другом языке) дублировать в scorer-е. И это, казалось бы, уже практически (а не идеологически) плохо.
Может быть, можно как-то поддержать оба варианта?
(7.) Из соображений безопасности хочется запускать scorer — как и checker — на инвокере, а не на компьютере с тестирующей системой. Но для задач с соревновательной оценкой он должен иметь доступ к файлам, хранящимся централизованно в тестирующей системе — иначе будет отдельное "соревнование" на каждом инвокере. Видимо, их придётся кидать на инвокер при каждом запуске scorer-а. Избавиться от тормозов поможет кеширование.
Предложу альтернативную схему (не факт, что она лучше, чем предложенная Егором, но в ней есть какой-то смысл).
Сначала проверка задачи идёт как обычно, записываются ответы участника и комментарии чекера.
После того, как вся проверка прошла, на инвокере запускается scorer, которому в папку кладутся все файлы вида XX/XXX (входные), XX.a/XXX.a (ответы жюри), XX.output/XXX.output (ответы участника), XX.comment/XXX.comment (комментарии чекера). И ещё XX.internal/XXX.internal — что-нибудь для хранения соревновательной части, которая накапливается по ходу контеста. Много-много файлов, без кеширования никуда.
Как, которые из этих файлов и в каком порядке обрабатывает scorer — его дело. Но в итоге он должен выдать тестирующей системе (не знаю, как именно — как текст в stdout, как код возврата, как сообщение в системно-зависимом формате) одно число — сколько баллов поставить участнику за эту задачу. Обычно в современных задачах это целое число от 0 до 100. Ну и изменившиеся *.internal система забирает обратно.
Сразу недостаток 1: *.internal придётся лочить, при их наличии работа такого scorer-а не распараллеливается. То есть в один момент времени на всех X инвокерах может быть запущен не более чем один скорер по каждой задаче. Если запускать scorer не на всех тестах сразу, а на каждом в отдельности, этот недостаток минимизируется (не более чем один скорер для пары задача+тест). Но тогда будет неудобно оценивать сразу группы тестов.
Но есть и преимущество 1: это вроде бы покрывает все схемы scoring-а, которые сейчас возможны при помощи костылей.
Преимущество 2: легко перезапустить из тестирующей системы эту часть, не перетестируя все решения на всех тестах.
Преимущество 3: scorer можно написать на любом удобном языке. Можно, например, стандартизировать поддержку таких scorer-ов в C++ testlib.
Мне в такой схеме (как и в valuer'ах eJudge) не нравится количество информации, которую получает участник — оно ограничено суммарным баллом за задачу, хотя всегда можно выдать больше. Например, какая группа была пройдена, а какая нет. В случае той самой задачи с IOI — худший результат по подруппе.
Вступительные мысли:
, которым проще доставить плашку на 4GB, нежели оптимизировать код.Вот еще одна схема:
quitp. Если scorer отсутствует, можно разрешить чекеру возвращать PC для упрощения разработки стандартных задач и обратной совместимости.Еще раз основные идеи, кратко: разделение оценки посылки в целом и оценки каждого теста (на valuer и scorer, соответственно), использование scorer для обновления оптимумов (в зависимости от его кода возврата — PC/OK), использование valuer'a необязательно (например, выставление минимума за группу тестов мажорирует все системы оценки, которые я видел).
Плюсы: участник получает максимум информации, не обязательно использование valuer, необязательно использование scorer, не требуется доработка testlib/разработка нового framework, сохраняется идея с "internal" файлами (тестирующей системе не надо знать их формат), можно меньше гонять их по сети (все можно сделать на тестирующем компьютере за один запуск), не требуется блокировка этих "файлов" даже при наличии valuer.
Минусы: потенциально возможно дублирование кода между scorer и valuer (хотя я не не могу представить себе такую ситуацию), требуется запускать еще больше процессов, увеличение количества сущностей
Что-то мне кажется, что тут всё излишне усложнено. Можно ведь сделать совсем просто: тестирующая система предоставляет scorer'у RESTful API, с помощью которого можно получить доступ к произвольным данным по решениям (input/output по каждому тесту, output чекера, время сабмита, etc.). А scorer периодически отдаёт обратно полный scoreboard (всё равно все современные тестирующие системы не генерят scoreboard на каждый запрос, т.к. даже в случае ACM это смерть серверу при существенно ненулевом количестве участников). Понятно, что при этом скорер должен поддерживать какой-то state, поэтому он должен быть непрерывно запущен (а в случае, если его захотят прибить — должен уметь сохранить свой state, ну или восстановить его после перезапуска).
Схема достаточно общая, чтобы покрыть все мыслимые use-cases, но есть проблема с тем, что автору scorer'а придётся самому реализовывать всякие фичи вроде кеширования. Но с этим легко побороться, предоставив framework для популярных языков (сейчас framework даже для чекеров используется, называется testlib). Ну а тем, кто захочет писать на извращённых языках, придётся написать такой фреймворк самостоятельно (но только 1 раз).
Из плюсов: нет обмена информацией через stdin/stdout (ура!), scorer может работать на платформе, отличающейся от платформы тестирующей системы (ура!!), подходит для произвольных систем оценки решений.
Из минусов: необходимость немаленького фреймворка для языка, на котором пишется scorer.
То есть предлагается вообще весь процесс генерации монитора вынести в отдельную программу? В чём-то это разумно, но интерфейс с тестирующей системой может оказаться слишком громоздким. В случае ACM придётся передать всякие нетривиальные параметры типа "как округлять штрафное время" и "считается ли CE за попытку". В случае IOI нужно передавать информацию по токенам, а также по какому из сабмитов считаются итоговые баллы. И это только навскидку.
В общем, по-моему, такая схема если и подходит, то скорее для разработки новой системы — в существующих многовато придётся переделывать.
Мне в целом нравится идея standalone scorer-а, но лучше, если он будет работать на уровне каждой посылки, а не на уровне всего контеста. Опять же, чаще нужна не вся таблица результатов, а подробные результаты конкретной посылки.
По поводу "как округлять штрафное время" и "считается ли CE за попытку" — можно просто передавать конфиг, а scorer сам его распарсит и интерпретирует, как захочет.
По поводу "в существующих многовато придётся переделывать" — я знаю по крайней мере одну существующую, в которой мало что придётся переделывать, но она не опенсорсная. Вот ejudge конечно придётся переделывать существенно, но там всё настолько сильно костылями обросло, что давно нужен основательный рефакторинг.
Отвечу сразу нескольким комментаторам. В предложении, что valuer'у доступен output, есть один большой недостаток. Этот output надо где-то хранить. Как минимум на время между testing'ом и подсчетом очков. А, если не хочется перетестировать (а не хочется перетестировать), то хранить все время.
При этом output'ы — это может быть тупо много. А даже если не должно быть, то надо как-то бороться с участниками, которые
while (true) printf("*")или еще какой-нибудь треш.PS Кстати, от такого кода на CF раньше случался Check Failed. Точнее не на CF, а у testlib видимо.
Например, в ejudge и так хранятся output-ы. Да, место на диске кончается.
Output-ы можно архивировать.
В моём предложении "посылать ли output-ы scorer-у" — то есть не обойдётся ли он комментариями чекера — можно сделать параметром задачи.
Да, ещё длинные output-ы можно не посылать, если комментарий чекера к ним — WA или PE.
А output limit кто отменял? Он по идее эту проблему решает.
By the way, а разве существующие системы не хранят output? E-judge, насколько я понимаю, хранит, codeforces наверное тоже (судя по тому, что часть output'а можно в логе посмотреть). В любом случае, с современными ценами на харды, это не должно быть проблемой.
output-limit никто не отменял. Но 100 тестов x 20 посылок. И привет закончившемуся диску со всеми вытекающими.
По поводу цен на харды. Это хорошо, когда стоит себе сервер и стоит. А скажем на сборах, где сревер — один комп, и judge еще один, который привозят только на время сборов. И у него есть свои 120 GB памяти и больше ничего — это уже грустно.
Хотя видимо кроме TestSys все много распространенное хранит.
Да ладно, в этой схеме самая большая проблема — не сохранить output, а передать его с инвокера по сети.
А потом testsys зависает с попытками записать в лог, то, что у него не получилось записать в лог, потому что закончилось место на диске.
Обычно скорость передачи по сети больше скорости чтения с харда (кроме случая SSD+тормознутая сеть, но это уж совсем изврат). Тем более передавать output можно только в случае, если scorer'у не хватит output'а чекера и он попросит output программы.
Не поверишь, но последние сборы тестились на ноуте с SSD, подключенном к judge через wifi.
Ну вот это проблема сборов. Очевидное же решение — иметь один экземпляр тестирующей системы (в быстром датацентре с кучей invoker'ов и без проблем со storage space) и проводить на нём все возможные контесты, включая сборы. Подобные вещи уже есть (contest.yandex.ru, codeforces.ru, хотя в случае последнего быстрого датацентра нет), но все почему-то продолжают делать custom instances тестирующих систем для проведения пары-тройки контестов.
Мы иногда даже локальный svn пару раз использовали на сборах. Приходилось. Потому что вот исчезает интернет во всём заведении, и замечательная централизованная система живёт себе спокойно дальше. Но без участников.
В современных условиях быстрый интернет бывает недоступен регулярно на любых мероприятиях, длящихся более нескольких дней. И на школьных сборах, и на студенческих. Так что расчёт на быстрые красивые сервера далеко в интернете — минус рейтинговый контест. Лучше уж потратить время и сделать локально, но чтобы контесты не пропали.
Я и не думал, что до сих пор есть такие проблемы. Сейчас даже с телефона можно без проблем получить канал шириной несколько мегабит, что более чем достаточно для любого контеста. (в том числе и в Петрозаводске; неужели там тоже интернет исчезает?)
В общем, локальные сервера — это конечно workaround, но если пропадает интернет, то проблема несколько более фундаментальная, и повод заняться инфраструктурой места проведения (хотя бы по части инета).
<offtop> Тебе предложить объяснить руководителям школьных сборов почему их надо проводить в другом месте? </offtop>
< offtop> Можно не предлагать; с чего бы они вдруг стали меня слушать? :)
Но в любом случае, есть же всякие work-around'ы вроде VSAT (да, дорогие, но учитывая, что на школьников минобразования всё же выделяет немало денег (в отличие от студентов), при желании проблема решаемая). < /offtop>
В тот же оффтоп можно ещё вспомнить, куда в России обычно деваются выделенные государством на что-то деньги.
И вообще. Можно делать централизованную систему и подстраивать под неё текущие условия. А можно учитывать текущие условия и подстраивать под них более переносимую систему. Не вижу, чем второй подход сильно хуже первого.
Не забудь еще, что сравнивать лексикографически токены не тоже самое, что сравнивать лексикографически числа. Так что еще + настройка
Что такое "сравнивать лексикографически числа"? Я представлял так: берётся токен, определяется, является ли он числом (хоть
sscanf(s, "%lf", &x) == 1) и в зависимости от этого определяется, как сравнивать.Если система счисления больше десятичной, или (и) используется ДА этот способ не пройдёт.
Давайте считать жюри адекватными. Тот кто выводит scoring в HEX сам дурак.
Речь не об этом. Речь о 2-х принципиально важных моментах. 1. О классе задач на системы счисления. 2. И что более важно, мы в задачах с динамической оценкой сравниваем ведь не с ответом, а с какой-то разницей от эталона, посчитанного по тоже какой-то ф-ции. И в случае с задачами на системы счисления тут не всё так просто посчитать то самое епсилон. Придётся скорее всего наверх дополнительно ещё один специфический чекер на точность навешивать. А по предыдущей логике действительно, выгоднее тогда просто вообще исключить класс задач на системы счисления в применении к динамической системе оценки, что, согласитесь, вряд ли целесообразно, как любое исключение.
Вы о чем? Так предлагается сравнивать output чекера.
А разве задачи с динамической оценкой гарантируют, что оутпут чекера точнее в чекере, нежели, скажем, у автора, или, что ожидается — в решении пользователя.
Ведь, собственно, подобные задачи и нацелены на поиск лучших решений, нежели авторское. Но чекер не доказывает корректность или некорректность подобного решения.
По моему пример вполне описан. Например есть задача коммивояжёра. Чекер не знает лучший ли ответ — но может посчитать длину. Зачем эту длину выводить в hex? Предлагается сравнивать такие вот вещи.
Мм.. произвольная строчка, которая сравнивается лексикографически у нескольких пользователей вдруг может оказаться числами. И да, sscanf("25ololo") вроде бы вернет 1. (мб полечится спецификатором "%lf%s).
Впрочем, это все не очень важно.
PS: сравнивать лексикографически числа — сравнивать их по очереди до первого отличия
Казалось бы, почему не воспользоваться тем же валуером, только валуер будет отвечать за целую задачу.
Т.е. для каждой задачи (например, при запуске контеста) запускается интеркативный валуер (интерактивный в том смысле, что в процессе тестирования различных посылок он обменивается сообщениями с инвокером; что-то похожее сейчас есть в ejudge, но используется только для подсчета результата одной посылки). При этом, этот валуер у себя в памяти держит результат каждого участника по задаче в любом удобном виде, и может отвечать на сообщение-запрос вида "дайте мне баллы этого участника на текущий момент" (вычислять их на основе всех данных, которые у него имеются — баллы этого участника, других участников, какие-нибудь эталонные баллы и т.д.).
Можно также добавить ему возможность исправлять сразу таблицу результатов (или он может просто таким же образом обмениваться сообщениями с программой, которая генерирует таблички), или записывать что-то в нужные файлы.
Правда, получается, что нужно на каждую задачу по отдельному процессу для подсчета результатов, который в памяти у себя должен хранить "что-то". Но, казалось бы, это "что-то" так или иначе придется где-то хранить.
Выше уже выдавали похожую идею. Там же идёт её обсуждение.
А не бывает такого, что полученные баллы зависят не только от лучшего решения? Что-то в духе рейтинга ИТМО
(балл/макс.балл) * (1 — место/кол.во участников).
В таком случае было бы логично отдавать данные всех участников.