В последнее время формат типичных задач на соревнованиях по программированию расширяется новым видом задач, которые принято называть интерактивными. Решения таких задач в некотором роде общаются (взаимодействуют) с тестирующей оболочкой. Обычно, интерактивные задачи используются для задач двух видов:
- Задачи на online-алгоритмы, т.е. такие алгоритмы, которые не читают все входные данные сразу, а могут читать их только по мере своей работы. Простой пример: задано множество из n чисел. Надо обработать n запростов. Каждый запрос содержит элемент множества, до обработки запроса надо вывести минимум чисел в множестве, а потом удалить этот элемент. Естественно, после последнего запроса множества станет пустым. Если решать эту задачу как офлайн-задачу, то можно решать ее <<с конца>>, обрабатывая запросы от последнего к первому (т.е. фактически добавляя в множество элементы). В таком случае решение совсем тривиально. Онлайн-формулировка не позволяет решению прочитать очередной запрос до обработки предыдущего, что вынуждает писать решение, обрабатывающее запросы в прямом порядке. В таком случае необходима структура данных типа
std::set
в С++ для поддержания минимума в динамическом множестве. - Задачи на игры. В таком случае участнику надо написать программу, которая делает какие-то ходы, а ответы на эти ходы зависят от того, как именно сходила программа. Здесь в качестве игр могут выступать не только типичные игры, но и «угадайки». Например: было загадано число от 1 до n. Программа участника пытается его угадать, а интерактивный модуль отвечает больше или меньше загаданное число очередной попытки участника. Требуется отгадать число, сделав не более попыток. В качестве решения здесь участник может использовать бинарный поиск.
Интерактивные задачи немного сложнее для поддержания в тестирующих системах, так как требуют одновременный запуск решения в связке с неким интерактивным модулем в таком режиме, что вывод модуля перенаправляется на ввод решения и наоборот. Такой функциональности можно добиться, используя пайпы (pipes) операционной системы.
В настоящий момент есть несколько источников интерактивных задач, в них похожим образом устроен процесс тестирования. Опишем этот процесс, обобщив опыт существующих разработок. Я уверен, что одинаковый workflow тестирования значительно упростит процесс переиспользования подобных задач. Призываею использовать именно его в тестирующих системах. Конечно, предварительно его следует обсудить в комментариях.
Пакет задачи состоит из:
- Одного или нескольких тестов, возможно с ответами (на картинке это файл file.in и file.a). В качестве ответов обычно используются выводы интерактора при тестировании модельных авторских решений.
- Интерактивного модуля (сокращенно, интерактора) — специальной программы, которая <<общается>> с решением.
- Тестирующей программы (чекера).
- Крайне желательно наличие авторского решения.
- Крайне желательно наличие специальной программы — валидатора. Валидатор получает на вход текст теста (file.in) и возвращается с кодом возврата 0 тогда и только тогда, когда тест корректен. Здесь есть хитрость, так как по-идее еще надо валидировать непосредственно данные, отосланные решению (стрелочка от интерактора к решению stdout-stdin). В настоящий момент такую валидацию лучше встраивать в интерактор.
Как происходит запуск решения и его оценка в интерактивной задаче.
- Сначала запускается в <<связке>> одновременно решение и интерактор. На решение как обычно наложены традиционные ограничения на время и память. На интерактор похожие ограничения тоже должны быть наложены, но довольно лояльные (например, 15 секунд/256MB). Интерактор запускается с теми же параметрами командной строки, что и обычный чекер — именем файла для чтения описания теста (в схеме file.in), именем файла для вывода информации о результатах взаимодействия (в схеме file.out), именем файла с ответом (в схеме file.a). Возможны дополнительные классические параметры testlib, если интерактор написан на нем.
- Ждем события, что один из процессов завершился (сам собой или был прерван).
- Первый случай, первым завершилось решение:
- Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт
Time Limit Exceeded
,Memory Limit Exceeded
илиIdleness Limit Exceeded
(последний, если программа продолжительное время вообще не расходовала процессорное время). - Если завершилось с кодом возврата неравным 0, то возвращаем
Runtime Error
. - Если завершилось благополучно и с кодом 0, то продолжаем ждать пока завершится интерактор.
- Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт
- Второй случай, первым завершился интерактор:
- Если завершился по причине превышения каких-то ограничений, то сразу возвращаем вердикт
Judgement Failed
. - Если завершился с кодом возврата неравным 0, то обрабатываем его как обычный чекер:
- код 1: возвращаем вердикт
Wrong Answer
, - код 2: возвращаем вердикт
Wrong Answer
(илиPresentation Error
, если такой вердикт поддерживается), - код 3 или любой другой: возвращаем
Judgement Failed
.
- код 1: возвращаем вердикт
- В случае любого из ненулевых кодов возврата, вывод интерактора на стандартный поток ошибок (stderr) следует считать комментарием тестирующей системы о тестировании на этом тесте.
- Если интерактор вернулся с кодом 0, то ждем завершения решения. Применяем к нему пункты о превышении ограничений или ненулевом коде возврата из предыдущего пункта. Таким образом, считаем, что оно благополучно завершилось с кодом 0.
- Если завершился по причине превышения каких-то ограничений, то сразу возвращаем вердикт
- Ждем завершения второго процесса, считаем, что он благополучно завершился с кодом 0, иначе вердикт очевиден.
- Запускаем чекер, передавая ему в качестве аргументов file.in (описание теста), file.out (вывод интерактора) и, если есть, file.a (файл ответа). Таким образом, командная строка запуска имеет вид:
check file.in file.out
илиcheck file.in file.out file.a
. Чекер запускаем с лояльными ограничениями (например, 15 секунд/256 MB). Ждем завершения процесса. Если ограничения были превышены, то возвращаемJudgement Failed
. В противном случае смотрим на код возврата:- код 0: возвращаем вердикт
OK
, - код 1: возвращаем вердикт
Wrong Answer
, - код 2: возвращаем вердикт
Wrong Answer
(илиPresentation Error
, если такой вердикт поддерживается), - код 3 или любой другой: возвращаем
Judgement Failed
.
- код 0: возвращаем вердикт
- В случае любого из ненулевых кодов возврата, объединенный вывод чекера на стандартный поток вывода (stdout) и ошибок (stderr) следует считать комментарием тестирующей системы о тестировании на этом тесте.
Некоторые тестирующие системы используют альтернативные способы получения информации о вердикте после запуска чекера. Например:
- PCMS2 считает, что чекер всегда должнен возвращаться с кодом 0, а его вердикт считывается из специального XML-файлика.
- EJUDGE имеет свою собственную систему кодов возврата, несовместимую с общеприятой.
По этой причине настоятельно рекомендуется использовать testlib для разработки как чекера, так и интерактора, чтобы инкапсулировать способ передачи вердикта в проверенную совместимую библиотеку.
Вот пример простого интерактора под testlib.h, который делает задачу A+B интерактивной:
#include "testlib.h"
#include <iostream>
using namespace std;
int main(int argc, char* argv[])
{
setName("Interactor A+B");
registerInteraction(argc, argv);
// reads number of queries from test file
int n = inf.readInt();
for (int i = 0; i < n; i++)
{
// reads query from test file
int a = inf.readInt();
int b = inf.readInt();
// writes query to the solution, endl makes flush
cout << a << " " << b << endl;
// writes output file to be verified by checker later
tout << ouf.readInt() << endl;
}
// just message
quitf(_ok, "%d queries processed", n);
}
В данном случае не имеет смысла встраивать логику проверки в интерактор, хотя это возможно сделать. В некотором смысле она в нем имеется, например он может остановиться с вердиктом PE, не найдя ответа на очередной запрос (программа участника завершилась досрочно).
В задачах на игры иногда имеет смысл переносить большую часть логики чекера в интерактор, хотя лучше этого избегать.