Всем привет.
Можете ли вы представить, что монитор (тот, который положение участников контеста, а не который надо разбивать после этого контеста) может быть вреден? На самом деле такое встречается нечасто, но в этом посте мы разберем два таких примера, а также попробуем предложить возможное решение этой проблемы. По идее, для MikeMirzayanov не должно быть проблемой реализовать эту фичу.
Итак, первый пример, 2015 год, четвертьфинал Южного региона в Саратове. Пруфы тут будут такие себе, так как контест куда-то исчез с CF. Вот тут этот контест был, когда я его писал: https://codeforces.com/contest/589 (можете глянуть 14-ую страницу моих посылок, там еще задачи были пошаффлены), вот анонс: https://codeforces.com/blog/entry/20989, а сейчас ссылки на задачи ведут в тренировку с id 102042, закрытую от всех. Непорядок! Тем не менее, постараюсь рассказать, что там было.
Официальные стендинги: http://neerc.ifmo.ru/archive/2015/southern/standings.html Мы видим на первом месте с 11 задачами команду Нижнего Новгорода, на голову сильнее остальных (так оно и было на самом деле). Но давайте себя поставим на место одной из команд, решивших 7 задач. Вопрос: на часах 3:00, два часа до конца. Какую задачу решать восьмой по счету?
Мы видим, что все команды, пытавшиеся сдать 8-ую задачу, пробовали сдать задачу I. Именно задачу I сдала восьмой по счету команда Нижнего Новгорода. Между тем, когда этот контест проводился на Codeforces через пару дней после четвертьфинала, почти все команды из фиолетовых-желтых участников решили 8+ задач, а восьмой они сдали задачу, которая в официальном мониторе обозначена как G. Кроме того, команды, решившие 9 задач, примерно поровну сдавали I и K из официального монитора (к примеру, мы тогда сдали 9 задач, и девятой сдали именно K). Пруфов, как я уже написал, не будет, так как контест куда-то удалили.
Ошибка всех команд с онсайта состояла в том, что они пытались следовать за командой, в составе которой были vepifanov и KAN. Для этих ребят сложность 8-10 задач была примерно одинаковая: примерно very easy. Но для более слабых участников это вовсе не так! Им не стоило копировать порядок задач, стоило подумать своей головой, а не смотреть в монитор. И тогда бы они обнаружили и то, что G халява, и то, что K не очень то уж и сложнее I.
В случае с четвертьфиналом Южного региона 2015 правда о сложности задач хотя бы вскрылась на зеркале, но вот второй пример меня полностью поразил. Это случилось совсем недавно, когда мы выложили контест, проводившийся в этом году в Самаре: https://codeforces.com/gym/102215, анонс: https://codeforces.com/blog/entry/67178 Результаты как онсайта, как зеркала, так и того, что в нем происходило потом, в виртуальных участиях, абсолютно неадекватны. Не в том плане, что слабые обгоняют сильных, а в плане порядка решения задач. Постараюсь не особо спойлерить.
В принципе, что на онсайте, что в зеркале происходило одного и то же. Итак, начинается контест, и желтые участники начинают решать задачи по порядку. Читают первую — сдают за 10-15 минут. Читают вторую — она еще легче, сдают за 5-10 минут. Читают третью — тоже легкая, тоже сдают. Читают четвертую — ну тут конечно кода побольше, но тоже легкая, сдают уже за 20 минут. И так далее.
А между тем зеленые видят монитор и недоумевают, а чего это контест какой сложный. Почему вторая по сложности задача какая сложная, на нее полчаса нужно! А на третью еще полчаса, а на четвертую целый час! Ответ прост: не нужно следовать за теми, кто намного сильнее тебя. Для желтых почти все задачи в этом контесте легкие, желтые решают их буквально с прочтения. Как минимум три задачи, сложность которых я оцениваю как very easy, остаются почти неоткрытыми до третьего/четвертого часа, где их обнаруживают желтые после того, как они решили намного более сложные задачи. А на онсайте одну из этих very easy задач вообще first-accept-нул участник, решивший ТОЛЬКО эту задачу.
Я думаю, если написать этот контест, сначала прочитав все задачи, а потом вообще не смотря в монитор, результат будет лучше, чем если бы вы использовали монитор по назначению. И точно не будет (цитата) туплю, чтобы мне на четвёртом часу таблица предложила [решить задачу уровня Div2B]. Если вы слабо-желтый и ниже, можете попробовать, а потом взглянуть на таблицу и, мягко говоря, удивиться.
Ну а теперь feature request. Нужно добавить два параметра в монитор — верхнюю и нижнюю границу рейтинга участников, показываемых в мониторе и внизу монитора (там, где говорят, сколько человек какую задачу решило). В принципе, можно только верхнюю. Например, я бы поставил себе верхнюю границу 2300 или 2400 и мне бы это отлично подошло — мне неважно, сколько там решил условный турист, это для меня не показатель. Турист может решить за 5 минут то, что я не решу за 5 часов. Намного более важно, какие задачи решают люди, равные и чуть более сильные по скиллу (ну а более слабые точно не помешают). Сделаем результаты более адекватными!
such marks, we can't satisfy the second condition (about the median), and the answer is -1. Otherwise we can get exactly such number of 
(maybe it's already satisfied). This is the required action for satisfying the second condition.
. This is the probability with which we go the the state dp[r][s — 1][p], with the number of scissors less by one.
. All other cases will be something between them.
people in each list.
