MikhailRubinchik.ru's blog

By MikhailRubinchik.ru, 5 years ago, In Russian,

Данный пост — третий в серии постов о квалификационном туре — посвящён задачам и правилам. Начните с чтения первого и второго постов.

1. Подготовка задач. Как сделать задачи и для тех, кто не умеет программировать, и для Dandelion?

Вообще-то такие задачи делать не нужно! На квалификационном туре совершенно нормально иметь десяток тоталов. Лишь бы всем не прошедшим командам было далеко до тотала. В нашем же случае я был не только автором задач, но ещё и тренером, поэтому мне хотелось, чтобы команде Dandelion было чем заняться в последние три с половиной часа контеста. Самое сложное в подготовке квалификации — это подготовить самые простые задачи. Обычно на соревнованиях авторам задач нужно развести слабых и сильных программистов, а также слабых программистов и тех, кто не умеет программировать вообще. На квалификации же вам нужно развести тех, кто не умеет программировать, и тех, кто не умеет программировать.

Я несколько утрирую. Вообще-то написать программу типа A+B способны все участники (а если вдруг кто-то не способен, вам нужно их научить этому во время пробного тура). Но куча народу (в нашем случае — большинство) не будут иметь никакого опыта олимпиад. Они будут долго читать условия задач, потом долго их пытаться понять. Потом попытаются написать какие-то решения (возможно, не на те задачи, на которые нужно), потом увидят, что их программа не работает, и не будут знать, что делать дальше.

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

Подготовьте штуки три задачи, в которых решение состоит из пяти строк, не содержит циклов и массивов, даблов на выходе (не все умеют выводить числа с нужной точностью!), long long’ов. На входе должны быть либо только целые числа, причём лучше каждое в отдельной строке (есть паскалисты, знающие ReadLn и не знающие Read, а есть шарписты, не знающие метода Parse), либо строка c ровно одним(!) токеном.

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

Есть ещё одна категория людей, о которых хочется сказать отдельно. Это те, кто хорошо программирует, но совсем не умеет придумывать математические/алгоритмические (не обязательно даже олимпиадные) задачи. Для них обязательно должна быть хотя бы одна средняя техника (на 100 строк кода), в которой всё, что нужно сделать, написано в условии. Она должна быть совершенно топорной, никаких корней или логарифмов в асимптотике алгоритма (это касается даже сортировки) — только чистые полиномы. У вас должно быть авторское решение за полином самой большой степени, который вы только сможете придумать. Вы должны написать это решение на джаве/питоне/шарпе. Обязательно используйте в нём побольше динамической памяти (например, вместо всех массивов используйте ArrayList’ы). И даже такое решение должно заходить с 10-кратным запасом. У нас такую роль выполняла задача D. Она была 7-й по сдаваемости, но при этом её решила команда с 280-го места, которая решила всего 3 задачи.

UPD: 1.1 Дополнительно про задачи

Олег Христенко в комментариях сказал ещё о важных вещах.

1)Задачи нужно делать на русском. Изначально хотели английский, но несколько площадок нам написали, что очень бы хотели русский, поэтому перешли на русский. Т.е. давать задачи на родном языке сильно снижает планку. Сложность здесь возникнет в кволах западного чф. Придётся давать на целых четырёх пяти разных языках? Но я думаю, что они придумают что-то, может быть и правда так сделают.

2)Халявы должны быть по краям. Тут всё не совсем строго конечно. Но самая простая задача должна быть А. А дальше в каком-то порядке В, С, и последняя задача (некоторые читают с конца). У нас были А, В — очень простые. Дальше С, дальше К.

2. Правила отбора

Вам нужно будет придумать правила отбора с квалификации. Как всегда, в правилах должны соседствовать два принципа: географический и спортивный. С одной стороны хочется, чтобы на основном туре были представлены все вузы/города/регионы. С другой стороны хочется, чтобы приехало максимальное число сильных команд, а все участники основного тура были способны что-то решить и на нём. Если забивать на слабые регионы, то АСМ там никогда не разовьётся. Если звать мало сильных, то команда, которая потенциально способна пройти на полуфинал, может не выйти в основной тур четвертьфинала в случае случайного слива квалификации.

Правила, по которым мы отбирали команды с квалификации на основной тур, можно найти здесь: http://acm.urfu.ru/qf/2015/qual/selection.html. На следующий год я бы внёс в них следующие изменения (а что сделают орги следующего года — увидим):

1)Хочется фиксированные квоты заменить диапазонами. Например, диапазон “от 10 до 20” означает, что проходит 10 команд и все, кто решил столько же, сколько 10-я команда, но не больше 20 в сумме.

2)Хочется вообще убрать вайлдкарды и добавить вместо них правила, что после распределения мест по первым трём пунктам вуз получает +1 место на основном туре за каждые 15 выставленных команд, а вуз-организатор площадки получает +1 место за каждые 30 команд на площадке (тут нужно ещё определиться, считать ли команды дважды). Эти правила могли бы мотивировать вузы на местах заниматься пиаром. Константы конечно тут могут быть разные

3. Лирическое отступление о правилах

Многие правила написаны так, что их можно трактовать как угодно. Различные трактовки могут привести к столкновению интересов разных людей и к жалобам в вышестоящие инстанции. У меня сложилось мнение, что позиция руководства ACM ICPC (и в Бэйлоре, и в ИТМО) по поводу разрешения конфликтных ситуаций следующая: пока на местах стороны конфликта ещё способны сами друг с другом договориться, не нужно вмешиваться. Стороны — это, например, участники и тренеры, организаторы ЧФа и тренеры, организаторы разных ЧФов. То есть руководство готово вмешиваться только в том случае, если уладить все вопросы самостоятельно не удалось.

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

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

4. Замены

В правилах на Бэйлоре написано, что если участник отказывается от участия в финале, то получает пожизненную дисквалификацию. В отдельных ситуациях дисквалификацию на год-два может получить и целый вуз. Но там не сказано, что делать, если такая ситуация произошла на полуфинале. Как не сказано это и в правилах NEERC.

Сразу после окончания квалификации к нам начали поступать просьбы о заменах по причине того, что тот или иной участник не хочет ехать на основной тур (или тренер не хочет, чтобы он ехал). Сначала мы отвечали на все такие просьбы отрицательно. Потом мы сформулировали свою позицию в правилах http://acm.urfu.ru/qf/2015/changes.html .

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

5. Новые вузы

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

1)Есть правило, озвученное руководством NEERC, по которому новый вуз вправе сам выбирать четвертьфинал, в котором будет участвовать.

2)Другие четвертьфиналы (в данном случае Южный, Центральный и Западно-Сибирский) плохо занимаются пиаром, и мы считали, что сможем с помощью квалификационного тура сделать это лучше

3)Мы не собирались “навсегда” забирать новые вузы в свой регион. Этот шаг рассматривался в первую очередь как способ ввести вуз в АСМ-сообщество. Мы были бы не против в дальнейшем передать этот вуз в положенный ему по региональному делению четвертьфинал (как например, произошло в этом году с Белгородским университетом).

Некоторые представители Центрального и Южного четвертьфиналов очень любят рассказывать о том, что у них нет АСМ-щиков-любителей. Может, это и так, но зато мы теперь знаем, что в Омском педагогическом университете они точно есть. Уже на основном туре четвертьфинала мы рассказали их тренеру о том, что в Новосибирске есть свой четвертьфинал, в котором у команды ОмГПУ будут выше шансы на выход в полуфинал. Она ответила, что они подумают, какой из двух четвертьфиналов выбрать на следующий год.

6. Спорные регионы.

Ссылки http://neerc.ifmo.ru/subregions/west-siberian.html и http://neerc.ifmo.ru/subregions/eastern.html дают понять, что Тюменская и Курганская область относятся сразу к двум четвертьфиналам. Хотя исторически они играли всегда у нас. Кроме того, ХМАО и ЯНАО по уставу Тюменской области входят в её состав. Вузы этих округов участвовали в нашем четвертьфинале, кроме Югорского ГУ, который участвовал в Западно-Сибирском. В этом году Югра поучаствовала в нашей квалификации и впоследствии приехала к нам на основной тур. Перед этим они написали нам письмо с вопросом о том, не нарушают ли они правила. Ведь они как будто не относятся к нашему ЧФ, но участвовали в нашей квалификации. Мы изложили им ситуацию и предоставили право выбора четвертьфинала на следующий год.

Я не знаю, есть ли такие спорные территории между другими ЧФами, поэтому советую вам внимательно изучить списки соседних регионов. С появлением квалификации пиар дотянется дальше, а значит, вы и ваши соседи можете вспомнить об одних и тех же новых вузах/городах.

P.S. Я обещал три поста. Но решил сделать ещё один. Это будет краткий конспект самых важных мыслей. Его можно будет использовать как чек-лист при подготовке квалификационного тура в своих регионах. Ждите этот пост через пару дней.

 
 
 
 
  • Vote: I like it
  • +73
  • Vote: I do not like it