| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Доброго утра!
Только, что прошел очередной СРМ, а поста до сих пор нету( Вот я и решил что настало мое время написать пост про СРМ. Интересно как решать Hard.
P.S.: Кажется у KADR а 2999 рейтинга facepalm. Удачи в следующем раунде :-)
P.S.2: Систесты оказались мгновенными.
Спасибо, удача мне теперь не помешает :) А главное, все из-за ресабмита по 250, в которой я завел слишком маленький массив...
Насчет решения 1000. Там можно перебрать одно ребро, которое мы точно удалим. Теперь, у нас есть 2 дерева и нужно из них поудалять куски так, чтобы оставшиеся деревья были изоморфны. Будем делать динамику: f(e1, e2) — максимальный размер изоморфных кусков, при условии что мы только что удалили из первого дерева ребро e1, из второго — e2 и стоим в их концах (ребра ориентированные). Посчитаем в начале нашу динамику для всех пар вершин, смежных с теми, где мы стоим. Теперь нам нужно как-то заматчить между собой эти вершины, максимизировав при этом суммарное количество вершин в дереве, которое получится. Это можно сделать Венгерским алгоритмом или же при помощи MCMF.
Сложность на первый взгляд большая (можно оценить как O(N6)), но наверняка там все делится на N или N2 (я этого не доказывал). Работает 0.323 на макстесте в практис руме.
По 250й я тоже потерял баллы. Я неправильно понял слово within я почему-то подумал, что это ровно, а не меньше или равно)
А по харду крутое решение.
achievement unlocked, можно обратно в желтые.
500 можно решить быстрее, чем за куб?
Не похоже. Тем более ее бы не дали с ограничениями 300. Вообще на US Open этого года в Gold дивизионе задача A была немного похожа на эту (только совсем другая :-)).
Так мало ли, пример — задача F c чемпионата Урала, который сейчас идет.
Ее тоже обычно дают с ограничениями в пределах 300. Но вот тут взяли, и не дали:)
Если решение с лучшей асимптотикой слишком сложное для div1 500, то все выглядит вполне логично.
Я заинтересовался, потому что вспомнил, что где-то уже видел такую или очень похожую задачу с довольно жесткими, как для куба, ограничениями. То ли 1000, то ли 1111 даже.
Вроде бы за квадрат не сложно решается. Пусть f(i, j) — это количество способов расставить волков так, чтобы предпоследний был в позиции i, а последний — в j. Чтобы сделать переход, переберем позицию предыдущего волка k и если она согласуется с нашими отрезками, то прибавим к f(i, j) величину f(k, i). Это пока работает за O(N3). Теперь заметим, что все подходящие нам k идут подряд, начиная с первой ячейки. Значит, мы можем хранить частичные суммы на префиксах для каждого фиксированного параметра j и делать переход за О(1).
У меня примерно то же самое сдано на контесте. Динамика f(pos, one, two) — сколько способов расставить волков до позиции pos, причём дальше до позиции one можно будет поставить не более одного волка, а до позиции two — не более двух волков. Оптимизация состоит в том, что two — это функция исключительно от pos, значения которой получаются по данным отрезкам линейным предподсчётом. Поэтому состояния динамики — на самом деле пары (pos, one), и из каждого два перехода: поставить или не поставить волка на позицию pos. Вот код.
Ну да, все ведь так просто) Спасибо.
Как по мне, могли бы ее дать в роли 500 и с ограничениями, не допускающими решение за куб. Тем более, что подобного рода задачи у них в роли медиума бывают не так уж и редко.
Затупил.