Привет, 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 баллов, если додуматься, как сделать восстановление, но мне было впадлу.
Спасибо за внимание.
Comments (0)
