Всем привет!
4 апреля, в 15.00 MSK состоится Topcoder SRM 615.
Предлагаю после контеста обсудить здесь задачи.
GL & HF
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 20.09.2024 14:54:02 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Не, эти SRM не очень честные. Участники из бывшего ссср имеют преимущество.
В арене "Russian Federation" теперь стала "Russia". Политика?:)
Да, да, да :)
"а иностранцы завистливо называют ее..."
Как Div1 500 решать?
Если из нулевой вершины нет ребер — Impossible. Иначе запустим дейкстру на графе, где вершина это пара (вершина исходного графа, остаток от длины пути по модулю MOD), где MOD = 2 * (длина какого-нибудь ребра из вершины 0). Если мы не посетили вершину (n — 1, T % MOD) или пришли за время большее T, то очевидно, до нее дойти нельзя. А если посетили (за меньшее или равное T время), то ответ Possible, т.к. можем несколько раз сходить по первому ребру туда-обратно, а потом пройти по пути, который нашел алгоритм Дейкстры.
Вообще неочевидно и не понятно, почему этого достаточно. Можно поподробнее?
Никак не могу понять, почему всегда выгодно ходить только по ребрам из нулевой вершины туда-обратно. Почему не может быть ситуации, когда мы крутимся по какому-нибудь циклу в середине пути?
P.S. Решение заходит, я что-то погорячился в предыдущей правке:) Оказалось, что в графе ребра только в одну сторону добавлял:)
Ну смотри. Для чего нам может быть нужно крутится по циклу в середине? Только для того, чтобы изменить длину пути по модулю MOD (если мы ходим по циклу с длиной равной 0 по модулю MOD, то вместо этого могли бы ходить по ребру вначале). А если нам выгодно пройти по циклу, чтобы изменить значение длины по модулю MOD, то мы это сделаем в дейкстре.
Можно попробовать понять это другим образом. Мы считаем динамику: dp[i][j] — минимальная длина пути из вершины 0, в вершину i, чтобы она по модулю MOD была равна j. Понятно же, что если dp[n — 1][T % MOD] > T, то никак дойти до вершины n-1 за время быстрее чем T+1 мы не сможем (если это неправда, то мы неправильно посчитали динамику). Если же dp[n — 1][T % MOD] <= T, то дойти можно.
В какую сторону доказательство непонятно?
Про то, что циклы обрабатываются Дейкстрой, теперь ясно.
А почему можно выбрать удвоенную длину любого ребра, ведущего из нулевой вершины, в качестве модуля?
Если мы для некоторого модуля запустили Дейкстру и увидели, что ответа нет, то его точно нет. Но при этом если существует путь, который по модулю подходит, еще не факт, что существует путь длины ровно T. Мы выбираем модуль равный двум длинам ребра, чтобы всегда выполнялось последнее утверждение (а оно будет выполнятся, т. к. любой путь длины LEN + MOD * k мы можем построить, где LEN — длина пути, которую нашли в дейкстре, а k — любое неотрицательное целое).
Я имел ввиду, почему достаточно только длину первого ребра использовать в качестве модуля? Почему не надо перебирать всевозможные длины ребер, исходящих из первой вершины? Ведь в таком случае условие d[n-1][T%M] <= T вроде бы меняется произвольно. Как-то неочевидно, что из d[n-1][T%M1] <= T следует d[n-1][T%M2] <= T.
А нам только нужно чтобы из d[n-1][T%M1] > T следовало, что не существует пути длины T (это же очевидно, да?). А если в неравенстве знак в другую сторону, то мы сразу можем предъявить нужный путь, и нам все равно что получится, если взять другой модуль.
Теперь понял, спасибо за помощь:)
Может такое быть, но это обработается алгоритмом Дейкстры: цикл в исходном графе с вершиной v будет простым путём через пары (v, r) с разными остатками r.