На Codeforces уже поднимались темы об интерактивных задачах (первая и вторая).

В этой теме мне хочется поднять вопрос о вердиктах в интерактивных задачах (с которыми довольно часто возникают проблемы) и предложить дополнение к алгоритму тестирования, которое позволит выставлять их практически не завися от прихотей ОС (проблема, поднятая NALP в этой теме). Также будет показан код под Windows, реализующий это дополнение.

В самом начале хочется спросить: а как, вообще говоря, выставляются вердикты в обычных задачах? Базовой аксиомой является "сначала решение корректно завершается, а потом проверяется ответ". Таким образом, даже если решение вывело (не)корректный ответ в выходной файл, а потом завершилось с ненулевым кодом возврата (либо зависло), система не станет это проверять, а просто скажет RTE/TL.

В интерактивных задачах эта аксиома не работает. Например, если в процессе какой-то игры участник выводит несуществующий ход, продолжать взаимодействие не имеет смысла и надо выдать WA. Я предлагаю взять за аксиому следующее: "в первый момент времени, когда стало возможным выдать вердикт, отличный от OK, выполнение должно прерываться с очевидным вердиктом". Рассмотрим несколько примеров:

1. Участник вывел неверный ход и ждёт ответа чекера. Это очевидный WA.

2. Участник вывел неверный ход, понял, что сам дурак, и завершился с RTE.

3. Участник в процессе вывода вышел за границу массива, вывел бред и завершился с RTE.

Я утверждаю, что ситуации 2 и 3 в принципе неотличимы. Проверяющая система не может однозначно определить, вывел ли участник бред из-за RTE или же он случился строго после. Поэтому выставляется вердикт WA, который случился в момент вывода в stdout, что произошло раньше, чем RTE, который случился в момент завершения программы. В частности, при изменении задачи на интерактивную, могут поменяться получаемые вердикты: любой из них (TL/RTE/ML) может поменяться на WA. Это довольно неинтуитивно после стандартных задач. В качестве альтернативы после завершения интерактора можно некоторое время (до IL/TL) ожидать падения решения и, если оно произойдёт, поставить RTE. Это будет чуть ближе к стандартным задачам в том смысле, что в случае падения решение не будет проверяться его последний ответ. Это место еще стоит обсудить.

Также хочется отметить сложность в отличии вердиктов Idleness Limit Exceeded и WA/PE. Первый легко получить, если забыть fflush. Однако представим себе ситуацию, в которой участник по каким-то причинам вывел четыре числа вместо пяти и начал ждать ответа интерактора. В этом случае налицо нарушение протокола взаимодействия и хочется выставить WA/PE. Однако с точки зрения тестирующей системы ситуации отличаются только наличием вывода "в последнее время", что непонятно, как формализовать. Есть предложения? Мне лично хочется оставить как есть и ничего не придумывать.

Теперь перейдём к решению старых проблем. В первой теме MikeMirzayanov предложил алгоритм тестирования задач. Вкратце:

1. Параллельно с решением запускается интерактор, который имеет доступ к тесту (и ответу, если такой есть) и взаимодействует с решением. В случае нарушения протокола/заведомо неверного ответа он завершает работу. Если всё в порядке, то отдельно запускается чекер, который проверяет ответ, выведенный интерактором в файл вывода (в некоторых задачах чекер пустой и несодержателен — всё проверяет интерактор).

2. Если первым завершается решение, то либо сразу ставится вердикт из-за некорректного завершения (RTE/TL/ML), либо ожидается завершение интерактора, после чего выставляется вердикт, соответствующий результату работы интерактора/чекера.

3. Если первым завершается интерактор, то либо сразу ставится вердикт WA/PE, либо ожидается корректное завершение решения и запускается чекер.

В отдельном посте NALP указал на довольно существенный недостаток системы в реальных условиях: стандартные средства ОС не дают возможности точно определить, какой процесс завершился первым (да и не очень понятно, что это такое в многозадачной среде). Поэтому с точки зрения проверяющей системы ситуации "решение вывело WA, интерактор закрылся, решение упало с RTE, так как не смогло считать" и "решение упало, интерактор сказал WA, так как поток закрылся" неотличимы: решение завершилось некорректно, интерактор завершился с кодом возврата WA.

Теперь я хочу предложить точное и стабильное решение последней проблемы. Для этого сделаю два предположения:

1. При попытке чтения оба процесса (не поток, а весь процесс) полностью блокируются. Обычно использование многопоточности на олимпиадах либо запрещено, либо бессмысленно из-за подсчёта процессорного времени. Ситуации, в которой потребуется неблокирующий ввод в задаче, я представить также не могу, так что я этот пункт считаю покрывающим вообще все задачи.

2. Даже после выставление вердикта ОК, интерактор не завершается, пока не получит EOF, чтобы проверить, что участник не вывел что-то лишнее.

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

Итого, алгоритм получается такой:

1. Запустить параллельно интерактор и решение с замкнутыми друг на друга вводом-выводом. При этом необходимо сохранить открытые хэндлы в тестирующей системе.

2. Пусть первым завершился интерактор. Так как он должен был ждать EOF в случае OK, то он должен был завешиться с вердиктом WA, который мы и выставляем (либо, как альтернативное решение, надо подождать и проверить отсутсвие RTE).

3. Значит, первым завершилось решение. Если решение завершилось корректно, мы закрываем хэндлы, интерактор получает EOF и завершается с некоторым вердиктом, который мы возвращаем как результат проверки. Если же оно завершилось некорректно, то возможно два варианта: либо это произошло вскоре после получения WA (и интерактор должен скоро завершиться), либо нет. Чтобы отличить WA/RTE в этой ситуации, надо проверить, что интерактор не ждёт ввода (т.е., тратит процессорное время). Если ждёт — ставим RTE, если делает что-то осмысленное — ждём его завершения и ставим вердикт.

Эта идея осуществлена в написанной мной для демонстрации утилите, которую можно скачать здесь. Она следует концепции "выставляем то, что случилось раньше" и не ждёт RTE после завершения интерактора с WA, зато ожидает завершения интерактора в случае падения решения.

Прошу высказать свои мысли по поводу дополненной схемы, возможности её реализации в других ОС, а также любую критику по поводу высказанных мыслей.