Предисловие: Мне этот раунд очень напомнил раунд Сергея Ведерникова с отличными задачами и ужастным контестом.

А теперь по сути.

Да, меня этот момент тоже смутил. К счастью, на КФ можно задать вопросы. К несчастью, как я понял, авторы раньше не давали раундов на КФ и не знали того, что мне практически в начале моего раунда сказал Артем Рахов — мы стараемся не отвечать "без комментариев". Так что получив "БК", я пробормотал пару нелестных вещей в адрес авторов и продолжил думать — уже через 3 минуты я получил более-менее нормальный ответ. Так что разобраться конкретно с этой проблемой было можно. Как, в общем, и с люыбым другим вопросом по условию, и это замечательно.

Меня смутил больше другой момент. Как минимум для одного из авторов русский язык вроде бы родной.. А в условии формулировка про "отрезок СД" что до, что после правки оставляет много непоняток, тесты из условия не полностью помогают, так как в первом тесте всегда выбирается один и тот же отрезок СД, в условии несколько раз фигурирует величина С и с в разных смыслах, не сразу ясно из условия, что хотя даны вероятности, каждая из них от 0 до 100, а вовсе не сумма, и т.д. То есть я не могу сказать, что условия (особенно после правки) были некорректны, но.. Судоку тоже можно иногда решит без перебора, последовательно анализируя, что у нас есть — так и с этими условиями, из них все можно вывести, но не сразу. Я не берусь утверждать, но мне кажется, что авторы не очень часто давали раньше задачи, и попали в ловушку, в которую часто все попадаються — "я знаю, что надо сделать и я знаю, как это сделать — значит условие ясно, а задача легкая". Вот и получился раунд, в котором А Б С Д должны были быть Б С Д Е...

On the brighter side of things, хочу заметить, что это один из лучших проблемсетов — задачи достаточно оригинальны, в них нужно приложить очень неплохо думалку, особенно порадовала задача Б. Даже стандартное дерево отрезков подали так, что многие его не очень то и порешали. (Хотя, может это с другим связано).

Интерестно было бы послушать и другие мнения.

Возможно автор поста хотел услышать и не мое мнение, но я все-таки отвечу) Контесты подобные codeforces round хороши тем что в них вы не получаете никакой прямой выгоды от результата, это не всерос где на кону стоит диплом, дающий президентскую премию и поступление, и не раунд TCO с призом — поездкой в штаты. В такой ситуации контест вполне может содержать некий образовательный момент. Это и был один из них, мы намеренно не стали оговаривать это в условии, предоставив участникам самим подумать об этом случае (а ведь о нем еще надо вспомнить) и разобрать его. Может быть то, что Вы теперь имеете большее представление о пустых множествах и вообще понимаете что подобные случаи в задачах могут быть, ценнее 10 места div 2 codeforces round #107?

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

Зато могу посоветовать пару соображений и упражнений с пустыми множествами для перехода от "бытовой" логики к "формальной".

Если какая-то функция F (например, сумма, максимум, произведение) определяется на множествах (последовательностях, наборах), удобно было бы определить её естественным образом для любого множества. Иначе каждый раз придётся разбирать случаи, и для сложных объектов их количество будет очень быстро расти. А естественность значит, что для непересекающихся A и B хочется получить функцию от объединения равной этой же функции, применённой к значениям на A и B по отдельности: . Скажем, для суммы хочется SUM({2, 3, 4, 5}) = SUM({2, 3}) + SUM({4, 5}), для максимума max({2, 3, 4, 5}) = max(max ({2, 3}), max({4, 5})), и так далее. Подставим . Значит, для естественности нужно .

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

Упражнение 1: чему равно произведение пустого множества чисел, и почему? (ответ: 1)

Упражнение 2 (стащено у Дмитрия Павлова): определим башню степеней от последовательности:

(вычисляется "сверху вниз": сначала $a[n - 1]$ возводится в степень a[n], затем a[n - 2] возводится в степень — результат предыдущего шага, и так далее). Чему равно ?

Ещё можно прочитать пространную статью в Википедии (на английском) об утверждениях о пустом множестве.

Речь, я полагаю, идет о случае k > n в 150B - Количество строк? Ну... небольшая подстава, да, бывает такое в задачах ;) В принципе, не фанат подобного, но простой подход — разбирая случаи, разбирай их все.

Гораздо больше "не в традициях жанра" в задаче для второго дивизиона не объяснить, что же такое "строка над алфавитом". И речь даже не о том, что кто-то это может просто не знать.

Вот, например, Билл Смит. Его определение строки ("Computing patterns in strings"), данное в самом начале, допускает бесконечные строки, циклические строки и прочие прелести жизни. То, что понималось в условии, он называет "linear string" (причем не допуская при этом в определении пустую строку). Для циклических строк верны все примеры. Для циклических строк, например, ответ при k > n зависит от определения понятия "подстрока".

GlebsHP Благодарю за критику, действительно, выиграть не главное, и цель моя — обучение. Но тут собака и зарыта. Я ведь придумал решение задачи. Относительно быстро, что весьма обрадовало. А сдать не смог. Вот почему обидно. Однако своего я добился, узнав с помощью этого поста много интересных мнений.

Отдельное спасибо Gassa, за развернутое докладное объяснение, благодарю еще раз, обязательно изучу.

Alias — именно это я и имел ввиду: "явным указанием того, что ожидается увидеть в данном случае."

Спасибо еще раз всем, кто не прошел мимо. Этот тур действительно добавил очередное знание в мою копилку, и, разумеется не без вашей помощи =)