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

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

Тема подготовки задач для контестов, конечно, не так популярна, как извечный вопрос "как стать красным за три месяца", но все-таки вызывает некоторый интерес публики. Я уже писала про особенности подготовки Surprise Language Round и про эмоциональный аспект авторства задач; пора поделиться суровыми фактами о подготовке самых обычных контестов.

Задачи

Сколько времени у вас уходит на то чтобы подготовить, выбрать, вспомнить или подыскать сами идеи задач — происходит ли это в течение дня-двух, или они постепенно рождаются недельку-месяц а потом вы начинаете думать "не применить ли их в контесте?"

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

Генерация идей — процесс долгий, практически непрерывный. Когда я придумывала задачи, я все время генерировала идеи из чего попало (о, белка побежала... хмм, а это идея! — честное слово, задача до сих пор лежит, сложная :-) ) и конспектировала их. Когда у меня было время и настроение написать контест, я перетряхивала эти конспекты в поисках задач, которые были бы 1) решаемы, и 2) симпатичны и достаточно нестандартны, и собирала из них сет. Минус такого подхода — я совершенно не умею придумывать задачи для обычных раундов по принципу "здесь нужна задача на строки", я могу только пойти от придуманной легенды и решить ее, но не наоборот.

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

В моих первых 4 контестах (TC High School — задачи для школьников чуть проще, чем Див2) задачи на 1000пт были на поиск в ширину, с бантиком типа геометрии или неквадратного лабиринта — это было нормально для школьного уровня образца 2007 года, но скучно для полноценных Див2 контестов образца 2014 :-) Что же касается Див1 задач, то за все годы моей карьеры как автора я довела до контеста ровно четрые задачи, которые были сложнее тех, что я могу решить как участник: два Див1 Hard'а на TC (1, 2) и Див1 132D - Константы на языке Шекспира и 132E - Биты старой Англии на CF. Из них одна была на геометрию + графы (т.е. суровая реализация), остальные три мне помогли решить красные. Были и задачи "попроще", в которых тестеры ломали мое авторское решение (и не всегда я понимала, как именно), приходилось считать reference solution их вариант — например в 345E - Атака черных кошек мое решение из чисто геометрических соображений оказалось неправильным, пришлось использовать тернарный поиск. А сколько задач были забракованы более опытными координаторами/соавторами как стандартные/скучные, хотя лично для меня они были сложными и новыми... А сколько так и осталось в черновиках, потому что я так и не придумала, как они решаются... В общем, не скажу за всех желтых/фиолетовых, но лично мне для написания Див1 раунда нужна помощь более красных товарищей.

Сколько сил (в человеко-часах) у вас лично отнимает подготовка раунда?

Много. Как известно, задача = идея + условие + решение + инфраструктура (чекер, валидатор тестов, генератор тестов, специальные ручные тесты). И если идея может родиться за 60 секунд, то все остальное занимает время, много времени, и чем сложнее задача, тем больше. Даже для развлекательных задач с совершенно очевидным решением на пару строк и стандартными тестами (несколько чисел из определенных диапазонов или строка из определенных символов — в общем, никаких затейливых ограничений) от создания задачи в Полигоне до сабмита первого варианта проходит не меньше часа. Немного выручает переиспользование инфраструктуры из старых задач с похожими тестами (а иногда и самих задач, если в этот раз они будут решаться на другом языке, хотя это неспортивно). В общей сложности на контест уходит от 3-4 дней (если контест простой, а дни выходные) и до нескольких недель (если писать урывками контест посложнее). Последние пару дней перед контестом приходится засиживаться не то что заполночь, а и часов до 3-4 утра — подготовка задач всегда занимает больше времени, чем запланировано.

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

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

Подсказка: TC Арена не позволяет вводить в тестах строки длинее 50 символов.

Ответ: "board will contain between 1 and 50 elements, inclusive." + "Element i of board will contain exactly 2*i+1 characters." означает, что в максимальном тесте будет 50 строк, и в 50-ой строке будет 99 символов — а такой тест невозможно ввести в Арене для челленджа. Увы, в этом матче челлендж-фаза проходила без макстеста — очень неловко получилось.

Люди

Как вы общаетесь с администрацией CF — сообщениями на сайте, почтой, скайпом или ещё что? Насколько этот процесс быстрый или медленный особенно если разные временные зоны?

Сколько итераций у вас могут пройти задачи прежде чем вы по их идеям достигнете согласия с администрацией и приступите непосредственно к подготовке раунда? Или задачи всегда "нравятся" с первой попытки?

Общаемся почтой и google talk (или как он там теперь называется). Последние полтора года разница часовых поясов между мной и администрацией CF колеблется в районе 11 часов, так что процесс, скажем прямо, небыстрый. Если не брать в расчет контесты вида "я хочу написать Surprise Language Round, настройте компилятор COBOL и дайте мне дату, а дальше я сама", обсуждение задач может занять неделю или больше — особенно для задач посложнее, в которых у меня есть только смутная идея и нет уверенности в том, как же она решается. С другой стороны, примерно за сутки до начала контеста общение становится быстрым и крайне интенсивным — в отличие от TC, в котором за 24 часа до SRM-а наступает lockdown, после которого задачи правятся только в случае крайней необходимости :-)

К кому можно обратиться за помощью если задач не хватает или их качество нехорошо — или тут что-то администрация предлагает подсказывает?

Как выбираются тестеры для задач, как они участвуют в подготовке — например, советуют ли снять задачу, изменить количество баллов по ней и т.п.?

В отличие от TC, где тестеры выбираются из ограниченного пула официально и независимо от автора контеста, на CF кого автор уговорил, тот контест и тестирует (за исключением Gerald). То же самое относится к недостающим задачам — кого уговоришь, тот задачу и придумает. Мне кажется, схеме CF вообще ближе понятие соавтора, чем тестера — соавтор может помочь сформировать список задач, раскритиковать одни идеи и предложить другие, может даже написать основное решение и/или инфраструктуру, если у основного автора не хватает времени (хотя это очень оптимистичый сценарий), ну и все остальное по мелочи само собой. Для сравнения, на TC тестер только читает и критикует условие и пишет тестовое решение, ну максимум добавляет пару тестов. Граничных случаев два — Surprise Language Round-ы я пишу в гордом одиночестве, а в Первоапрельском контесте 2012 года всю техническую подготовку раунда взял на себя maksay (святой человек!), я только придумала концепт контеста и идеи задач и потом просмотрела готовые задачи на их соответствие авторскому видению. Обычно получается все-таки что-то среднее.

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

Да, обязательно. В админском интерфейсе контеста есть вопросы, которые задают участники, и на них надо отвечать. Это что-то вроде автоматической обратной связи: написал плохое условие — будь добр ответить на стотыщ вопросов по нему или срочно правь условие, написал Surprise Language Round — объясняй людям, что сабмитить правда-правда можно только на одном языке, и нет, на C++ нельзя. Ну, а если все хорошо — спокойно пиши эдиториал, чтобы выложить его пораньше (кажется, написать эдиториал заранее у меня не получилось еще ни разу).

Вот так контест выглядит изнутри.

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

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

Спасибо большое за веселые и нетривиальные задания!! До сих пор одним из самых интересных головоломок для меня остаются шуточный апрельский контест и новогодний квест. Надеюсь, будут продолжения :)

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

In response to what you said about maksay I must say http://xkcd.com/541/ . I know its not the most constructive of things to be pointing out but the emoticon-parentheses thing is one of my pet peeves. Also, great article.

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

    Pointing this out is absolutely not constructive, especially since the link doesn't offer a good solution to the problem. However, in this case it is useful, since I never meant to have a smiley there, Russian version of the post doesn't have it. This is fixed :-)

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

As I have no experience on setting contest, would you please tell me what can I do If I have just the problem ideas?