Всем привет!
Последнее время все больше недовольства у участников раундов по поводу их организации или задач. Встречаются проблемы с условиями, слабыми претестами, неправильным распределением сложностей и т.п.
Я предлагаю здесь обсудить, каким должен быть идеальный раунд с точки зрения как авторов, так и участников.
Сам я участвовал в разработке задач как для кфа, и не только. Поэтому в посте приведу немного своих мыслей, возникающих по ходу подготовки контеста. Само собой, этот список нуждается в дополнении, поэтому я бы очень хотел увидеть ваши идеи в комментариях.
Условие
Прежде всего условие должно ясно объяснить участнику, в чем, собственно, суть задачи. Отсюда появляются следующие соображения:
Условие должно быть коротким
Нужно стараться умещать мысль как можно емко и грамотно. Задача участника — написать правильный код и сдать его, а не читать полторы страницы воды. К этому же пункту можно отнести и легенду. Да, действительно, куда приятней решать задачу про персонажей. Однако история в данном случае — лишь украшение, и не должна преобладать над сутью.Условие должно быть понятным
Все введенные термины и примеры должны быть объяснены в разделе Примечания. Не нужно загромождать определением само условие и разъяснять общеизвестные понятия, но, если у участника появился вопрос насчет толкования какого-то примера или термина, ответ на него он должен найти после семплов.Условие должно быть однозначным
В идеале, уже после первого беглого прочтения задачи, должно быть понятно, что требуется, какие есть нюансы и тонкости. В случае, если какая-то фраза является ключевой, ее нужно выделать изменением шрифта или начертания.Условие должно быть структурированным
Под структурой я имею ввиду четкое разделение на части Собственно условие, Формат входных данных, Формат выходных данных, Примеры, Примечания. На codeforces с этим проблем не бывает. Однако очень часто на локальных олимпиадах я встречал ограничения для переменных прям в самом условии, что дико напрягало.
Ограничения
Правильно подобраные ограничения сильно помогают решить задачу. Поэтому из них должна быть понятна требуемая от участников асимптотика. За эти годы сложились традиционные константы, и я не вижу причин не использовать их без особого повода:
- O(n) — 107
- O(n2) — 5000
- O(n3) — 500
- O(nlogn)- 2·105
- 2n — 23
- mod — 109 + 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
Он должен простыми словами на понятном даже не продвинутым в математике людям языке объяснять решения задач. К каждой задаче должен быть приложен пример кода с комментариями.
Еще, приятно, когда разбор появляется сразу после раунда, а не через несколько дней.
Желательно читать комментарии к разбору, отвечать, если кому-то непонятен разбор (часто объяснение другими словами хорошо помогает разобраться).
Пример хорошего разбора на русском, на английском.
--МЕСТО ДЛЯ ВАШИХ ПРЕДЛОЖЕНИЙ--
Ну, из основого, что сейчас у меня на уме, вроде все.
Еще раз повторяю, что паста выше — это мое субъективное видение. Оно может (и должно!) отличаться от вашего. Я создаю этот пост для того, чтобы в одном месте собрать какие-то соображения для будущих авторов(в том числе и для себя:)).
Еще насчет ограничений: ввод не должен быть большим. Желательно не подавать на ввод более 5·105 чисел/строк, чтобы не получилось так, что ввод
cin'.ом дает TL, как, например, вот в этой задаче. Если важно проверить задачу на больших данных, то можно в условии записать формулу для генератора (сейчас задачу не вспомню, но вроде подобное не так давно было на Topcoder).Хорошая идея, спасибо, отразил в посте
Проблема с долгим считыванием cin'ов решается двумя путями:
использованием scanf/printf, ИМХО, они удобнее при решении задач по спортивному программированию, т.к. позволяют считывать гораздо легче некоторые данные; (к примеру для считывании времени в формате hh:mm достаточно написать scanf("%d:%d", &h, &m), а cin'ами придётся извращаться;
в начале кода написать команду sync_with_stdio(0).
С генераторами тяжелее работать, поскольку часто требуется внимательность и не поставленная туда переменная может исказить массив или тому подобное. Кроме того, в некоторых задачах нужны не рандомные, а именно определённые данные (допустим для того, чтобы задачу можно было решить только Декартовом деревом, а не обычным бинарным, необходимо подавать вершины в порядке возрастания\убывания).
Поэтому, по моему мнению, нет особой проблемы, если количество чисел будет больше 5 * 10^5.
На мой взгляд, не очень приятно получать TL из-за того, что ввод-вывод отработал медленно. К тому же, достаточно вспомнить, сколько было гневных комментариев по этому поводу после контеста.
К тому же, не все используют
scanf/printf.cinиcoutзащищают от неправильного указания квалификаторов (к примеру, написал%d, а считываешь вint64_t. К тому же, если локально пишешь на Linux, то придется менять%lldна%I64d.Я согласен с Вами, что неприятно получать TL. Но я тоже прошёл через то, что моё решение падало с вердиктом TL из-за использования cin'ов, когда я только начинал решать задачи на кф. Но если говорить о необходимости сокращения данных лишь из-за того, что некоторые пользователи пользуются cin'ами, то тогда вообще стоит запретить создавать задачи, где требуется знанием определенных алгоритмов или структур данных, поскольку кто-то может не знать такой алгоритм\структуру данных и решать задачу в лоб. Но, по-моему, пропадёт весь интерес к задачам, если будем облегчать их ради того, чтобы пользователи не получали TL.
UPD: Я тоже пишу на Linux, но мне не приходится менять lld на I64d, поскольку есть компилятор C++14, которому всё равно на тип. Кроме того, я сдавал задачи с lld на компиляторах C++5, и они получали Accepted. И, как я уже писал ранее, можно писать всего 1 оператор и работать спокойно cin'ами, не думая о том, что задача получит TL из-за большого количества входных данных.
Тогда давайте вообще делать массивы на 107 чисел и пусть все пишут быстрый ввод-вывод наподобие этого.
А вообще, я к тому, что участник на контесте должен думать над тем, как написать быстрый и качественный алгоритм решения, а не над тем, чем быстро вводить чиселки.
Ввод чисел — одна из частей алгоритма (ибо без чисел нечего считать). Я не стал писать дольше код с использованием scanf\printf, а в некоторых случаях (я уже приводил пример в первом комментарии) код становится понятнее, а времени на написание уменьшается.
Возможно, если бы сервера кф были мощнее и во время соревнования участники не сдавали бы решения по 50 — 100 человек одновременно, то можно было делать тесты с количеством данных 10^7 и больше, но такие тесты генерируются медленнее, валидатор проверяет дольше и памяти требуют много. И, по моему мнению, именно поэтому очень мало задач, где количество чисел не менее 10^7.
Вот, кстати, еще один аргумент против больших тестов :)
Саш, а как тебе аргументы за большие тесты типа этого или этого?. Или этого. Ну здесь еще. И тут.
26661885 AC
26661906 TL 11
Разница лишь в способе ввода/вывода :)
26662047 Может быть, сервер был загружен или прочие факторы, но у меня зашло
Вероятно, C++14 вместо C++11.
Вы — участник. Ваша задача — сделать так, чтобы ваше решение не получило TL. Жертвовать ограничениями задачи ради "комфортного ввода" нецелесообразно, это может ограничить изначальные замыслы авторов и предоставить свободу тем, кто решает задачу неоптимально. Вдобавок, за редкими исключениями, в претестах всегда содержатся максимальные по размеру инпута тесты.
И, уж извините, за квалификаторами
scanfдолжен уметь следить каждый уважающий себя участник. А если бы, например, мы давали свободуScannerв Java, то ограничения пришлось бы урезать еще сильнее, либо повышать TL специально для Java — каждый из этих вариантов в реалиях Codeforces имеет существенные недостатки.И еще раз — не забывайте, что решать задачи оптимально — ваша задача, а оптимальный ввод данных — это часть оптимального решения.
Единственный идеальный раунд на кф — 368.
Еще хотелось бы рассказать подробнее про разбор. Во-первых, желательно читать комментарии к разбору, отвечать, если кому-то непонятен разбор (часто объяснение другими словами помогает). Во-вторых, если решение использует какой-то факт, то нужно доказать этот факт, объяснить, почему решение работает.
Писать комментарии в авторском коде — действительно хорошая идея, но, к сожалению, я еще не видел таких кодов в разборе.
Насчет оформления разбора. Можно включать вместе с основным текстом разбора подсказки, которые лишь немного "подталкивают" к решению задачи. Хорошая идея также прятать разбор под спойлеры, как, например, сделано у меня. Иногда хочется почитать разбор только одной задачи, а над остальными подумать самому.
Еще пример хорошего разбора
Ещё бывает так, что в задаче, на пример, подаётся на вход матрица m*n, а в сэмпле матрица квадратная и по привычке обычно пишешь код для n*m, и как итог получаешь штраф. В идеале нужно указать прямоугольную матрицу в сэмпле, чтобы было понятно, что из чисел обозначает количество строк, а что обозначает количество столбцов.
... или перестать ловить штраф и прочитать формат входных и выходных данных и выяснить в каком порядке пишутся координаты. Лучше прямо во время набора соответствующего кода ввода/вывода. Так еще начнем жаловаться, если нет примеров, из которых ясно, отсчитываются координаты с 0 или с 1, что какое-то число во вводе может быть 0 и это особенный случай и так далее.
В мире (особенно практического) программирования очень много не стандартизовано, RTFM — крайне, крайне полезный навык.
Спасибо, добавил раздел "семплы" в статью
Раз уж на то пошло. Когда я посылал свое первое предложение раунда, мне кинули ссылку вот на этот документ, где хорошо описаны многие моменты, касающиеся подготовки контестов.
Комментарий от Errichto на эту тему.
Ну вот не знаю. Честно говоря, я лично буду бомбить от задач с тегами "кот тапок количество" или от строгой математической формулировки намного больше, чем от того, что мне пришлось прочитать три абзаца воды. Например, когда я вижу задачу о построении пифагоровой тройки и задумываюсь о том, что четное число может быть представлено как 2mn, а нечетное как m^2-n^2=(m-n)(m+n) мне становится скучно, потому что у меня просто спросили, знаю ли я вид пифагоровых троек. Действительно хорошая задача должна иметь последствия, а не быть последствием.
Дальше, по личным впечатлениям, у меня возникает желание просто перестать решать задачу, когда она содержит стандартную бесполезную олимпиадную технику или очевидно обходится сильными методами, но это личное. Олимпиадный профессионализм — данность, но я против, чтобы задачи поощрали его. Даже если задача имеет интересную идею, но при этом достаточно просто
скопипаститьнабить min-cost-max-flow мне становится скучно и я не понимаю, зачем дали такую задачу.Кроме того, я не понимаю, как избавиться полностью от вопроса "зайдет/не зайдет". Ну серьезно, вы должны оставить запас для решения, и над любым
сразу нависает корневая 
, не говоря о квадратах логарифма, и вряд ли вы сможете их отсечь. Требуемая асимптотика не может быть проверена (если вы не затребуете формальное доказательство, конечно).
Еще к каждой задаче автору/тестеру нужно не полениться и написать решения со всеми временными асимптотиками, что приходят в голову(причем полностью оптимизированными, вплоть до написания брутов по типу while(clock()-starting_time <= 1.99*CLOCKS_PER_SEC)) и так же все возможные наивные решения(которые по идеи должны получать WA). Если не писать такие решения, то оптимизированный O(n^3) может пройти при ограничения n <= 5000 или жадина может пройти вместо динамики/mincostmaxflow и т.д.
К сожалению, это в большинстве случаев пустая трата времени. Скорее, нужно детальное изучение задачи, хотя и это часто не работает. Вы должны понимать без реализации, какими методами задача решается, какими не решается и почему.
Например, бруты с указанным типом в задаче бывают только при существенной разнице времени работы в случае "нашлось/не нашлось" и нужно изучать вопрос, почему же так долго рассматривают случай "не нашлось". Очень часто в этом случае есть альтернативные решения и специфические тесты его веток, которые как раз построены против подобных брутов. Если вы — автор задачи, вы, как правило, должны были уже найти это альтернативное решение.
То же самое с наивными решениями — они либо от природы не работают на рандоме (и тогда зачем их писать?), либо работают и тогда задаче светят очень большие проблемы с рандомизированными решениями.
Да, в теории можно перебрать решения в голове и не писать их, но опыт показывает, что в достаточно большом количестве случаев лучше бы все же написать их. Возможно на КФ это не так актуально, потому что есть взломы, но на ресурсах, которые дают сразу полный фидбек по результату задачи, это актуально.
Проблема не в том, чтобы написать некоторое конкретное решение, это легко. Проблема в том, что вы просто не знаете, что на самом деле надо было оптимизировать в переборе или в наивном решении.
Для примера, вот задача (Окружной этап Всероссийской олимпиады школьников по информатике, Самара 2013, гроб II тура). Задан неориентированный граф. Нужно найти в нем цикл (разрешены повторы вершин и ребер), посещающий каждую вершину нечетное число раз (обратите внимание, что ноль четное число). Цикл не обязательно кратчайший, но не должен быть длиннее, чем 10·n + 42, где n — число вершин. Ограничения 100 вершин, 1000 ребер.
Вот интересно, как по-вашему я должен оптимизировать перебор, чтобы он зашел? :)
Некоторые высказанные тезисы выглядят неоднозначно. Все-таки речь идет о соревнованиях, а не об учебных раундах.
Допустим, в задачах А (возможно, B) div 2 действительно стоит "опекать" начинающих, чтобы они писали правильные вещи и сохраняли мотивацию для дальнейшего участия. Но непрозрачные намеки для более опытных представляются излишними: кажется, нет ничего плохого в подходе "у нас есть авторское решение за квадрат, за куб мы ничего хорошего не придумали, но почему бы не предоставить возможность участникам попробовать это сделать".
Т.е., по сути, гарантировать, что прохождение претестов приведет к прохождению всех тестов? Опять же, более-менее опытный участник должен уметь тестировать свои решения.
Ну не сочетается "беглое прочтение" с "нюансами и тонкостями". Опять же, если речь идет о задачах A div 2 — да, наверное, там лучше вообще без тонкостей. Но условия задач нужно уметь читать. Если однократное внимательное прочтение с самостоятельным разбором сэмплов приводит к однозначному (и правильному) пониманию — с задачей все хорошо.
Понятно, конечно, что если условия будут содержать сугубо формальную постановку задачи с намеками на нужные структуры данных / алгоритмы, а претесты нельзя будет пройти, не написав правильного решения — то шансы сдать задачу повышаются. Вот только умения решать задачи (которое, наверное, и есть наиболее ценный навык, приобретаемый участником) это не прибавит.
Задача Сdiv2/Adiv1 — ключевая задача раунда.
Не могу согласиться, по крайней мере, с Adiv1. Конечно, если зафейлить при подготовке или оценке сложности задачу Adiv1 — все пойдет насмарку практически гарантированно, участники бросят писать раунд и так далее... но называть самую легкую задачу раунда ключевой неправильно.
Если уж и разделять задачи на ключевые и не ключевые, то ключевой я буду считать ту, которая содержит определенную идею и обычно требует определенных усилий для решения — ну сами подумайте — предлагая другу вспомнить раунд, вы скорее будете описывать задачу, над которой больше думали (при этом вы могли как сдать ее, так и не сдать, но все же получили определенное удовольствие от ее решения). Задача Adiv1 такой задачей, даже следуя вашему описанию, быть не может.