На Codeforces уже поднимались темы об интерактивных задачах (первая и вторая).
В этой теме мне хочется поднять вопрос о вердиктах в интерактивных задачах (с которыми довольно часто возникают проблемы) и предложить дополнение к алгоритму тестирования, которое позволит выставлять их практически не завися от прихотей ОС (проблема, поднятая NALP в этой теме). Также будет показан код под Windows, реализующий это дополнение.
В самом начале хочется спросить: а как, вообще говоря, выставляются вердикты в обычных задачах? Базовой аксиомой является "сначала решение корректно завершается, а потом проверяется ответ". Таким образом, даже если решение вывело (не)корректный ответ в выходной файл, а потом завершилось с ненулевым кодом возврата (либо зависло), система не станет это проверять, а просто скажет RTE/TL.
В интерактивных задачах эта аксиома не работает. Например, если в процессе какой-то игры участник выводит несуществующий ход, продолжать взаимодействие не имеет смысла и надо выдать WA. Я предлагаю взять за аксиому следующее: "в первый момент времени, когда стало возможным выдать вердикт, отличный от OK, выполнение должно прерываться с очевидным вердиктом". Рассмотрим несколько примеров:
Участник вывел неверный ход и ждёт ответа чекера. Это очевидный WA.
Участник вывел неверный ход, понял, что сам дурак, и завершился с RTE.
Участник в процессе вывода вышел за границу массива, вывел бред и завершился с RTE.
Я утверждаю, что ситуации 2 и 3 в принципе неотличимы. Проверяющая система не может однозначно определить, вывел ли участник бред из-за RTE или же он случился строго после. Поэтому выставляется вердикт WA, который случился в момент вывода в stdout, что произошло раньше, чем RTE, который случился в момент завершения программы. В частности, при изменении задачи на интерактивную, могут поменяться получаемые вердикты: любой из них (TL/RTE/ML) может поменяться на WA. Это довольно неинтуитивно после стандартных задач. В качестве альтернативы после завершения интерактора можно некоторое время (до IL/TL) ожидать падения решения и, если оно произойдёт, поставить RTE. Это будет чуть ближе к стандартным задачам в том смысле, что в случае падения решение не будет проверяться его последний ответ. Это место еще стоит обсудить.
Также хочется отметить сложность в отличии вердиктов Idleness Limit Exceeded и WA/PE. Первый легко получить, если забыть fflush. Однако представим себе ситуацию, в которой участник по каким-то причинам вывел четыре числа вместо пяти и начал ждать ответа интерактора. В этом случае налицо нарушение протокола взаимодействия и хочется выставить WA/PE. Однако с точки зрения тестирующей системы ситуации отличаются только наличием вывода "в последнее время", что непонятно, как формализовать. Есть предложения? Мне лично хочется оставить как есть и ничего не придумывать.
Теперь перейдём к решению старых проблем. В первой теме MikeMirzayanov предложил алгоритм тестирования задач. Вкратце:
Параллельно с решением запускается интерактор, который имеет доступ к тесту (и ответу, если такой есть) и взаимодействует с решением. В случае нарушения протокола/заведомо неверного ответа он завершает работу. Если всё в порядке, то отдельно запускается чекер, который проверяет ответ, выведенный интерактором в файл вывода (в некоторых задачах чекер пустой и несодержателен — всё проверяет интерактор).
Если первым завершается решение, то либо сразу ставится вердикт из-за некорректного завершения (RTE/TL/ML), либо ожидается завершение интерактора, после чего выставляется вердикт, соответствующий результату работы интерактора/чекера.
Если первым завершается интерактор, то либо сразу ставится вердикт WA/PE, либо ожидается корректное завершение решения и запускается чекер.
В отдельном посте NALP указал на довольно существенный недостаток системы в реальных условиях: стандартные средства ОС не дают возможности точно определить, какой процесс завершился первым (да и не очень понятно, что это такое в многозадачной среде). Поэтому с точки зрения проверяющей системы ситуации "решение вывело WA, интерактор закрылся, решение упало с RTE, так как не смогло считать" и "решение упало, интерактор сказал WA, так как поток закрылся" неотличимы: решение завершилось некорректно, интерактор завершился с кодом возврата WA.
Теперь я хочу предложить точное и стабильное решение последней проблемы. Для этого сделаю два предположения:
При попытке чтения оба процесса (не поток, а весь процесс) полностью блокируются. Обычно использование многопоточности на олимпиадах либо запрещено, либо бессмысленно из-за подсчёта процессорного времени. Ситуации, в которой потребуется неблокирующий ввод в задаче, я представить также не могу, так что я этот пункт считаю покрывающим вообще все задачи.
Даже после выставление вердикта ОК, интерактор не завершается, пока не получит EOF, чтобы проверить, что участник не вывел что-то лишнее.
Решение проблемы выставления вердикта состоит в следующем: при создании пайпов для взаимодействия решений, тестирующая система не закрывает свой хэндл на вывод в пайп. Таким образом, у каждого пайпа образуется не два, а три конца — по одному у решения, у интерактора и у системы. При завершении любого из двух процессов, пайп не закрывается и решение/интерактор не получают EOF, пока этого не захочет тестирующая система.
Итого, алгоритм получается такой:
Запустить параллельно интерактор и решение с замкнутыми друг на друга вводом-выводом. При этом необходимо сохранить открытые хэндлы в тестирующей системе.
Пусть первым завершился интерактор. Так как он должен был ждать EOF в случае OK, то он должен был завешиться с вердиктом WA, который мы и выставляем (либо, как альтернативное решение, надо подождать и проверить отсутсвие RTE).
Значит, первым завершилось решение. Если решение завершилось корректно, мы закрываем хэндлы, интерактор получает EOF и завершается с некоторым вердиктом, который мы возвращаем как результат проверки. Если же оно завершилось некорректно, то возможно два варианта: либо это произошло вскоре после получения WA (и интерактор должен скоро завершиться), либо нет. Чтобы отличить WA/RTE в этой ситуации, надо проверить, что интерактор не ждёт ввода (т.е., тратит процессорное время). Если ждёт — ставим RTE, если делает что-то осмысленное — ждём его завершения и ставим вердикт.
Эта идея осуществлена в написанной мной для демонстрации утилите, которую можно скачать здесь. Она следует концепции "выставляем то, что случилось раньше" и не ждёт RTE после завершения интерактора с WA, зато ожидает завершения интерактора в случае падения решения.
Прошу высказать свои мысли по поводу дополненной схемы, возможности её реализации в других ОС, а также любую критику по поводу высказанных мыслей.
Хм, ну первое, что бросается в глаза, — "при попытке чтения оба процесса блокируются". Не очень понимаю, это как? А если процесс aio_read позовёт? Не говоря уж о тредах, которые, как ни странно, иногда применяются на контестах. Очередные патчи к ядру писать, которые его делают не-POSIX-совместимым? В общем, требовать какого-то фиксированного поведения от программы участника — не самый лучший способ решения проблемы.
(.7z-архив с утилитой я пока не смотрел, посмотрю, когда доберусь до девайса, умеющего такое открывать; или может лучше на гитхаб код выложить?)
Имеется ввиду, что если процесс хочет что-то прочитать, он блокируется до получения нужной информации/EOF.
А можете привести пример контеста (в котором требуется именно отсылать код), в котором применение потоков имеет смысл? Ну, кроме, пожалуй, первого тура Всесибирской олимпиады этого года, но там используются grader'ы.
Точно так же непонятен смысл применения асинхронного I/O. Вот тут уже я примеров придумать не могу. Казалось бы, если мы не смогли считать требуемую информацию, мы не можем продолжать выполнение, потому что мы взаимодействуем с интерактором.
Пример use-case тредов — задачи на перебор с тест-кейсами. Если хочется сделать отсечение по времени — то последовательное решение тест-кейсов не прокатывает. Для интерактвных задач это конечно не use-case, но и там можно много чего придумать.
Даже если смысл применения асинхронного IO непонятен, это не значит, что никто из участников не будет его использовать. Как вы хотите это технически реализовать? Отправлять процессу SIGSTOP при любом обращении к пайпу? А если там много данных читать надо, а он читает их посимвольно?
В общем, я хочу сказать, что борьба с race conditions методом запрета какой-то функциональности — не самое удачное с архитектурной точки зрения решение.
немного не уловил.
вроде из за ВА он упасть не должен был. то есть можно относительно безопасно говорить RE ?
После того, как решение уже вывело WA (некорректный ход или проигрыш), может случиться так, что интерактор не может предложить ему никакой корректный ответ. Соответственно, непонятно, как продолжать взаимодействие, и стоит просто выйти из интерактора.
В свою очередь, решение, не получив правильное продолжение ввода в своём неправильном понимании протокола, вполне имеет право упасть с ненулевым кодом возврата.
При этом причина произошедшего, скорее всего, в том, что случился WA, а не в том, что решение потом упало по другим причинам. Например, если решение хочет проверить корректность выводимого ответа и в случае чего упасть по assert-у — логично это сделать до того, как его вывести.
Посмотрим: пусть первым завершилось решение. Оно не должно было упасть из-за того, что интерактор упал с WA.(Оно могло ожидать ввод, но не упасть, писать в пайп еще можно). (Из-за каких-то ассертов и прочих радостей — да, но тогда уже участник ССЗБ и может получить RTE).
Я, видимо, понял, что имелось ввиду: если вывелось WA, интерактор падает, а solution падает из-за того, что получил фиговую ситуацию. (Странно, кстати, зачем что-то писать, а потом не сразу читать?).[Вы об этом, кстати?] Тут по-моему, участник заслужил и WA, RE, одинаково нормально выставить и то, и то.
Возможен, например, такой сценарий:
Напомню предлагаемую смену аксиоматики для интерактивных задач: "в первый момент времени, когда стало возможным выдать вердикт, отличный от OK, выполнение должно прерываться с очевидным вердиктом".
Очевидно, что в соответствии с этим нужно вернуть WA, а не RE.
Да, имелась ввиду именно такая ситуация: участник вывел WA, подумал, упал с RTE. Тестирующая система получила WA от чекера и RTE от участника, вывела WA.
тоже немного не понял: где мы используем, что решение читает блокирующе?
А вот это хороший вопрос. Я сейчас перечитал и, по-видимому, существенно только использование блокирующих вызовов в интеракторе, когда мы хотим узнать, не хочет он сказать, что WA произошло перед некорректным завершением работы решения (если он "висит" — значит, ждёт ввода и это RTE, а иначе — WA).
А вот в решении это становится существенным в обратной ситуации, которая, впрочем, не соответствует предлагаемой аксиоматике (и поэтому не реализована в утилите): если интерактор завершился с WA, то ждём, пока решение успешно доработает до следующего ввода, чтобы имелась возможность получить RTE.
Так что судя по всему, участник получается ничем не ограничен и моя дискуссия с ilyakor почти теряет смысл.