В 2010 Москвы.
Всём удачи!
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
18:53:13
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
18:53:13
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | djm03178 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 29.11.2024 22:41:47 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Спасибо, а почему емблема гугла на входе в арену?
Значит Google спонсирует СРМ. Ну и собирает инфу по участникам. Хотя галочки "желаете ли вы расшарить инфу о себе" вроде не было.
у всех заходит в арену?
У меня да
Попробуйте обновить арену.
Нет, ну как задачи наподобие 450 вообще пропускают? Так и хочется написать автору: "Hey, dude, I KNOW HOW TO SOLVE TSP BY DP!!!".
А теперь — обратите внимание на процент АС по задаче)
Да говно баянистое, а не задача. У меня упала из-за того, что я забыл учесть при переходе время начала работы магазина. Просто из головы вылетело. Задача-то точно ни о чем. Топкодер в последнее время не очень радует интересностью задач. Первая задача вообще больше читается, чем решается. Контест абсолютно бесполезный в плане саморазвития.
Если судить только по тех задачах, которые удалось решить во время контеста, то 95% контестов — полное говно в плане саморазвития. Вы 1000 решили?
Upd. А моему саморазвитию, к примеру, он очень помог. Во время контеста узнал несколько полезных вещей; и сейчас — еще несколько. И задач вроде сегодняшней 450 я никогда раньше в жизни не то что не делал, но даже и не видел.
Надеюсь, автору матча станет легче от того, что хоть чьему-то саморазвитию он помог:)
Насколько я понимаю, большинство упавших — по ТЛ. Автор, видимо, зачем-то пытается различить динамику 2m * m2, Дейкстру 2m * m2 * log(2m * m2) и Дейкстру 2m * n * log(2m * n). Первое, кажется, проходит почти всегда, второе и третье — зависит от прямоты рук. Мне это кажется глупостью, которая задачу думательно вообще не усложняет:(
Может автор хотел различить тех кто пишет а потом думает от тех кто сначала думает а потом пишет) Как показала практика я отношусь к первым :-)
А теперь раскройте скобки логарифмов и получите 2m * m2,
и 
. Скажете, что разница в 64-128 раз — это мало?
Скорее: 2m * m2, 2m * m3 и 2m * n * m. Но разница все равно большая.
См. http://vexorian.blogspot.ru/2013/05/srm-579-disaster-averted.html. За день до контеста имеющаяся задача оказалась палёной. Не то чтобы это оправдывает авторов, но хотя бы объясняет их позицию.
Как делается 1000ка?
Не успел додебагать на контесте, но кажется верным следующее:
Основная ДП — F(rock, paper, scissors, points) — вероятность того, что у нас выпало столько таких значений на кубиках и мы получили столько очков. Пересчет с помощью вспомогательной ДП: R(r, p, s), P(r, p, s), S(r, p, s) — пусть у нас было брошено r + p + s кубиков, выпало столько таких значений на кубиках, какое матожидание вероятности того, что на следующем кубике выпадет R, P, S соответственно. (иными словами, сумма вероятностей R, P, S кубиков, которые не были выброшены, поделенная на их количество). Зная на каждом шагу основной динамики эти вероятности, смотрим, что выгоднее всего выбрать нам, и в зависимости от того, что мы выкинули на очередном кубике, пересчитываем основную. Как-то так..
А как пересчитываем дополнительную динамику?
Для каждого кубика мы можем посчитать следующую величину:
Вероятность того, что он не вошел в наш набор из R, P, S
Вероятность того, что он вошел и был выкинут как R, P или S (соответственно, единица минус предыдущая вероятность, умножить на вероятность выпадения R, P, S)
Зная эти 2 вероятности, делаем инкрементальную ДП — каждый кубик отправляем в одно из 4 множеств R, P, S, NULL с задаными вероятностями и пересчитываем значение — считаем не матожидание вероятностей выпадения R, P, S в множестве NULL, а их сумму, а в конце делим на размер этого множества.
UPD: Походу у меня неверно считается первая вероятность, надо так как в решении, описанном Petr ниже.
Более интересный вопрос, почему он не зависит от порядка, а только от количества.
Нам для перехода не нужно знать, в каком порядке у нас выпадали значения на кубиках, только то, сколько раз какие выпадали. А как именно они выпадали, то есть все возможные сочетания кубиков и результатов у нас как бы "учтены" во вспомогательной ДП.
Возможно, я неверно понял вопрос?..
Да, не совсем понял, но ты на него ответил в коментарии с решением на самом деле. Там действительно зависит, но нам нужно среднее, поэтому все считается.
Сначала заметим что ответ — это сумма матожидания выигрыша на 1-м шаге, матожидания выигрыша на 2-м шаге, и так далее. Поэтому давай научимся считать матожидание выигрыша на i-м шаге.
На i-м шаге есть сколько-то возможностей для #камней, #бумаг, #ножниц, выпавших к этому шагу, и для каждой возможности легко посчитать её вероятность. Теперь нужно всего лишь научиться находить матожидание выигрыша на i-м шаге если уже выпало a камней, b бумаг, c ножниц, и мы сказали, например, "камень".
Ясно что последнее, в свою очередь, равно сумме таких величин: матожидание выигрыша на i-м шаге, если уже выпало a камней, b бумаг, c ножниц, мы сказали "камень", и вытащили из бочонка j-й кубик. Оно равно вероятности того, что в бочонке вообще есть j-й кубик, деленной на n-a-b-c (что мы вытащим именно его), и умноженной на (3*вероятность ножниц+вероятность камня).
Таким образом осталось научиться находить вероятность, что в бочонке есть j-й кубик, если уже выпало a камней, b бумаг, c ножниц. А это как раз и считается динамикой — считаем вероятность набрать a,b,c всеми способами и всеми способами, но без j-го кубика, и делим второе на первое.
Не очень понятно, почему для подсчета ответа нам важно знать тройку (a, b, c). Если смотреть на рассуждения выше, то нам достаточно знать a + b + c, т. е. номер шага.
Потому что мы знаем тройку (a,b,c), когда делаем свой ход, поэтому максимум нужно выбирать не глобально, а при условии тройки (a,b,c). Там где в верхнем посте сказано "например, камень", имеется в виду, что нужно взять максимум по трём возможным ходам.
Что может быть под uncaught exception в практисе? Что угодно?)
А что может быть под:
Expected:
16
Received:
1 0
0 1
2 0
0 2
... (много строчек)
О_о оказывается, я даже не самый оригинальный:)
По поводу моей — у меня подозрение на ML)
Upd. Ну да, почти наверняка ML. Падает на pushback...
Нашел. У меня эти пары чисел выводились в System.err и каким-то образом были восприняты как возвращаемое значение.