Блог пользователя NALP

Автор NALP, 12 лет назад, По-русски

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

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Я писал интеракторы так: чекер выдавал вердикт, а интерактор возвращал 0 (подождать решение участника) или 1 (убить решение участника и запустить чекер). Поэтому у меня было 5 вердиктов: ok0, wa0, wa1, pe0, pe1. Конструкция для считывания данных была такой:

switch (scanf("%d", &t)) {
case 1:
	break;
case -1:
	pe0("Unexpected eof");
	break;
default:
	pe1("Wrong output format");
	break;
}

Если вместо pe0 написать pe1, то не будут выдаваться вердикты TL, ML, RT.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Представим, что решение упало при выводе числа (маловероятно, но все же). Например, оно собиралось вывести некое отрицательное число, поставив перед положительным знак минус, а потом само положительное число. (Например, знак обозначает какое-то направление и по решению мы отдельно получаем направление и модуль ответа). Между этими двумя выводами участник сделал assert решения и он фейлится. Это приведет к тому, что в интерактор попадет просто знак минус, который проинтерпретируется как pe1 -> будет PE, а не RE.

    Следует учесть, что вывод/чтение чисел это простейшая операция, а иногда бывает и хитрее — строки (возможно с определенной структурой), последовательности и проч.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Это легко решить на системном уровне. Надо просто не передавать строку интерактору, если она не заканчивается символом конца строки.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Извиняюсь, а есть ли где-то технические подробности — вдруг я что-то упустил. Т.е. конкретно на какой платформе реализован интерактор и как он запускает процессы... Линуксовый с fork/exec или жаванский или что?

Казалось бы нужно ждать не завершения потока а раньше ли случится WA от чекера или исключение/выход от решения. Наверное при некоторых реализациях можно ещё придумать ситуацию когда в решении возникает исключительная ситуация, но до получения управляющим потоком ошибки происходит передача управления и чекер выдаёт WA/PE (а интерактор глядит — второй-то поток ещё жив!). Но это подозрительно и фантастично т.к. если интерактор самовольно начинает разбор потока то он и раньше мог неполный ответ прочесть. В общем если можно, расскажите плиз подробнее... %)

(Идеальным бы решением был собственный механизм выполнения потоков, этакая не песочница а теплица с вытеснением контекстов, но учитывая количество компиляторов и интерпретаторов поддерживаемых это, наверное, мучительно было б реализовывать)

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Интерактор сам ничего не запускает, он такой же процесс, как и решение. Его и решение замыкают в пайп.

    А вот механизм запуска совершенно ничего не знает о протоколе, он оперирует процессами, и эту схему менять не хочется.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      О, я туп, но кажется понял. Я должен был писать "интерактор" вместо "чекер" и "запускатор" вместо "интерактор". Вы имеете в виду что "запускатор" не выносит вердиктов? А вердикт TLE, например, кто фиксирует?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        "запускатор" выносит вердикты только типа TL, ML и еще что-то.. и после "запускатора" мы знаем exit-code решения и интерактора. В целом это почти все, что мы знаем стандартными средствами.

        из нестандартных: например, интерактор может вести свой лог, ну еще что-нибудь

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится -15 Проголосовать: не нравится

перенаправить средствами ОС stderr решения в его stdout, тогда интерактор во всем сможет разобраться. Если разбираться должен чекер или еще кто-нибудь, то перенаправить stderr и решения и интерактора в одно и то же "куда угодно" — от кого пришел первый эксепшн, тот и молодец.

или еще вариант: определивший неверные данные интерактор должен падать не сразу, а например через пару сотен миллисекунд. Тогда ОС вряд ли ошибется

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    Ну а вариант ниже у нас в голове тоже давно лежит.. но все равно хочется решение поизящнее..

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Кстати, если интерактор завершился раньше с вердиктом WA, то это ещё не значит, что система должна выдать вердикт WA. Например, участник вывел ответ "DONE x", этот ответ оказался неверным, а после вывода программа виснет в бесконечном цикле. Понятно, что здесь интерактор может завершится раньше, но мне кажется, в этой ситуации надо выдавать вердикт TL. Когда я ждал ответ от участника, я выдавал ok0 / wa0, а не ok0 / wa1.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    ну всегда приоритет TL больше, чем WA, как и в обычных задачах

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну да, у вас немного другая технология, чем на ejudge. Я столкнулся с проблемой, что после вывода мусора интерактор завершался, а программа участника продолжала висеть в системе.

      Все равно я немного не понимаю вашу технологию. Как она различает эти случаи?

      Здесь надо выдать TL:

      printf("DONE 1\n").
      fflush(stdout);
      while (1) {}
      

      Здесь надо выдать PE:

      printf("Done 1\n").
      fflush(stdout);
      while (1) {}
      
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        и то, и другое получит TL, что логично, так как у TL приоритет больше

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Понятно. Но в интерактивных задачах иногда лучше выдавать WA / PE, не дожидаясь корректного завершения программы участника. Иначе участнику придётся много чего лишнего писать в своей программе, хотя всё может организовать в системе.

          Если WA / PE выдавать как в обычных задачах, то участник должен перед каждым вводом и выводом писать:

          if (feof(stdin)) exit(0);
          

          иначе он будет получить TL, RT, ML вместо WA / PE.

          А вдобавок ему ещё надо вручную считать количество запросов, и если оно превысило (QL-1), то делать

          while (1) {
          new double[10000];
          }
          

          И при выводе делать assert, если вдруг он выведет одинаковые числа, выведет повторную клетку, выведет число не из промежутка и т. д.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            откуда это все? О_О

            разумеется, интерактивные задачи нужно формулировать так, что либо:

            • решение сразу знает, сколько запросов обрабатывать;
            • интерактор умеет давать решению команду остановиться.

            а то, что ты написал — это не очень...

            • »
              »
              »
              »
              »
              »
              »
              12 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              В теории мне тоже казалось, что всё будет работать как надо, но после первого же прорешивания командой СпбГУ4 выявилось слишком много проблем. В линуксе ещё есть проблема с SIGPIPE. Если участник что-то выводит, а интерактор закрыт, то это приведёт к RT.

              Все мои интеракторы сообщали когда надо выйти из программы, но участники, даже зная это, не пишут проверку. Например, думают, что 2 цикла сделают не более 50 запросов, и в них не делают проверку. В результате вместо WA получают RT.

              Или как правильно написать интерактор с использованием testlib, если надо попросить участника вывести массив из n элементов от 1 до k? Допустим, вторым числом он вывел 0. Это PE. Но как в таком случае написать автору интерактор? Я пишу так:

              for (int i = 0; i < n; i++) {
                  a[i] = readInt(1, k);
              }
              

              Но после второго числа интерактор закроется, а участник попытается вывести третье, случится SIGPIPE и система выдаст RT. И таких случаев полно, для всех случаев не сделать заплатки.

              Идею с кодом возврата интерактора я взял с системы полуфинала PCMS. Там тоже вердикты WA / PE могут даться раньше, чем закончится программа участника.

              • »
                »
                »
                »
                »
                »
                »
                »
                12 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Про проблемы на OpenCup. То, что участники не обращают внимания на вывод интерактора — это они сами себе злобные буратины, и будут получать свой заслуженный Runtime.

                Про случай с массивом: вот как раз об этом и пост :) как сделать это аккуратно, если интерактор уже понял палево, и продолжать не может.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                  Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                  На Opencup были проблемы только у тех, кто писал заранее. К основному этапу уже был патч к ejudge и проблем таких не было.

                  Опять же, как тогда писать условия к задаче? Например, к G.

                  После команды Reflect x (1 <= x <= n), участник должен считать n вещественных чисел. Но что если он выведет Reflect 0? Мой интераткор скажет системе выдать PE и закрыть программу участника. А иначе какой выдавать стоп-символ? Первоначально, я выдавал строку Quit. Но будут ли участники дива2 считывать строку и парсить её в массив вещественных чисел на паскале? И как написать про это в условии?

                  После команды Reflect x, считайте строку, если это не Quit, распарсите её на n вещественных чисел, а если вы этого не сделаете, то вы получите случайный вердикт TL, PE, RT, в зависимости от вашей реализации.

                  Участник дива2, конечно, выберет получать неадекватный вердикт, чем писать парсер.

                  Кстати, количество запросов иногда не знает даже сам интерактор (задача H).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Именно об этом я и написал пост. И из него понятно, что у меня нет ответа на этот вопрос.

                  Пока все придуманные решения — костыли по большому счету.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Ну так, а чем плохо решение, которое используется на полуфинале? Сделать больше вердиктов:

                  ok (проверять на TL, ML, RT)

                  wa0 (проверять на TL, ML, RT. Если ничего из этого нет, то выдать WA)

                  wa1 (не проверять на TL, ML, RT)

                  pe0 (проверять на TL, ML, RT)

                  pe1 (не проверять на TL, ML, RT)

                  Это решает все проблемы. Другого решения я за год найти не смог.

»
12 лет назад, # |
Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

Прочитаем очередной ответ решения до перевода строки или до EOF. Если мы ещё не увидели EOF, попытаемся неблокирующе прочитать ещё символ. Если результат чтения — EAGAIN/EWOULDBLOCK (ну или что там в Windows), то считаем, что всё хорошо (решение ожидает наш ответ). Если мы получили неожиданный EOF, то решение по какой-то причине завершилось.

Далее разбираем случаи:

  1. всё хорошо, ответ решения допустимый — продолжаем работу по протоколу;
  2. всё хорошо, ответ недопустимый — WA;
  3. был EOF — завершаем интерактор с каким-нибудь другим кодом. Тестирующая система видит это и смотрит на код завершения решения. Если EXIT_SUCCESS — то WA, иначе — RE.

Что ещё надо учесть:

  1. Надо решить, что делать, если при попытке заглянуть вперёд мы успешно считаем символ.
  2. Если протокол разрешает решению вывести ответ и сразу выйти, а не ждать команды, то этот случай надо обрабатывать особо, так как здесь тоже получим EOF.

Как выглядит такой метод?

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Хм, что-то я никак не пойму, в чём проблема. Похоже, вся ботва получается из-за странной архитектуры на картинке в посте по ссылке :)

Чем плоха такая схема: есть тестирующая система, она запускает программу и интерактор. После этого она повторяет процесс "получить строку у интерактора, скормить программе, получить у программы, скормить интерактору". "Время" в таком случае дискретно (т.к. момент времени — количество строк), и проблемы "что упало раньше" нет. Да, такая схема накладывает ограничения на формат ввода/вывода, но 1) это довольно-таки хорошо — какая-никакая стандартизация, 2) если очень хочется "нестандартный" формат — можно написать конвертер, который будет между жить программой и тестирующей системой и упаковывать вывод программы в строку/распаковывать ввод из строки. Достоинство этой схемы — всё дискретно и просто.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, вся ботва в той схеме. А именно через тестирующую систему никакие данные не прокидываются, только напрямую между процессами

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Есть проблема с производительностью — по такой схеме гонять данные туда-сюда становится в два раза дороже по сравнению с прямым обменом данными между решением и интерактором, да и переключений контекста теперь больше.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Bottleneck в задачах по программированию обычно всё же не в копировании ввода/вывода, тем более в памяти. Само решение обычно работает существенно дольше, да и накладные расходы из-за безопасного запуска, коммуникаций между тестирующими машинками и сервером, etc. обычно сильно больше.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Почти хорошо, может так и надо делать. Но казалось бы, есть задачи, где первый ход делает решение (угадайки). Кроме того писать прослойки понадобится регулярно. Очень часто один элемент input-а (т.е. вывод интерактора) занимает более одной строки: любые наборы неэлементарных величин — например, ребра при описании графа. Не забывайте, что хочется не только изобрести свою схему, но и уметь поддерживать чужие интерактивные задачи, а они вполне могут не следовать описанному выше принципу.

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Как вариант (по крайней мере у нас так сделано) — система запускает интерактор и решение + 2 потока, которые занимаются исключительно перебросом данных через пайпы: первый — от интерактора решению, второй — от решения интерактору.

      Кажется, такая схема от формата ввода-вывода в задаче не зависит никак.

      И такая схема решает вопрос с тем, кто завершился раньше, поскольку второй процесс не завершится (поскольку ему в пайп пишет система), а стало быть либо завершится решение, либо интерактор.