Процесс творения раунда без прикрас и страшилок.
Путеводитель по творению раунда от автора четырёх 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(n²) с битовой оптимизацией.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эпилог.

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

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

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