NALP's blog

By NALP, 11 years ago, In Russian

Тема интерактивных задач становится все популярнее, такие задачи каждый год встречаются на 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?

  • Vote: I like it
  • +28
  • Vote: I do not like it