Здравствуйте, сегодня в 5:00 по московскому времени начался очередной SRM, предлагаю после окончания соревнования вести его обсуждение здесь.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3993 |
2 | jiangly | 3743 |
3 | orzdevinwang | 3707 |
4 | Radewoosh | 3627 |
5 | jqdai0815 | 3620 |
6 | Benq | 3564 |
7 | Kevin114514 | 3443 |
8 | ksun48 | 3434 |
9 | Rewinding | 3397 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 155 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
10 | nor | 152 |
Название |
---|
Задачи точно от него?
А то раньше Джон, Брюс и счастливые числа - это была строго его фишка, а сейчас уже начали плагиатить, уже минимум 3 человека на эту тему матчи давали.
Хотя по стилю - да, задачи от Шефа)
Отличный матч и интересные задачи! Не понимаю почему так много людей тупило на 250.
Наверно потому, что задача интересная и не очень привычная. Многим и в голову не пришло, что чисел будет очень мало, и можно перебирать влоб - значительная часть участников написала динамику построения, которая пашет и для ограничений 10^100, но пишется намного дольше. И баг в ней допустить намного проще.
А я тупил жестко. Вчера экзамен сдавал, сегодня голова еще туманная, не поспал нормально, тупил жестоко. Сразу понял идею задачи, но потратил кучу времени на реализацию. В результате только 183 место, +6 (приятно хоть не минус... новый 1879).
Особенно весело было, когда я назвал функцию рекурсивного построения числа try, и долго думал, почему компилятор арены требует от меня какой-то catch)
Забавно, что у многих была готовая динамика построения, в которой нужно было только прописать 3 строки переходов и строку или две на работу с флагом "была/не было плохой цифры".
Сдать адекватное решение на 240-245 - вполне реально (ты это доказал своими 240.04... если сразу понять, что перебор проходит, то при быстром кодинге набирать надо еще больше). А написать с ноля динамику, которую сдают на примерно такой же балл... Или мне очень-очень далеко до настоящих задротов кодинга, или это довольно трудно.
Да, и как я мог забыть, поздравляю со счастливым 44 местом в дивизионе!
Вот разница между 245 и 240 как раз в этой проверке, ты, видимо, "не спешил". Мне тоже всегда, когда задачу можно сдать довольно быстро, кажется, что надо лишний раз потестировать, так как сейчас прям все сдадут, и после возможного ресабмита у меня будет 0 шансов на хороший результат:(
Да, и сделай сейчас еще счастливые +47 вклада)
upd. Новая цель тебе - получить +74)
Да,странно с рейтингом.
В моей руме было 2-ое синих у кого рейтинг примерно одинковый (1339 и 1349)
Первый 1 раз неудачно меня отчеленжил (причем кажется из-за того,что я переменную в коде не так назвал :D) и получил -215(!) ,а второй с 0-ем получил -7:)
Возможно это потому,что первая задача все таки должна быть такой,чтобы ее действительно решали все.
Формулами это легко объяснить. К тому же они довольно логичные:) Место берется среднее по диапазону равных баллов.
Следовательно, если 0 баллов, то сегодня это, условно говоря, около 430 места.
Если очень упрощенно, то синий пользователь, вероятно, по рейтингу мог находиться примерно на этом месте... Да еще и ему на пользу то, что его обогнало мело тех, кто не должен был обогнать (таких вообще мало), но он мог обогнать многих "неожиданно" (тех, у кого минуса, и рейтинг на 1-2 цвета выше:) ).
А если -25, то это место в седьмой сотне, и "вас взули почти все, кому не лень".
Вопрос скорее по теории:)
В общем, все знают, что если много нолей и низкий рейтинг, то можно словить + и с нолем.
Так вот, ниже 3 пользователя из тех, кто сегодня написал на 0, их старый рейтинг и изменение после матча:
4ndypanda 1312 +4
jayi 1306 0
liquid_amber 1306 -3
От чего такая разница? Согласно формулам, место для всех, у кого 0, берется одно и то же (середина диапазона нулей).
Следовательно, на знак изменения рейтинга влияет только 1 вещь - expected rank.
Для jayi я бы еще мог предположить, что он не в минусах, потому что weight меньше получился, и его минус "очень маленький".
Но по поводу того, что более высокий рейтинг получил +, а более низкий -... Что получается, из за разницы volatility у одного получился expected rank ниже его места, а у другого выше (ведь у одного +, у другого -, а actual rank у них одинаковый).
Это можно как-то красиво объяснить влиянием volatility и общего распределения результатов в дивизионе, или не судьба?
Кстати, пока думал над этим вопросом, немного порылся в теории, узнал о такой вещи, как error function (которая прямо используется при вычислениях expected rank), раньше даже не обращал внимания, что она есть в формуле, забавная штука:) А мне казалось, что там берут минимум из реального значения и единицы:) Может, что-то связанное с ней?
Тут свою роль сыграл показатель volatility:
Для участников с относительно низким рейтингом (по сравнению со всем дивизионом) получается, что чем выше его volatility (т.е. чем более участник "нестабилен"), тем выше его ожидаемое место.
Таким образом, от liquid_amber ожидали чуть большего, чем от jayi. А volatility у 4ndypanda настолько меньше других, что от него ожидали более низкого места даже при немного большем рейтинге.
Сел с ручкой и бумажкой разобраться, почему именно так выходит согласно формулам. Кажется, понял - потому что чем выше нестабильность, тем больше знаменатель, следовательно, тем выше шанс, что меня победит слабый игрок. Аналогично для более сильных - шанс моей победы вырастет, но более сильных намного больше. т.е. уменьшение нестабильности при низком рейтинге прибавит мне немного мест за счет шанса проиграть более слабым, зато "отнимет" кучу мест за счет того, что увеличится вероятность обогнать кого-то сильного (на каждом сильном я насобираю больше).
Посчитал, что у меня шанс обогнать Петю почти 2 из 10000000, но если поднять мне нестабильность от 294 до 500, то шанс вырастает сразу более чем в 1000 раз, до 2 из 10000:)
Спасибо за объяснение причин этого "парадокса".
Получается, что в верхней части таблицы большинство тех, с кем меня сравнивают, ниже меня по рейтингу, и мне выгодней иметь больший показатель нестабильности (тогда мне простительно иногда лажать)?
Получается так.
Топовым "игрокам" выгодна большая нестабильность, т.к. для них она понижает ожидаемое место.