| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
3 января 2019 в 20:20 (время московское) стартовал первый этап SnarkNews Winter Series 2020. Как и несколько предыдущих серий, SNWS-2020 пройдёт на системе Яндекс.Контест. Опубликовано расписание серии.
По просьбам участников отдельно публикую ссылку на вход в первый раунд. Здесь же по окончании раунда в соответствии с расписанием можно будет обсудить задачи первого раунда.
А в чем идея Е в итоге? Я в дорешку сдал d&c оптимизацию без доказательства, но после стресса стало очевидно, что она не работает) Нормально тогда в такой задаче иметь 7 тестов без мультитеста?)
В е лешко заметить, что lca куска определяют какие-то не более 2 подряд идущих вершин
Как это помогает?
Ну мне кажется, что это решающее наблюдение. Можно назвать идеей Е
Ну это значит что можно не разбивать на куски, а взять к непересекающихся пар соседей или отдельных элементов, и минимальная сумма значений для них совпадает с минимальным ответом для отрезков.
Ок, я неправльно понял твой коммент
После этого давай найдем K отрезков длины не больше двух, таких, что сумма lca на отрезке минимальная (остальные вершины можно добавить к любому из соседних отрезков не ухудшив ответ)
Получаем динамику d(i, j) — сколько стоит выбрать j таких отрезков на первых i вершинах перестановки, с переходами d(i, j) = min(d(i, j), d(i — 1, j)); d(i, j + 1) = min(d(i, j + 1), d(i — 1, j) + level(p[i])) и d(i, j + 1) = min(d(i, j + 1), d(i — 2, j) + level(lca(p[i], p[i — 1])))
А что, если в оптимальном ответе получились, например, только единичные отрезки, их же вроде как нельзя так просто расширить как отрезки с двумя элементами?
Почему? Ответ от расширения отрезка никогда не увеличивается
А, точно, спасибо
На самом деле d&c должна работать, и это следует из нормального решения (точка оптимума либо остается прежней, либо становится последней возможной).
Но это все, конечно, только если отдельно обработать единичные отрезки.