В последнее время формат типичных задач на соревнованиях по программированию расширяется новым видом задач, которые принято называть интерактивными. Решения таких задач в некотором роде общаются (взаимодействуют) с тестирующей оболочкой. Обычно, интерактивные задачи используются для задач двух видов:

• Задачи на online-алгоритмы, т.е. такие алгоритмы, которые не читают все входные данные сразу, а могут читать их только по мере своей работы. Простой пример: задано множество из n чисел. Надо обработать n запростов. Каждый запрос содержит элемент множества, до обработки запроса надо вывести минимум чисел в множестве, а потом удалить этот элемент. Естественно, после последнего запроса множества станет пустым. Если решать эту задачу как офлайн-задачу, то можно решать ее <<с конца>>, обрабатывая запросы от последнего к первому (т.е. фактически добавляя в множество элементы). В таком случае решение совсем тривиально. Онлайн-формулировка не позволяет решению прочитать очередной запрос до обработки предыдущего, что вынуждает писать решение, обрабатывающее запросы в прямом порядке. В таком случае необходима структура данных типа std::set в С++ для поддержания минимума в динамическом множестве.
• Задачи на игры. В таком случае участнику надо написать программу, которая делает какие-то ходы, а ответы на эти ходы зависят от того, как именно сходила программа. Здесь в качестве игр могут выступать не только типичные игры, но и «угадайки». Например: было загадано число от 1 до n. Программа участника пытается его угадать, а интерактивный модуль отвечает больше или меньше загаданное число очередной попытки участника. Требуется отгадать число, сделав не более попыток. В качестве решения здесь участник может использовать бинарный поиск.

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

В настоящий момент есть несколько источников интерактивных задач, в них похожим образом устроен процесс тестирования. Опишем этот процесс, обобщив опыт существующих разработок. Я уверен, что одинаковый workflow тестирования значительно упростит процесс переиспользования подобных задач. Призываею использовать именно его в тестирующих системах. Конечно, предварительно его следует обсудить в комментариях.

Пакет задачи состоит из:

1. Одного или нескольких тестов, возможно с ответами (на картинке это файл file.in и file.a). В качестве ответов обычно используются выводы интерактора при тестировании модельных авторских решений.
2. Интерактивного модуля (сокращенно, интерактора) — специальной программы, которая <<общается>> с решением.
3. Тестирующей программы (чекера).
4. Крайне желательно наличие авторского решения.
5. Крайне желательно наличие специальной программы — валидатора. Валидатор получает на вход текст теста (file.in) и возвращается с кодом возврата 0 тогда и только тогда, когда тест корректен. Здесь есть хитрость, так как по-идее еще надо валидировать непосредственно данные, отосланные решению (стрелочка от интерактора к решению stdout-stdin). В настоящий момент такую валидацию лучше встраивать в интерактор.

Как происходит запуск решения и его оценка в интерактивной задаче.

1. Сначала запускается в <<связке>> одновременно решение и интерактор. На решение как обычно наложены традиционные ограничения на время и память. На интерактор похожие ограничения тоже должны быть наложены, но довольно лояльные (например, 15 секунд/256MB). Интерактор запускается с теми же параметрами командной строки, что и обычный чекер — именем файла для чтения описания теста (в схеме file.in), именем файла для вывода информации о результатах взаимодействия (в схеме file.out), именем файла с ответом (в схеме file.a). Возможны дополнительные классические параметры testlib, если интерактор написан на нем.
2. Ждем события, что один из процессов завершился (сам собой или был прерван).
3. Первый случай, первым завершилось решение:
   • Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт Time Limit Exceeded, Memory Limit Exceeded или Idleness Limit Exceeded (последний, если программа продолжительное время вообще не расходовала процессорное время).
   • Если завершилось с кодом возврата неравным 0, то возвращаем Runtime Error.
   • Если завершилось благополучно и с кодом 0, то продолжаем ждать пока завершится интерактор.
4. Второй случай, первым завершился интерактор:
   • Если завершился по причине превышения каких-то ограничений, то сразу возвращаем вердикт Judgement Failed.
   • Если завершился с кодом возврата неравным 0, то обрабатываем его как обычный чекер:
     • код 1: возвращаем вердикт Wrong Answer,
     • код 2: возвращаем вердикт Wrong Answer (или Presentation Error, если такой вердикт поддерживается),
     • код 3 или любой другой: возвращаем Judgement Failed.
   • В случае любого из ненулевых кодов возврата, вывод интерактора на стандартный поток ошибок (stderr) следует считать комментарием тестирующей системы о тестировании на этом тесте.
   • Если интерактор вернулся с кодом 0, то ждем завершения решения. Применяем к нему пункты о превышении ограничений или ненулевом коде возврата из предыдущего пункта. Таким образом, считаем, что оно благополучно завершилось с кодом 0.
5. Ждем завершения второго процесса, считаем, что он благополучно завершился с кодом 0, иначе вердикт очевиден.
6. Запускаем чекер, передавая ему в качестве аргументов 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.
7. В случае любого из ненулевых кодов возврата, объединенный вывод чекера на стандартный поток вывода (stdout) и ошибок (stderr) следует считать комментарием тестирующей системы о тестировании на этом тесте.

Некоторые тестирующие системы используют альтернативные способы получения информации о вердикте после запуска чекера. Например:

1. PCMS2 считает, что чекер всегда должнен возвращаться с кодом 0, а его вердикт считывается из специального XML-файлика.
2. 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, не найдя ответа на очередной запрос (программа участника завершилась досрочно).

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