| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | pajenegod | 145 |
| 9 | orz | 145 |
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 должна работать, и это следует из нормального решения (точка оптимума либо остается прежней, либо становится последней возможной).
Но это все, конечно, только если отдельно обработать единичные отрезки.