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

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

UPD: немного поправил примеры

Некоторые из вас знают про мой плагин для Idea. Одной из его самых интересных/полезных частей является автоматическое создание конфигураций с запуском задачи на всех тестах для некоторых сайтов, а именно — Codeforces, CodeChef, Timus, E-Olimp и RCC. Некоторые другие плагины предоставляют похожую функциональность для других сред разработки и языков программирования. На текущий момент это реализовано за счет скачивания веб-страниц и их парсинга. Данный подход имеет сразу несколько минусов:

  • Повышается нагрузка на сервер (особенно в пиковое время вроде начала контеста)
  • Изменение в структуре веб-страницы приводит к необходимости исправлять парсер и выпускать новую версию. Кроме того, некоторые сайты не имеют четкой структуры оформления примеров (например, CodeChef) — приходится использовать эвристики. Некоторые соревнования — SN*S, OpenCup — используют pdf для задач, что делает невозможным (или, по крайней мере, очень трудным) их парсинг
  • Некоторые контесты (например, виртуальные) требуют логина для доступа к текстам задач. Доверять свои логин и пароль 3rd party софту — опасно

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

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

  • Иметь по фиксированному url (скажем, http://codeforces.com/contests/list.xml?key=my_codeforces_key) xml файл с мета-данными о доступных контестах, которые в случае обращения без указанного выше ключа сообщают о контестах, доступных для всех, а в случае его наличия, а в случае обращения с ключом — доступные конкретному человеку. При этом может сообщаться дополнительная информация. Пример:

<site>Codeforces</site>
<icon url="http://codeforces.com/favicon.png" />
<contest-list>
  <contest id="211">
    <name>VK Cup 2012 Finals</name>
    <name locale="ru">VK Cup 2012, Финал</name>
    <url>http://codeforces.com/contest/212/contest.xml</url>
    <status solved="4" attempted="4" />
  </contest>
  ...
</contest list>
  • Аналогично — для контеста иметь описание в примерно таком формате:
<contest id="211">
  <name>VK Cup 2012 Finals</name>
  <name locale="ru">VK Cup 2012, Финал</name>
  <task id="211A">
    <name>Privatization</name>
    <name locale="ru">Приватизация</name>
    <url>http://codeforces.com/contest/211/problem/A.xml</url>
    <status solved="false" attempted="false" />
  </task>
  <task id="211B">
    <name>Polycarpus is Looking for Good Substrings</name>
    <name locale="ru">Поликарп ищет хорошие подстроки</name>
    <url>http://codeforces.com/contest/211/problem/B.xml</url>
    <status solved="true" attempted="true" />
  </task>
  ...
</contest>
  • Ну и наконец — для задачи:
<task id="211B">
  <name>Polycarpus is Looking for Good Substrings</name>
  <name locale="ru">Поликарп ищет хорошие подстроки</name>
  <status solved="false" attempted="false" />
  <input file="false" />
  <output file="false" />
  <memory-limit value="256" />
  <test-type value="single" />
  <test-case id="0">
    <input>aaaaa\n2\na\na\n</input>
    <output>1\n1\n</output>
  </test-case>
  <test-case id="1">
    <input>abacaba\n3\nac\nba\na\n</input>
    <output>1\n2\n4\n</output>
  </test-case>
</task>

Задача данного поста — понять, считает ли коммьюнити введение подобного единого стандарта хорошим шагом и помочь сформулировать полную спецификацию формата

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

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

\n выглядит странно в xml. Казалось бы, &#xA;.

Upd 1. Теги I/O лучше (когда возможно несколько)

<input><file>stdin</file><file>input.txt</file></input>
<output><file>stdout</file><file>output.txt</file></output>

Кроме того, в общую информации хотелось бы макрос проверки компиляции на сервере (ONLINE_JUDGE).

Upd 2. В первом примере нарушен принцип "в xml должен быть root-узел". Может быть, <site name="Codeforces"> ... </site>

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

    Казалось бы &#xA; выглядит странно, так как в XML такой сущности нет. Наиболее естественно выглядит перевод строки как есть. Кодировать надо только амперсанд, меньше-больше и два вида кавычек.

    Что за множественные варианты IO? Это где-то используется? Про ONLINE_JUDGE да, идея хорошая, только вот поддержка и ее способ зависят от языка.

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

      All permitted Unicode characters may be represented with a numeric character reference. Consider the Chinese character "中", whose numeric code in Unicode is hexadecimal 4E2D, or decimal 20,013. A user whose keyboard offers no method for entering this character could still insert it in an XML document encoded either as &#20013; or &#x4e2d;. Similarly, the string "I <3 Jörg" could be encoded for inclusion in an XML document as "I &lt;3 J&#xF6;rg".

      http://en.wikipedia.org/wiki/XML#Escaping

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

        Ну да, можно и так. Кажется, записи эти эквивалентны. Еще тонкость — тест это не текст, а последовательность байт. Поэтому рассматривать его как UTF-8 или UNICODE-строку наверное нехорошо. Уж лучше каким-нибудь base64 байтики закодировать и как атрибут вставить.

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

      ONLINE_JUDGE — просто указывать директиву препроцессора, как ее обрабатывать — вопрос программы.

      На последнем SNSS были обе возможности — читать из stdin и читать из файла.

      Про &#xA; (как верно подмечено riadwaw это одна из форм записи произвольного символа) — есть робкая надежда, что так записанный перевод строки создаст меньше проблем произвольному парсеру, чем просто записанный перевод строки (там бывают спецэффекты).

      Про xml — для автоматических генераторов в нашем неидеальном мире, в целом, предпочтительно записывать содержимое всех "неизвестных" строк через <![CDATA[текст]]> внутрь тега так:

      1. Ряд символов, которые в принципе невозможно записать в xml (все из диапазона U+0..U+1F, кроме \r, \n и \t; несуществующие символы U+B800..U+BFFF) просто удаляются — их и существовать не должно.

      2. Если в тексте встречается последовательность ]]>, то CDATA переоткрывается посередине: для текст]]>такой записывается <![CDATA[текст]]]]><![CDATA[>такой]]>. Такая конкатенация, хотя и рассматривается как два text element парсером, правильно выдает содержимое свойства text у тега.

      Все остальные способы очень рискуют попасться рано или поздно на какую-нибудь редкостную проблему, вроде первого пробела, первого (последнего) перевода строки, zero-width-non-joiner, случайно попавшего в текст и т.д. и т.п.

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

Идея хорошая. Если организаторы подключатся, это однозначно шаг вперед.

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

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

    Думал об этом, но это выглядит нечестно. Дело в том, что это дает явное преимущество пользователям автоматических средств. Кроме того, это поле явно забивается вручную, т.е. это дополнительная нагрузка на авторов контеста.

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

    Мне тоже кажется выдача чекера не очень идея.
    Человек должен сам догадаться (из формата вывода), как его будут проверять.

    Тупой пример:
    Есть задача "....выведите любой подходящий пример", а ответ один. В таких случаях не нужно светить чекер.

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

      Я не понимаю о чем вы. Я предлагаю определить набор стандартных чекеров, можно прямо взять те что есть в полигоне. Выдать им строковые идентификаторы типа wcpm, lcmp и т.д. И сделать зарезервированный идентификатор custom. Клиентские программы тогда смогут точнее сравнивать вывод, в случае стандартных — повторить их действия, в случае custom например сравнить посимвольно и если не правильно то выдать предупреждение, что может ответ и нормальный, т.к. чекер нестандартный.

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

        Да я понял, о чем вы.

        1) Мне (субъективно), кажется, что дело участника догадаться из условий, как его будут тестировать.

        2) Пример(может быть немного искусственный), когда автоматическое проставление такого не будет работать: Есть задача, в ней написано "выведите любой из возможнх вариантов ответа, оптимизирующий что-то" (типа найдите самй короткий путь, выведите сам путь), но ограничения в задаче такие, что ответ всегда единственен(в данном примере: дано дерево или все веса — различне степени двойки). Естественно в данном случае использовать стандартнй потокенный чекер. Но сообщать об этом пользователю нельзя.

        Ну и да, расставление этого ручками считаю плохим вариантом

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

          И при тестах, не соответствующих условию, участники будут тупо ловить WA и терять время.

          В то время как интеллектуальный чекер как найдёт ошибку в решении автора (и выдаст JE), так и корректно обработает граф, в котором пример не единственен (и может тоже выдать JE, если ответы не совпадают).

          Особенно это становится критично в случаях, когда тесты взяты as is, а валидатор в технологии отсутствовал.

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

            Для тестов не соответствующих условию есть валидатор, который отловит это еще раньше.

            В целом я не спорю с тем, что интеллектуальный чекер лучше неинтелектуального, но, по-моему, иногда овчинка выделки не стоит.

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

          По первому пункту. Я не понимаю о чем там догадываться. Я просто предлагаю сделать так, чтобы клиентская прога могла нормально сравнивать ответ с сэмплом. Если в задаче ответ не однозначный, значит чекер custom (а в условии пишут стандартную фразу про то что если ответов несколько выведите любой). Если ответ один, то тут не о чем догадываться, кроме всякой ерунды типа можно ли оставлять пробелы на конце (или между токенов), или выводить с десятью знаками после запятой вместо восьми. И вот эта ерунда и будет в стандартных чекерах.

          По второму пункту. В такой задаче надо делать кастомный чекер. И не важно что там один ответ. Все равно лучше сделать проверку на оптимальность в чекере, и более того проверять а не лучше ли пользовательский ответ того, что жюри выдало. А то всякое бывает, и жюри могли ошибиться в доказательстве того, что ответ всегда один.

          По поводу расстановки ручками. Если это вводить здесь на CF, то в полигоне все и так есть. Если брать что-то другое, то можно автоматом по умолчанию проставлять custom, хуже не будет. А потом глядишь и другие подправят у себя чекеры под стандартные и начнут о них инфу давать.

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

я думаю, достаточно просто попросить, чтобы авторы контестов расставляли теги input/output и т.д. на страницах с задачами. Работы минимум, на внешнем виде страниц это никак не скажется, а польза практически та же самая. Нагрузка на сервера, даже в началах контестов, я не думаю что такая уж проблема

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

Надо не забыть про интерактивные задачи.

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

    С интерактивными задачами это имеет смысл только если предоставляется код интерактора. Иначе непонятно что такое семпл

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

Интересная дискуссия выходит — это хорошо. Хотелось бы высказать пару мыслей:

  1. Многие теги можно сделать необязательными — типа test-type и checker.

  2. Можно очень много всяких свойств, в том числе специфичных для каждого языка вынести в contest-list. Или создать отдельный корневой файл с описанием джаджа и списка списков контестов — например, для Codeforces разумно иметь 2 списка — обычный и gym

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

I have installed beta 10. But don't see launch topcoder button anywhere.

Also was trying to run a codeforces task and getting this error.