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

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

Процесс творения раунда без прикрас и страшилок.
Путеводитель по творению раунда от автора четырёх Codeforces раундов.

Спасибо RodionGork, который придал мне необходимый испульс и hball1st, который придал необходимый импульс RodionGork.

1. Придумывание задач.

Тут сложно дать какой-то совет. Нет какого-то определённого алгоритма придумывания задач, а если бы он был, получились бы не задачи, а сложные упражнения на стандартные алгоритмы, как половина задач на Russian Code Cup. Чтобы получилась хорошая, интересная задача, должна быть какая-то идея, которая пришла в голову Вам, а потом должна прийти в голову участникам соревнования. Какая-то, хотя и самая элементарная, но идея, в идеале, должна быть даже в задаче A второго дивизиона. Так что, должен сразу предупредить, что, поскольку творческое мышление — процесс, воспитываемый с самого детства, то придумывать задачи дано не всем. Увы. Мне лично очень помог опыт составления математической олимпиады ЮМШ (это ежегодная открытая всероссийская олимпиада по математике, которая проходит в Питере). Примерно через год придумывания баянов и чисто технических задач на всем известные идеи, которые твёрдо отвергались опытными членами жюри, до меня дошло, что нельзя просто взять и придумать задачу. Но если постоянно об этом думать, рассматривать разные математические модели с разных точек зрения, то со временем могут начать рождаться интересные задачи.

Это всё равно что искать в лесу грибы. Нельзя просто пойти в определённое место и найти там гриб. Если Вы уже знаете, что там гриб — скорее всего, это означает, что все знают, что там гриб. А какой же это гриб, если все знают, что он там? Чтобы найти гриб там, где про него никто не знает, надо пойти в незнакомые места и заглядывать под листики. Далеко не под каждым листиком можно найти гриб, но под некоторыми они есть. Так что, ищите и, может быть, найдёте.

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

2. Составление проблемсета.

Тут задача понятна. Если Вы уже накопили достаточно задач, то можно попытаться составить из них проблемсет. В зависимости от Ваших целей, в нём должно быть 5 или 7 задач (а может, и какое-то другое количество, в необычных случаях). В принципе, сложность задач не слишком фиксирована. Главное, чтобы задачи шли по возрастанию сложности, а контест в целом может получиться более сложным или более простым. В соответствие с эти, одна и та же задача может сыграть роль D, а может — C. Кроме того, бывает нестандартная сложность задач. Насколько я могут судить, организаторы относятся к этому спокойно. Но в пределах разумного, конечно. Составить контест 500-500-1000-1500-1500 Вам никто не даст.

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

3. Решиться обратиться к Gerald.

Gerald не страшный. Он клёвый. После того, как Вы собрали свой проблемсет, надо просто обратиться к нему любым образом (я написал здесь в личку), ну а дальше уж вы выберете, каки образом общаться. Я с ним, например, в основном переписывался вконтакте, а когда требовалось написать что-то большое (проблемсет, новая задача, доказательство, описание алгоритма) — то на почту.

Gerald рассмотрит Ваш проблемсет, и честно скажет Вам, если какая-то задача баян, или какая-то задача просто плохая по каким-то причинам, или если Вы неправильно оцениваете сложность какой-то задачи. Всё это не страшно, сочинительство задач — очень сложное искусство и все это знают. После этого Вы можете заменить какую-то задачу, или изменить её так, чтобы она приобрела нужную сложность или качество. После некоторых обсуждений, Вы придёте к конценсусу. У меня всегда (и с RAD, и с Gerald) уходило примерно 3-4 паручасовых обсуждений.

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


После того, как список задач утверждён, каждую из задач надо подготовить. Подготовка задачи делится на несколько действий.

4. Написание условия.

Условие задачи должно быть максимально понятно и в нём не должно быть косяков. В общем-то, это всё. Если условие разрастается — это, конечно, не очень хорошо, но лучше пусть оно будет кристально ясным, чем коротким. В том числе, если для понимая условия будет очень полезна картинка — надо нарисовать картинку. При этом надо помнить, что длина условия тоже влияет на сложность задачи. Поэтому условие задачи A второго дивизиона не может быть слишком длинным.

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

5. Написание разбора.

Разбор — это очень важно. В разборе задачи заключается половина образовательной составляющей контеста. Однако не надо писать разбор так, как Вы бы разбирали для себя. Любую задачу, даже самую простую, надо изложить максимально подробно, понятно и лаконично. Важно помнить, что участники читают то, что Вы написали, но не могут знать, что Вы при этом думали.

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

И снова насчёт картинок: если в разборе нужна картинка, то нарисуйте картинку.

Вы должны написать разбор на обоих языках.

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

6. Написание чекера.

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

В самых тривиальных случаях надо просто проверить, что ответ, который выдало решение участника, такой же, какой выдаёт авторское решение. На это есть стандартные чекеры, которые делают это в разных случаях: для YES/NO, для одного числа, для последовательности чисел, для строчек, и так далее.

Во многих случаях есть множество правильных ответов. В таком случае чекер должен прочитать ответ участника, тест и ответ авторского решения, после чего проверить правильность ответа. Проверка может быть самой разной, в зависимости от задачи, и при этом быть очень сложной. В задаче 333C - Счастливые билеты, например, чекер был раз в 10 сложнее, чем решение.

При написании чекера используется testlib. Это простая и удобная библиотека для написания чекеров, валидаторов и генераторов. Если Вы не знакомы с testlib, то не переживайте, Gerald Вас познакомит.

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

7. Написание валидатора.

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

8. Написание решений.

Да-да. Решений. Не одного, а многих.

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

И есть множество причин написать другие решения.

Во-первых, должно быть решение и на C++, и java.

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

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

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

В-пятых, если есть какие-то альтернативные решения, стоит их тоже написать, чтобы понимать, будут ли они работать. Обязательно проверьте, что Ваша сложная задача с клёвым решением за O(nlog(n)) не решается втупую за O(n2) с битовой оптимизацией.

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

9. Написание тестов.

Тесты делятся на три части.

Тесты из условия служат для лучшего понимания условия. Это маленькие и как можно более простые по структуре тесты, на которых участник может понять, что происходит. 1-3 штуки.

Претесты проверяют, что участник не пытается протолкнуть какую-нибудь лажу и вообще правильно понял условие. Это несколько (в районе 7) простых тестов. Там могут быть крайние случаи, особые случаи, для некоторых задач — макстест, и тому подобное.

Основные тесты проверяют правильнось решения. Здесь надо учесть всё. Крайние значения всех параметров, тест на максимальное время выполнения и максимальное расходование памяти (это могут быть разные тесты для разных решений), тест на максимальный/минимальный ответ. Тест на переполнение. Самые разные по структуре тесты. Тесты, которые обрушат все написанные Вами неверные решения. Бывает, что нахождение всех этих тестов требует недюжинных размышлений, особенно для сложных решений.

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

По возможности, надо не допустить того, чтобы задача решалась оптимизированным брутфорсом.

10. Написание анонса.

В принципе, в анонсе надо объявить, что будет раунд, кто автор(ы) и какая разбалловка; а так же поблагодарить всех, кто Вам помог, включая Gerald и переводчика. Остальные плюшки — по желанию: рассказать о себе, пошутить, рассказать о сквозном персонаже, добавить прикольную картинку, посоветовать прочитать условия ВСЕХ задач...

Анонс тоже придётся на обоих языках написать Вам, но это как раз несложно участнику даже с самым минимальным уровнем владения языком.

11. Проведение раунда

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

Во время самого раунда надо быть онлайн и вместе с Gerald следить за ходом раунда и отвечать на вопросы участников по задачам. Кроме того, бывает, что надо поправить условие на контесте (это ай-ай-ай, невнимательность и спешка при подготовке, но бывает) или (мало ли) поправить ещё что-то (это совсем ай-ай-ай, у меня такого не случалось, насколько я помню). После контеста надо опубликовать разбор и поздравить победителей. Кроме того, желательно отвечать на вопросы в комментариях к анонсу.

Эпилог.

Надеюсь, мой путеводитель подтолкнёт Вас к тому, чтобы приготовить нам новые интересные раунды =)

Всё вышеперечисленное — это очень интересно (кроме написания валидатора). Если у Вас получится придумать задачи — смело пишите Gerald. Но надо понимать, что это довольно большой труд. У меня лично уходит на один раунд (после согласования задач) примерно две недели. Это не будет сложно, поскольку будет интересно. Но времени отнимет много, это да. Ну и огромная прибавка в карму, и чем качественнее и интереснее раунд, тем больше прибавка.

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

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

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

"После того, как Вы собрали свой проблемсет, надо просто обратиться к нему любым образом"

Обратится то можно, но не факт что он ответит

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

    Ну, я лишь описываю свой опыт. Мне всегда отвечал.

    А что, Вас он игнорирует?

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

      Ну игнорирует громко сказано. Просто есть несколько знакомых, зелено-синего цвета, которым он не ответил...но честно говоря, может это и к лучшему.

      Вы просто так все красиво описали, что сейчас публика моего типажа начнет ему писать по поводу контеста, питаться придумывать какие-то задачи, не обязательно хорошие, а Геральду на это все отвечать? Думаю, что он этим заниматься не будет. Тем более кому нужен контест от человека, который сам не в состоянии решить С (див2), Д (див2), не говоря уже про Е (див.2)

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

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

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

        Вообще, иногда он просто забывает, и ему можно напомнить

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

          Алексей говорит правду, я, бывает, в куче писем могу потерять/забыть/удалить письмо человека. Особенно, если обсуждение у нас было длительное и не очень динамичное, смело пишите мне в Hangouts или VK, я часто могу ответить.

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

Спасибо за ободрение, а то три года назад общение так и не завязалось.

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

Спасибо огромное за просвещение

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

А как там с интеллектуальной собственностью?

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

    Ну, если ты засветил задачу координатору, но она никуда не пошла, то задача остается в твоем безраздельном владении. Если Вы об этом.

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

it's been nearly 2 days. can someone please translate the Russian post into English?
i'm using Google Translate, but there are many grammar mistakes and it's frustrating to read when the post is as long as this one.

EDIT: English translation now available! thanks :)

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

    Be sure, the author is working on the translation! However of course he can be bit busy (either preparing new contest, passing exams or something other) and the post is lengthy enough so, please, have a bit patience!

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

    You are welcome!

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

Excellent article!

Анонс is translated as announcement, not annouce — I wonder where that mistake came from, since it's something we see frequently on the main page...

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

Напишу про то, как я готовил свой раунд (№169 для второго дивизиона). На пост у меня букв не хватит, да и незачем при наличии двух готовых постов, поэтому ограничусь комментарием.

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

Подготовка раунда — довольно непростой процесс, особенно если первый раз используешь Polygon и testlib. Однако научится этому всему практически самостоятельно — вполне реально, даже человеку без особого опыта в программировании.

О том, на когда запланирован мой раунд, я узнал примерно за 2 часа до его старта :) Мы были на Харьковской зимней школе, ко мне подошел Gerald и сказал, что надо бы написать анонс :) Я был крайне удивлен, но Gerald сказал, что он все проверил, поисправлял что надо и что все ок :)

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

Кстати, а правда ли, что авторы раундов получают футболочки от CF?

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

    Футболки авторам мы перестали рассылать, это очень хлопотно. Но обычно я стараюсь лично пожать руку и выдать футболку при встрече (футболка выдается один раз). Например, на сборы в Петрозаводск, на финал ACM-ICPC или другие мероприятия я часто приезжаю не с пустыми руками :-)

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

      Можно мне одну?... :D

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

      Пользуясь случаем, напомню, что команда авторов раунда 212 с нетерпением ждет футболок :) Кстати, чтобы их вручить, даже не нужно ехать в Петрозаводск/Екатеринбург либо прибегать к услугам почты России :)

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

Good article,I think this should be put in the FAQ.

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

The most frequent way I invent problems is when I misunderstand a problem statement. lol

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

The most frequent way I invent problems is when I misunderstand a problem statement. lol

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

Who is eligible to set a codeforces round?

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

    As far as I understand the author of this post — there are no limitations. I.e. as soon as you have about 5 problems at hand and you think they could be nice for contest — you can write to Gerald and ask his opinion on them.

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

This statement I don't understand it it is the first time to do that so that I will be so happy if you helped me :) PackageException: There exists an output where checker crashes, output description is "Single line containing 1000000 random characters". Expected checker exit code 0, 1, 2 or 7, but -1073741676 found.

what is this ?! and thanks in advance ;)

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

    This blogpost is not the right place to ask such questions, isn't it?

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

      Sorry about that but it's the first time to use the checker I thought that any one could help me but I just found they down vote for me I didn't ask any one to vote I asked for help but I did't found any of that. I thank you very much for replying to my question and sorry for all if I have bothered you :(

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

    It means exactly what it says. The checker breaks for some input. You can download your checker locally and run it for some random garbage inputs (like "single line containing 1e6 random characters"). My guess is you don't use testlib.h and instead you use scanfs or asserts.

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

      The problem that faced me that I try to understand the documention of that library.so I want to know could be such a way to understand that library or using something else I will be great full for you as I want to be good problem setter and thank you for replying my question

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

I think skill of problem setting will definitely help to improve the skill of problem solving . thanks a lot for the post . :-)

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

I think we can't go through step 3 these days.

Last visit: 4 months ago

Sorry but there is no Gerald.