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

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

Идея написать что-то подобное у меня возникла еще после сборов в Петрозаводске, где Михаил Мирзаянов прочитал лекцию о том, как правильно готовить контесты. На мой взгляд, лекция была очень правильная, и было бы здорово увидеть ее здесь, на Codeforces. Спустя некоторое время тема забылась, но фейл (полный провал - прим. Артема) с условиями на 58 раунде напомнил о ней. Хочу обратить внимание, что все написанное здесь это, конечно, наше мнение, но оно все же основано на довольно большом опыте.


Итак, из чего состоит условие задачи? (сверху вниз, затем слева направо):

  1. Название
  2. Ограничения (Time Limit, Memory Limit)
  3. Текст условия
  4. Перевод условия*
  5. Формат входных данных
  6. Формат выходных данных
  7. Источник и приемник данных
  8. Тесты
  9. Комментарии к тесту*

* - опционально

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

Теперь обо всем по порядку.

Название

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

 Хорошо, если в английском названии первая буква совпадает с индексом задачи (Эта традиция многих ACM-контестов, однако это правило подходит только для английской версии условия)

Ограничения
Ограничения обязательно должны быть указаны для каждой задачи! Кроме того, нужно сообщать об особых параметрах для некоторых языков (например Java) если такие есть.
 Плохо писать ограничения для всех задач только на отдельной странице.
 Плохо делать разные или нестандартные ML. Если ваша задача требует больше 256 МБ памяти - задумайтесь, может быть, это плохая задача?
 Хорошо делать одинаковые TL для всех задач.

Текст

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

 Плохо писать слишком длинную сказку.
 Плохо, если в сказке скрыта важная информация.
 Нельзя допускать грамматических или грубых пунктуационных ошибок.
 Не старайтесь завуалировать необходимую фразу, которая может подтолкнуть к решению - это может привести к тому, что условие будет истолковано неверно.
 Хорошо организовывать и структурировать полезную информацию в виде списка. Несмотря на очевидность, мало кто этим пользуется.
 Любая важная информация должна быть четко написана в условии, а любые нюансы не должны теряться в массе текста. Это ведь соревнования по программированию, а не по литературе.
 Особо важные моменты можно выносить отдельно. К сожалению, в традиционных контестах используется редко, в отличие от TopCoder (в условиях пометка Notes).
 Очень хорошо всегда давать читать условие человеку, незнакомому с задачами. Потом спрашивайте, как он понял условие. Выясняйте, насколько хорошо он понял нюансы и нет ли в вашем условии неточностей или неопределенностей. Помните, что читабельность и понятность в данном случае важнее изящества. Здесь работает правило “покупатель всегда прав”, и если вы встретили человека, который понял условие неверно, значит условие плохое.

Перевод

Все правила, обозначенные для текста на родном языке, должны применяться и здесь. Кроме того, часто бывают ситуации, когда вы не знаете как перевести ту или иную фразу. У вас есть два варианта:

 Залезть в словарик, учебник, и т.д. и найти нужное правило. Это плохой вариант. Вполне вероятно, что вы не так передадите смысл.
 Изменить фразу так, чтобы она стала понятна и вам без всяких разъяснений! Как показывает практика, люди скорее поймут ваше топорное "твоя-моя", чем мудреный некорректный оборот. Помните, что есть люди, которые английский знают на вашем уровне, но при этом не имеют возможности прочитать условия на языке оригинала!
 Обязательно дайте прочитать переведенный вариант человеку (а лучше двум - с хорошим знанием языка и плохим (: ), которые не знают задачу и не читали исходный вариант условия. Это - гарантия того, что вы не упустите какую-то мелочь или неточность.

Формат входных данных

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

Условно можно разделить задачи на две категории: задачи на форматирование текста и все остальные. Все нижесказанное относятся только к задачам второго типа.
 Плохо делать лишние whitespaces, кроме перевода строки в конце потока.
 Плохо, когда нельзя явно вычислить количество строк/элементов во входном потоке (и приходится использовать while(scanf(“”Гена одержал”)).
 Не используйте нестандартные или непечатаемые символы. В том числе кириллицу. Не надо. Серьезно.
 Я считаю, что нужно указывать ограничения на все входные данные, в т.ч. количество тестов, если это мультитест. К сожалению, на финалах данное не соблюдается, поэтому вы вправе игнорировать этот пункт.

Формат выходных данных

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

 Обязательно используйте одинаковое написание стандартных слов во всех задачах (YES/Yes).
 Тем не менее, для проверки слов yes, no, no solution, impossible и т.д. лучше использовать чекер, не чувствительный к регистру.

Потоки ввода и вывода

Как правило, используются стандартные потоки (stdin, stdout) или файлы.

 Очень плохо делать смешанные варианты (stdin + file.out).
 В имени файла допустимо использовать только маленькие латинские буквы, цифры и символы подчеркивания. Необходимо наличие расширения.
 В таблице с тестами пишите название потока или файла вместо "входные данные".
 Используйте стандартные имена файлов (input.txt/output.txt, file.in/file.out).
 Хорошо, если имя файла совпадает с индексом задачи (a.in).
 Можете указать, что работа со стандартными потоками означает ввод и вывод через консоль - новички скажут вам спасибо.

Тесты

О правильной подготовке тестов подробно рассказано в презентации Михаила Мирзаянова. Очень надеемся, что она появится на Codeforces.

 Старайтесь не давать бессмысленных тестов (например, граф без ребер). Исключение составляют тесты, ответы на которые явно наталкивают на решение.
 Обязательно проверяйте тесты из условий валидатором!
 Помните, что тесты из условия являются частью описания входных данных.

Комментарии к тестам
 Очень плохо, если после тестов идет информация, не относящаяся непосредственно к тестам (например, примечания).
 Очень хорошо наличие комментариев, поясняющих, как получен ответ на входной тест. Опять же, не используется почти никогда, кроме TopCoder, а зря.

Удачи и успешно проведенных контестов!

 Илья Акользин и Артем Верхоглядов, MIPT Guinness and Pistachios.
  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
И сразу добавлю от себя:
Google Docs - замечательный инструмент для совместной работой над документами и статьями! Так забавно видеть, как кто-то другой удаляет твое предложение и отвечать ему тем же :DD
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Отличная статья!
Надо чтобы с ней в принудительном порядке ознакамливались все люди, готовящие контесты :)
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    И по-поводу

    "Обязательно используйте одинаковое написание стандартных слов во всех задачах (YES/Yes)."

    Сразу вспоминается один раунд SN*S, где во всех задачах было DataSet #1:, а в одной DataSet 1:, и это при формате, где каждый штраф - это -0.2 задачи... Я там, как и почти все, свои заслуженные -0.2 задачи на этом поймал.

     

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да-да, такое реально часто бывает, хоть и звучит как бред сивой кабылы!
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Я один раз решал задача в которой надо было выводить либо YES либо No. Сдал с +1 понятно почему
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Статья и вправду отличная!
А замечание такое: делать длинную легенду, в которой встречается крайне важное для решения слово, причём это слово thousand, может быть и полезно. В качестве подготовки к финалу ]:->
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Предлагаю все вещи, которые могут быть полезны на финале и только там не использовать в общедоступных контестах. Для подготовки к финалам есть закрытые сборы в Петрозаводске, вот там и место для подобной узкой подготовки.
14 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится
Очень плохо делать смешанные варианты (stdin + file.out)

Авторы GP Саратова, если вы это читаете, пожалуйста, не делайте больше такой странный ввод-вывод. Спасибо.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Читать-то читаем, но высказанные тут утверждения являются отражением мнения автора поста, а не абсолютными истинами. На мой взгляд, сочетание файлового ввода и стандартного вывода - самое удачное. А вот стандартный ввод и файловый вывод, в самом деле, очень неудобно.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Такой ввод-вывод много лет использовался на финале ACM-ICPC, а мы планировали сделать контест на сборы по подготовке к этому мероприятию. Кстати, я, когда решаю задачи, то обычно использую именно такой вариант - с одной стороны не надо вводить каждый раз тест, с другой стороны вывод легко доступен по мере его появления.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я тоже, только в мой шаблон оказалась включена строка, чтобы я не забыл переключить вывод на нормальный. И эта строка вызвала несколько PE#1. Тогда уж давайте все олимпиады проводить с таким вводом-выводом. А то найдется комбинация против любого шаблона.
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Есть причины почему на Codeforces stdin/stdout. Ниже уровень входа для новичков (как читать с консоли в школе учат, но не всегда учат, как читать из файла). С другой стороны такие программы (которые работают через stdin/stdout) легче поддаются автоматизации при написании вокруг них каких-то скриптов (очевидно откуда писать, читать, это не зависит от задачи, в разных bash и cmd есть встроенные средства по манипуляциям с stdin/stdout).

        Названия "стандартный поток ввода", "стандартный поток вывода" намекают, что это стандартные способы взаимодействия программ через IO.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          На CF то понятно почему. Это вообще скорее не к вам претензия а просьба к тем, кто может повлиять на это на opencup/четвертьфиналах и т.п.. Или уж хотя бы либо заранее оповещать участников о файлах (видел в каком-то контесте в правилах олимпиады указание на то, как примерно будут называться входные и выходные файлы), либо в пределах одной серии олимпиад все делать одинаково (а не как в opencup первый тур с такими файлами, второй с такими).
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    По-моему, максимально удобный для участника вариант ввода-вывода - именно смешанный (file.in + stdout). Результат работы программы виден сразу без лишних действий, а если нужен дебаг - не приходится вводить тест заново.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну я уже написал выше, что я в общем то не против, если мне сообщат об этой неожиданности хотя бы минут за 5 до контеста.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну если речь идёт про opencup, то это очень странное требование, учитывая, что по правилам prewritten code запрещён.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
> Залезть в словарик, учебник, и т.д. и найти нужное правило. Это плохой вариант.

Не вижу ничего плохого, если словарь называется «Oxford English Dictionary».
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Я-вижу. Фактически никогда дословный перевод не совпадает переводом по смыслу. Каждое русское слово можно перевести десятком слов в английский, и даже в оксфордском можно не уловить разницу в смысле. Есть так же обороты, которые переводятся совсем по другому. Даже если ты переводчик, можно не найти хороший перевод(именно поэтому мы часто критикуем перевод фильмов). А уж искать его в словаре-совсем плохо.
    • 14 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится
      Вообще-то в словаре «OED» в принципе нельзя найти дословный перевод с русского языка. Так что ты не всосал в мой камент.


      А разницу в смысле уловишь обязательно, потому что толковые словари именно для этого и создаются.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Жду не дождусь Ваших контестов здесь.
14 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Я бы не называл тесты в условии тестами. Лучше примерами (samples по английски). Ну и добавил бы, что тесты должны начинаться с примеров, причем в том же порядке как и в условии. Далее, хорошо когда примеры показывают что выводить в не совсем очевидных ситуациях. Вот недавно был 56-й раунд, где в первой задаче было не очевидно что именно выводить если ответ 0, то ли 0 то ли -1. Другой пример это когда в задаче надо вывести значение какой-то функции от какого-то множества. Далеко не всем очевидно, что по умолчанию значение функции от пустого множества это 1. Надо или ставить ограничения, чтоб таких случаев не было, или приводить этот пример в условии.
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Мне не нравится стиль a.in/a.out. Контесты часто разбираются на задачи (например, тренировки) и это приводит к тому, что надо править условия, авторские решения (а иногда и что-то еще). В результате появляются одинаковые задачи в разных редакциях.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Важно отметить, что легенда, не смотря на литературность, должны формально определять условие задачи. То есть в ней должны быть явно написаны все факты и ньюансы задачи. Мутноватые вещи надо разжевывать на примерах (например, "abcbab" некрасивая строка, так как ...). Хорошо помогают пониманию картинки.

Еще важно отметить, что если задача графовая, то всегда проверьте:
  • четко ли написано какой граф - ориентированный или нет,
  • четко ли написано про кратные ребра и петли,
  • подумайте что со связностью, имеет ли ваша задача смысл, если граф несвязный,
  • написано ли как нумеруются вершины (ребра если надо).
14 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Хорошая статья, но немножко общая. А поскольку тут все-таки один конкретный codeforces, то можно просто часть правил сделать обязательными для всех контестов сайта, сформировав таким образом некий "фирменный стиль". В принципе, сейчас уже наполовину так и есть, просто нигде в одном месте не собрано и не прописано. 

В основном это, конечно, будет касаться форматов входных/выходных данных, но можно включить и некоторые правила по оформлению условия или даже упорядочить всякие мелочи типа того что "Yes" всегда пишется как "Yes", но чекеры принимают и как "YES".

  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    а вот всякие мелочи, вроде "чекеры принимают YES вместо Yes" - это уже неудачная идея

    если, допустим, есть официальный и принимаемый всеми документ о том, как должна выглядеть задача, работать чекер и т.п. везде, а не только на CF - да, я согласен; но ситуация обстоит иначе, и мы рискуем получить кодеров, абсолютно неготовых к "экстремальным" ситуациям на других контестах, в чекерах которых "Yes" не равно "YES"

    и потом: почему от авторов требуется максимально чёткая формализация тестов (валидаторы не пропустят тест, даже если в нём есть лишний перевод строки, или наоборот, в конце текста его нет), а участники могут выводить всякую фигню?
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Ну, с YES/Yes в чекерах не настаиваю, может и правда перебор уже.

      А что касается всякой фигни, то автор примерно один, а участников много и пишут они на разных языках, в которых ввод и вывод устроен по-разному. Чтобы случайно не превратить для кого-нибудь обычную задачу в задачу на разбор/форматирование текста(или еще какую свинью подложить) лучше все-таки придерживаться некоторых ограничний при составлении тестов и допускать некоторые вольности при проверке вывода.

      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вы совсем неправы - как раз на codeforces и авторов и участников много, и счет первых скоро пойдет на сотни. Правила должны быть достаточно общими, чтобы они не ограничивали CF от всего мира. 
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Я имел ввиду что у каждой конкретной задачи автор обычно один.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Как уже ответили, она не относится к КФ, потому что одним КФ дело не ограничивается, и мы (увы) не входим в авторский состав этого проекта, так что писать "законы" для других авторов просто не имеем права. 
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, я и не предлагаю вам этим заниматься =) Но, по-моему, было бы неплохо если б те кто право имеют соорудили подобный свод правил применительно к КФ и повесили на видное место.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А есть какие то рекомендации по типографике текста задач ?