Тема интерактивных задач становится все популярнее, такие задачи каждый год встречаются на NEERC, иногда на этапах OpenCup и в других местах. Но все-таки на данный момент это непаханое поле, так как совсем немногие полноценно поддерживают инфраструктуру для тестирования подобных задач.
На Codeforces эту тему недавно поднимал MikeMirzayanov в своем посте. Вот цитата оттуда (**рекомендую прочитать этот пост для того, чтобы быть в курсе темы**):
Первый случай, первым завершилось решение:
- Если завершилось по причине превышения каких-то ограничений, то сразу возвращаем вердикт 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.
А теперь рассмотрим два очень даже вероятных случая:
Решение выводит интерактору какую-нибудь неадекватную информацию и ждет ответа. Интерактор понимает, что дальше невозможно продолжать протокол и кончает жизнь суицидом — завершается с вердиктом WA (ну или PE, если этот вердикт поддерживается). Таким образом он завершает потоки ввода-вывода со своей стороны, в частности stdin решения. Напоминаю, что решение в данном случае ждет ответа интерактора, но так как поток с его стороны завершен, у решения не получается считать ответ и оно падает с RE;
Второй вариант противоположен. Решение пытается что-то вывести интерактору, но в середине этого занятия падает с RE, завершая поток stdin интерактора со своей стороны. Однако что-то на этот момент все еще лежит в буфере, и интерактор это "что-то" читает, считает, что решение просто вывело ерунду и логично завершает работу с вердиктом WA или PE.
Эти две ситуации с точки зрения тестирующей системы абсолютно равны, так как решение падает с RE, а интерактор выносит вердикт WA. Но между ними есть большая разница в причине такого поведения, а именно, это Runtime Error или Wrong Answer решения. Эта ситуация лечится определением того, какой из процессов раньше завершился. Если первым упало решение, то это RE, а если первым упал интерактор, то это WA, и казалось бы проблем нет...
НО! Оказывается, что нельзя гарантированно определить порядок завершения процессов, то есть на то, что скажет ОС, полагаться нельзя!
Вот мы и пришли к концу повествования, а именно к вопросу: а как же определить истинную причину и сказать настоящий результат участнику? Разумеется, совершенно не хочется категорично менять инфраструктуру, описанную в посте MikeMirzayanov'а, хочется обойтись минимальными дополнениями в существующую модель.
Any ideas?