Всем привет!

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

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

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

Условие

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

• Условие должно быть коротким
  Нужно стараться умещать мысль как можно емко и грамотно. Задача участника — написать правильный код и сдать его, а не читать полторы страницы воды. К этому же пункту можно отнести и легенду. Да, действительно, куда приятней решать задачу про персонажей. Однако история в данном случае — лишь украшение, и не должна преобладать над сутью.

• Условие должно быть понятным
  Все введенные термины и примеры должны быть объяснены в разделе Примечания. Не нужно загромождать определением само условие и разъяснять общеизвестные понятия, но, если у участника появился вопрос насчет толкования какого-то примера или термина, ответ на него он должен найти после семплов.

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

• Условие должно быть структурированным
  Под структурой я имею ввиду четкое разделение на части Собственно условие, Формат входных данных, Формат выходных данных, Примеры, Примечания. На codeforces с этим проблем не бывает. Однако очень часто на локальных олимпиадах я встречал ограничения для переменных прям в самом условии, что дико напрягало.

Ограничения

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

• O(n) — 10⁷
• O(n²) — 5000
• O(n³) — 500
• O(nlogn)- 2·10⁵
• 2ⁿ — 23
• mod — 10⁹ + 7
• и т. д.

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

Отдельно стоит упомянуть объем вводимых данных. Он должен быть доступным для считывания через потоки cin/cout.

Семплы

Их должно быть не меньше двух. К каждому нужно объяснение в разделе "Примечания".

Каждый семпл должен быть максимально информативным. Графы на одной-двух вершинах вряд ли помогут лучше понять условие и протестировать свои идеи.

Если по условию задачи ответ предполагает вывод строковых констант ("YES", "NO", и т.п) или варианта с невозможностью ответа (-1, или что-то подобное), необходимо предоставлять по одному на каждый из вариантов.

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

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

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

Претесты и взломы

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

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

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

Сложность задач

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

В идеале, количество участников, решивших задачу должно быть пропорционально объявленной до начала разбалловке.

Так же не стоит переграбливать контест. В моем понимании, "зеленые" должны спокойно решать A, B из div2, "синие" — A, B, C div2, "фиолетовые" — A, B div1, "желтые" — A, B, C div1, "красные" — A, B, C, D div1. В общем и целом, должна быть примерная корреляция между рейтингом среднестатистического участника и количеством решенных им задач.

Задача С

Задача Сdiv2/Adiv1 — ключевая задача раунда. По ней строится впечатление основной массы участников. Почему? На это есть несколько причин.

• Во-первых, эта задача отделяет "слабых" участников от "средних" во втором дивизионе. Если эта задача слишком сложная, увеличивается разрыв между уровнем решивших и не решивших, что не круто.

• Во-вторых, она определяет количество участников, пишущих 1 дивизион. Это первая задача, и, если она сложная, то бОльшая часть участников не решит ее в первые полчаса (ну и понятно, что в рейтинговых раундах, если участник ничего не решил в первые 30-40 минут, ему нет смысла что-то посылать вообще). Другими словами, недостаточно сильные участники первого дивизиона не имеют возможности написать раунд и получить плюс вообще.

Таким образом, Cdiv2/Adiv1 — это своеобразное `лицо' контеста и наибольшее внимание при подготовке нужно уделять ей.

Тематика задач

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

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

Также, нужно понимать, что тема должна соответствовать уровню участников, на которых направлена конкретная задача, и не давать, к примеру, графы в Adiv2 или ретроанализ в Cdiv2/Adiv1.

Разбор

Думаю, не нужно говорить о необходимости хорошего разбора:D

Он должен простыми словами на понятном даже не продвинутым в математике людям языке объяснять решения задач. К каждой задаче должен быть приложен пример кода с комментариями.

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

Желательно читать комментарии к разбору, отвечать, если кому-то непонятен разбор (часто объяснение другими словами хорошо помогает разобраться).

Пример хорошего разбора на русском, на английском.

--МЕСТО ДЛЯ ВАШИХ ПРЕДЛОЖЕНИЙ--

Ну, из основого, что сейчас у меня на уме, вроде все.

Еще раз повторяю, что паста выше — это мое субъективное видение. Оно может (и должно!) отличаться от вашего. Я создаю этот пост для того, чтобы в одном месте собрать какие-то соображения для будущих авторов(в том числе и для себя:)).

Столкнулся с такой проблемой при подготовке задачи с подгруппами:

При стресс-тесте решений валидатор полигона по умолчанию валидирует по ограничениям нулевой группы. Из-за этого стресс падает на первом же тесте с ошибкой от валидатора.

Подскажите пожалуйста, как можно указать группу, в которой работает генератор?

Поиск по записям codeforces не дал успехов, а в мануале полигона вообще нет ни слова про раздел Stresses.

Заранее спасибо.

Спасибо всем, кто написал раунд. Надеюсь, задачки вам понравились.

A — Фотографии Брейна

Нужно сделать ровно то, что написано в задачке: считать все символы, и, если есть хоть один из набора {C, M, Y} вывести "#Color" иначе — "#Black&White"

B — Пекарня

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

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

C — Пифагоровы тройки

Пожалуй, самая интересная задачка этого раунда.

Формализуем задачку:

Дано число a. Найти такие два числа b и c, чтобы выполнялось одно из следующих двух равенств:

a² = b² + c² или a² = abs(b² - c²)

Давайте разберемся, когда ответ найти невозможно.

Если а = 1. Доказательство:

1 = b² + c² — невозможно

1 = abs(b² - c²) — невозможно, т. к. не существует таких двух квадратов чисел, что разница между ними равна 1.

Если a = 2. Доказательство:

4 = b² + c² — невозможно.

4 = abs(b² - c²) — невозможно, т. к. минимальная разность квадратов двух чисел, больших единицы равна 5.

Теперь решение для остальных чисел:

Если а — нечетное:

b = a² / 2, c = a² / 2 + 1, где " / " — целочисленное деление.

Тогда c² - b² = (c - b) * (c + b) = (1) * (a²) = a².

Если a — четное:

Поделим а на 2. Тогда получится либо нечетное число, в таком случае, решаем задачку для (a / 2), а потом домножаем b и c на два:

b = (a² / 4) * 2, c = (a² / 4 + 1) * 2, где " / " — целочисленное деление.

Либо получится опять четное число. В этом случае исходное число а кратно четырем. И для решения используем известную Пифагорову тройку {3, 4, 5}:

b = 3 * (a / 4)

c = 5 * (a / 4)

D — Персистентный шкаф

Решение №1:

Заметим, что данные подаются все и сразу(offline). Тогда мы можем построить дерево версий, потом запустить DFS из корня и честно обрабатывать каждый запрос при переходе из вершины в вершину.

Решение №2:

Заметим, что Алина не использует операции, которые относятся к столбцам. Мы можем завести массив версий полок, а каждую версию шкафа представлять в виде массива индексов соответствующих полок и явно её хранить. Тогда при операции, как-то изменяющей шкаф, создается новая версия полки, которая была изменена, индекс этой версии записывается на позицию прежней полки. Этот подход избавляет решение от использование лишней памяти для хранения ненужной информации.

E — Гирлянды

Давайте обрабатывать каждый запрос следующим образом:

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

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

Всем привет!

20 августа в 16:05 MSK состоится рейтинговый раунд Codeforces #368 для участников из второго дивизиона.

Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

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

Спасибо координаторам danilka.pro и GlebsHP за помощь в подготовке контеста, vovuh за прорешивание, Roms за вычитывание условий, а также MikeMirzayanov за платформы Codeforces и Polygon.

Удачи!

UPD1: 500-1000-1500-2000-2500

UPD2: Поздравляем победителей!

Div. 2:

1. Philipsweng
2. ACCE12138
3. lastans
4. fastcoder
5. bblss135
6. YxuanwKeith
7. chenjiamin

Div. 1:

1. ksun48
2. MrDindows
3. dreamoon_love_AA
4. uwi
5. wangyisong1996
6. matthew99
7. irkstepanov

UPD3: Разбор