Привет, Codeforces.
Вчера закончился длинный тур Открытой олимпиады этого года, который проходил с 25.11 по 15.01. В нём было много интересных задач, которые мне хотелось бы разобрать и обсудить в этом посте.
Нетрудно заметить, что если $$$t_{i + 1} - t_i \leq m$$$, то задачи $$$i$$$ и $$$i + 1$$$ будут сданы либо в один день, либо в соседние дни, а для того, чтобы условие не выполнялось, необходимо, чтобы какие-то два соседних момента времени находились в разных не соседних днях (тогда в день между ними не будет сдана ни одна задача). Если же $$$t_{i + 1} - t_i \ge 2m$$$, очевидно, что между этими двумя моментами времени точно есть день, в который мы ничего не сдадим. Остаётся последний случай: $$$m \lt t_{i + 1} - t_i \lt 2m$$$. В этом случае "плохие" дни могут начинаться с момента $$$t_i + 1$$$ до момента $$$t_{i + 1} - m$$$.
Дальше нам каким-то образом нужно найти такой часовой пояс, чтобы никакой день в нём не начинался в "плохой" отрезок часов. Понятно, что для каждого "плохого" отрезка часов, область часовых поясов, которые он портит, представляет из себя циклически отрезок т.е. 1 или 2 обычных отрезка. Чтобы найти часовой пояс, который не испортится, можно использовать дерево отрезков (неявное или на сжатых координатах) с прибавлением на отрезке.
Асимптотика: $$$O(n \log n)$$$ (если сжать координаты) или $$$O(n \log C)$$$ (если написать неявное ДО).
Построим дерево отрезков с $$$2^{20}$$$ листов. Пусть $$$k_i$$$ — $$$i$$$-й бит очередного параметра запроса.
Покажем, что достаточно легко модифицировать обычный обход дерева отрезков, чтобы он делал то, что нужно в этой задаче. Предположим, что в некоторый момент мы оказались в вершине $$$v$$$, которая отвечает за отрезок $$$[l; r]$$$, и которая лежит в запросе не целиком.
Пусть $$$m$$$ — левый конец правого ребёнка этой вершины, т.е. $$$\frac{l + r + 1}{2}$$$. Если $$$v$$$ находится на высоте $$$h$$$ (листы находятся на высоте $$$0$$$), то все натуральные числа на отрезке левого ребёнка имеют 0 в $$$h - 1$$$ разряде битовой записи, а все натуральные числа на отрезке правого ребёнка имеют 1 в $$$h - 1$$$ разряде битовой записи.
Отсюда следует следующее. Пусть мы сейчас находимся в $$$v$$$ и $$$k_{h - 1}$$$ равен $$$1$$$. В таком случае, левый и правый ребёнок $$$v$$$ "обменяются" отрезками запроса, т.е. если часть запроса в левом ребёнке была равна $$$[l_1; r_1]$$$, а в правом — $$$[l_2, r_2]$$$, то после применения $$$\oplus k$$$ эти части превратятся в $$$[l_1 + (m - l); r_1 + (m - l)]$$$ и $$$[l_2 - (m - l); r_2 - (m - l)]$$$ соответственно.
Кажется, что после такой модификации, запрос к ДО все ещё должен работать за $$$O(n)$$$, но я не до конца умею это пруфать :/
Pro tip: поскольку ввод в этой задаче достаточно большой (больше 7M интов), неплохо бы перестраховаться и заюзать шаблон на быстрый ввод.
Асимптотика: $$$O(qn)$$$.
Группы 1-2: делаем все запросы втупую, после каждого запроса считаем ответ, используя ДП на DAG-е.
Группа 7: Нетрудно заметить, что в любой момент времени все рёбра будут образовывать множество отрезков из сонаправленных рёбер. Отрезок из $$$n$$$ рёбер вносит в ответ вклад $$$F(n) = \frac{n(n + 1)(n + 2)}{6}$$$. Нетрудно доказать, что все запросы удаляют сколько-то отрезков и образуют $$$O(1)$$$ новых, т.е. все отрезки можно поддерживать в сете интервалов.
Асимптотика: $$$O((n + q) \log n)$$$.
Пусть $$$l(x)$$$ — наименьшая позиция в порядке сдачи задач, на которой может стоять задача сложности $$$x$$$; $$$r(x)$$$ — наибольшая позиция. Нетрудно доказать, что в таком случае, задача сложности $$$x$$$ может находиться на любой позиции $$$l(x) \leq p \leq r(x)$$$.
Наименьшую позицию можно получить, если в каждый день, когда задача сложности $$$x$$$ ещё не разблокирована, мы будем решать не больше одной задачи (ноль, если все доступные задачи уже решены). Аналогично, наибольшую позицию можно получить, если каждый день, когда сложность $$$x$$$ недоступна, решать не более одной задачи, затем решать оставшиеся задачи сложности $$$\gt x$$$ по одной, а затем в один день решить все доступные в этот день задачи, решив задачу сложности $$$x$$$ последней.
Всё вышеописанное нетрудно посчитать за $$$O(n)$$$ (например, используя метод двух указателей) или за $$$O(n \log n)$$$ (например, используя мапы).
Асимптотика: $$$O(n)$$$ или $$$O(n \log n)$$$.
Самая первая идея, которая приходит в голову — поскольку различных цветов не так уж и много, можно сделать перебор/отжиг/ещё что-то смешное. Давайте остановимся на переборе. Но чтобы делать его быстро, нужно заметить несколько интересных утверждений.
Утверждение 1: если рёбер какого-то цвета достаточно много (например, $$$\gt 21$$$), то можно не перебирать рёбра этого цвета, т.к. если найдётся разноцветный лес с рёбрами всех остальных цветов, то количество рёбер, которые теоретически могут "испортить" лес при добавлении, будет $$$\leq \frac{8 \cdot 7}{2} - 7 = 21$$$ (например, если уже имеющиеся рёбра составляют бамбук длины 7).
Утверждение 2: теперь посмотрим на структуру перебора. Заметим, что есть сделать рекурсивный перебор всех возможных вариантов, а не просто выбор $$$k$$$ наборов рёбер, то можно отсечь какие-то плохие варианты. Также утверждается, что перебор цветов в порядке неуменьшения количества рёбер с таким цветов будет работать достаточно хорошо.
Утверждение (скорее совет) 3: в этой задаче не нужны сложные структуры или рандом. СНМ за квадрат работает достаточно быстро на таких мелких размерах графов (а ещё его очень удобно откатывать).
Следуя вышеописанным советам, для каждого запроса можно достаточно быстро находить нужное множество рёбер (если оно вообще существует).
...эта задача является упражнением на пересечение матроидов, но если у вас есть личная жизнь, вы явно не хотите такое писать.
Асимптотика: я не знаю, как это оценивать.
Будем называть плохими те вершины, для которых на текущий момент уже известно о $$$\gt 1$$$ исходящих рёбер. Нетрудно заметить, что среди любых 4 вершин есть хотя бы одна плохая (т.к. исходящих рёбер $$$6$$$, а вершин $$$4$$$; по принципу Дирихле будет плохая вершина).
Сначала будем спрашивать рёбра между двумя вершинами, которые не являются плохими. Нетрудно заметить, что к тому моменту, когда не останется неиспользованных рёбер между двумя неплохими вершинами, количество неплохих вершин будет $$$\leq 3$$$ и мы потратим не более $$$2n - 3$$$ запросов. Про оставшиеся вершины мы будем узнавать "втупую", то есть перебирать все рёбра между ней и другими вершинами.
Несложно понять, что такое решение работает за $$$5n$$$ запросов в худшем случае, но каким-то образом оно работает за $$$4n$$$ в группах с неадаптивным интерактором.
Асимптотика: $$$O(n^2)$$$, т.к. нужно поддерживать информацию о всех рёбрах, про которые ещё можно спросить на первом этапе решения.
Для начала заметим, что ответ можно забинарить (очевидно, что если $$$k$$$ циклов хватит, то и за $$$k + 1$$$ цикл можно сделать). Но как же именно проверять, подходит ли конкретное количество циклов?
Пусть хотим проверить, хватит ли $$$m$$$ циклов. Тогда применим к каждому блоку $$$m$$$ охлаждений на $$$B$$$ градусов. Далее, если $$$A \lt B$$$, проверим, сколько раз можно прибавить к какому-то элементу $$$B - A$$$, чтобы все элементы остались $$$\lt 0$$$. Если это число $$$\le m$$$, то $$$m$$$ циклов не хватит. Если же $$$A \ge B$$$, из каждого элемента будем вычитать $$$A - B$$$, пока тот $$$\ge 0$$$. Если необходимое количество операций $$$\leq m$$$, нам хватит $$$m$$$ циклов, чтобы выполнить условие.
Асимптотика: $$$O(n \log C)$$$.
Пронумеруем вершины в порядке сортировки по полярному углу. Очевидно, что первым ходом одна вершина удалится и останется $$$n - 1$$$ сторона исходного многоугольника. Что может происходить дальше:
выбираем какой-то отрезок из подряд идущих сторон исходного многоугольника и удаляем одну из его крайних сторон
выбираем какой-то отрезок из $$$\gt 1$$$ подряд идущих сторон исходного многоугольника и удаляем две стороны с какого-то из его концов
выбираем какой-то отрезок из $$$\gt 3$$$ подряд идущих сторон исходного многоугольника и удаляем две стороны из его середины, получая два новых отрезка с суммарной длиной $$$l - 2$$$
После каждого момента множество сторон исходного многоугольника составляет несколько отрезков подряд идущих сторон. Если рассматривать каждый такой отрезок как игру, получаем сумму игр. Чтобы посчитать результат исходной игры, применим теорию Гранди. Так как всего различных игр $$$n$$$, и из каждой не более $$$n$$$ переходов в суммы игр, всё это можно предподсчитать за $$$O(n^2)$$$.
Далее, нам нужно что-то делать с особыми точками. Понятно, что нас не интересуют те секторы, в которых нет особых точек, поэтому будем считать, что в начальном состоянии удалены все такие рёбра $$$AB$$$, что внутри треугольника $$$ABC$$$ не лежит ни одной исходной точки.
Понятно, что при добавлении/удалении особой точки удаляется/добавляется не более одной стороны исходного треугольника -> множество игр в начальной конфигурации можно поддерживать какой-нибудь структурой данных, например сетом интервалов.
Pro tip: поскольку ввод в этой задаче достаточно большой (больше 2M интов), неплохо бы перестраховаться и заюзать шаблон на быстрый ввод.
Асимптотика: $$$O(n^2 + q \log n)$$$.
Разделим решение на две части.
Часть 1 (группы 1-2): Пусть $$$dp_{0, v, i}$$$ — максимальная стоимость, которую можно получить, взяв $$$i$$$ рёбер в поддереве вершины $$$v$$$, при этом не взяв никакую пару рёбер с центром в $$$v$$$; $$$dp_{1, v, i}$$$ — аналогичная дпшка, но известно, что какая-то пара рёбер имеет $$$v$$$ в качестве центра. Случай, когда мы используем в паре ребро из $$$v$$$ в его предка (которое не входит в поддерево) нужно учитывать только для таких $$$dp_{1, v, i}$$$, что $$$i \mod 2 = 1$$$.
Достаточно очевидно, как пересчитывать эту динамику за $$$O(sub_v \cdot sub_u)$$$ для вершины $$$v$$$ и его ребёнка $$$u$$$, где $$$sub_i$$$ — размер поддерева вершины $$$i$$$. На самом деле, этого будет достаточно, потому что сумма всех таких слагаемых будет равна $$$O(n^2)$$$.
Часть 2 (группы 4-5): Пусть $$$dp_{l, m}$$$ и $$$dp_{m, r}$$$ хранят все самые выгодные стоимости взятия $$$k$$$ рёбер на полуинтервале вершин $$$[l; r)$$$. Тогда во-первых, $$$dp_{a, b}$$$ "вогнутое" для любых $$$a < b$$$ (массив "вогнут", если $$$a_i - a_{i + 1}$$$ возрастает с увеличением $$$i$$$), т.е. к нему можно применить $$$(max, +)$$$-свёртку за $$$O(n)$$$; во-вторых, $$$dp_{l, r}$$$ можно как раз пересчитать сверткой за $$$O(n)$$$ -> $$$dp_{0, n}$$$ можно посчитать за $$$O(n \log n)$$$, используя технику разделяй-и-властвуй.
Делать $$$(max, +)$$$ свёртку для "вогнутых" массивов можно вот так.
А вообще, можно получить 49 (+15 на оффлайн) баллов, используя лямбда-оптимизацию на дереве без восстановления ответа; и 100 баллов, если додуматься, как сделать восстановление, но мне было впадлу.
Спасибо за внимание.
Для задачи I, aliens trick (вроде его лямбда-оптимизацией кличут) заходит на 100. Пересчет дп аналогичный как в более ранних подзадачах, без учёта лишнего измерения; восстановление ответа чуть сложнее, но возможно благодаря танцам с бубном и шаманским пляскам, выводится с использованием бумаги и ручки довольно быстро, самое сложное — реализовать. Чуть позже прикреплю код если кому интересно)
Написал я этот ваш инопланетянский трюк, не понял правда за что свой сон отдал.
Опишу альтернативный подход, он уже встречался вот тут https://mirror.codeforces.com/gym/102331/problem/J
Будем решать задачу для всех k, а также держать в голове HLD дерева. Идея состоит в том, что нам нужно знать честные вектора динамики только для самых верхних вершин в тяжёлых путях. То есть алгоритм подсчёта может быть таким: для всех лёгких детей получить правильное значение динамики разделяйкой по их тяжёлому пути; объединить значения лёгких детей (тоже разделяйкой). Итого мы для вершины получим значение динамики без учета тяжёлого сына; как раз это значение и будет использоваться, когда понадобится правильное значение от верхней вершины текущего тяжёлого пути. Та, что по тяжёлому пути, совпадает с решением подзадачи на массиве (ОП рассказал). Та, что по лёгким детям, почти полностью повторяет мерж детей в рюкзаке за квадрат (и тут ОП помог). O(n log^2 n) времени, O(n log n) памяти, значительные константы.
Восстановление ответа сводится к запоминанию, когда делаем сумму Минковского, из каких индексов аргументов мы пришли. Граф этой штуки примерно такой — вот мы в корне, спустились по разделяйке для его тяжелого пути; там в листьях — корни разделяек по лёгким детям; у них в листьях — корни разделяек по тяжёлым путям и т.д. К сожалению, прямо так в память это не влазит. Запоминать только корни и листья, а промежуточные вершины каждый раз пересчитывать (лишний log в асимптотике) — не влазит по времени. Поэтому нужен trade off, а именно сделаем кеш для бедных — будем запоминать лишь вершины на глубине <= 2 от корня разделяйки; как только понадобилась какая-то более глубокая — пересчитываем (тоже с запоминанием на глубине <= 2). Кажется, формально асимптотика сломана, но так оно упихивается.
Код https://pastebin.com/4KUmwzb3
"B" можно было придумать с нуля, но легче читать блоги на CF почаще :)
https://mirror.codeforces.com/blog/entry/105723
А я Б так и не придумал :))))
F на (100?) баллов (если кому интересно). Изначально скажем $$$v = 0$$$ и сделаем форик $$$u$$$ in $$$1...n-1$$$. Если направление $$$vu$$$ $$$forward$$$, делаем $$$v := u$$$. Заметим, что для всех вершин кроме $$$v$$$ у нас есть ровно одно исходящее ребро, у $$$v$$$ их 0. Будем спрашивать направление до всех вершин от $$$v$$$, пока они не закончатся или пока у нас не станет 2 исходящих ребра. Далее, если 2 исходящих ребра нашлись, можно втупую за квадрат спросить все пары вершин, каждая из которых имеет 1 выходящее ребро. Так останутся 2 кандидата на ответ. Каждого спросим за $$$n - 1$$$ запрос. Итого $$$4n$$$ запросов. Почему $$$4n$$$? На момент, когда у нас осталось 2 кандидата, кол-во исходящих рёбер из всех остальных вершин ровно 2, поэтому мы сделали чуть меньше чем $$$2n$$$ запросов. Почему кандидатов будет 2? Если за квадрат спрашивать все вершины, каждая из которых ещё не имеет 2 исходящих ребра, может остаться не более 3 кандидатов, которые образуют цикл. Мы фориком сделали так, что любой цикл бы содержал вершину $$$v$$$, а потом её поспрашивали, поэтому кандидатов осталось 2
Ну кстати F — IMO Short List 2019 C8, если кому интересно...
Сегодня появился официальный разбор и дорешка в тренировке на Codeforces.
By the way, моё решение в E не прошло последнюю группу по времени, зато F прошла на 100 из-за плохого интерактора :)
Я слышал что у кого то прошла Е с СНМ со сжатием путей и откатами
Редакт: Во блин, оказалось был не прав и всё нормально работает. Десять раз извиняюсь.
Почему же не могут? Вполне себе могут, просто непонятно зачем
Разве?
Всегда считал (и слышал от других) что при использовании сжатия путей откаты не будут работать — ведь между откатами родитель вершинки может поменяться и как мы будем запоминатьТолько что осознал что все эти годы жил во лжи...
Пы.Сы.
на всякий случай уточню — откаты действительно работают вместе со сжатием не ломая асимптотики?
Оказалось, действительно возможно
Но как ещё оказалось, был тест буквально ломающий решение (т.к. откатывалось неправильно), но задачка не упала) В любом случае забавно
Но за дезинформацию выше прошу прощения =)