Convex hull trick
Постановка примера задачи
Есть n деревьев с высотами . Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что после уменьшения высоты спиливаемого дерева на 1 ее надо заправить. Причем стоимость заправки зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci. Изначально пила заправлена. И известны следующие ограничения : возрастают, убывают. (Задача с codeforces.com)
Наивное решение
Понятно, что нужно затратив минимальную стоимость срубить последнее (-е) дерево, т.к. после него все деревья можно будет пилить бесплатно (т.к. ). Посчитаем следующую динамику : - минимальная стоимость, заплатив которую будет срублено дерево номер Тогда . То есть понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешвые (док-во этого факта оставляется читателям как несложное упражнение). Тогда переберем - индекс предыдущего срубленного дерева. Пусть мы его срубили отптимальным (в смысле денег) способом. Тогда просто раз уменьшим высоту дерева i на 1. Каждый такой раз будем платить за последующую заправку пилы. Итак, на сруб -го дерева мы заплатили . Нетрудно видеть, что такая динамика работает за
О-Оптимизация
Давайте обозначим за , за , а за . Теперь формула приняла вид . Выражение напоминает уравнение прямой . Сопоставим каждому , обработанному ранее прямую . Из условия « убывают уменьшаются с номером » следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффицента. Давайте нарисуем несколько таких прямых : Файл:/Users/Vadim/Downloads/Снимок экрана 2016-11-23 в 19.04.01.png Итак, давайте выделим множество точек , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой , такой что . Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На катинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «»
Для чего нам нужна эта выпуклая оболочка прямых?
Пусть мы считаем динамику для -го дерева. Его задает . Итак, нам нужно для данного найти минимум по всем . Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую , можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять -ю прямую после того, как мы посчитали . Название статьи подсказывает, что нужно воспользоваться алгоритмом построения выпуклой оболочки множества точек. Но (внезапно) у нас не точки, а прямые… Но что меняется??? Пусть есть 2 стека , которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их и . Если оказалось, что новая прямая пересекает предпосл еднюю прямую выпуклой оболочки позже, чем последнюю (xL >= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или не станет меньше Ассимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет суммарно. Корректность : достаточно показать, что прямую нужно удалить из множества т.и т.т., когда она последнюю прямую множества наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю. Действительно, пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то найдется такой отрезок , что последняя(желтая) прямая при этих x-ах лежит ниже всех остальных и ее следует оставить в множестве. Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
Детали реализации:
Будем хранить 2 массива (имитирующих стеки) : и - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что возрастают (по условию задачи), а значит мы можем искать первое такое , что не бинарным поиском, а методом 2х указателей за суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x.
Р.Реализация
st[0] = 0
from[0] = -∞
sz = 1 // текущий размер выпуклой оболочки
pos = 0 // текущая позиция первго такого j, что x[i] >= front[st[j]]
for i = 1..n-1 {
while (front[pos] < x[i])
++pos
j = st[pos]
dp[i] = K[j] * a[i] + B[j]
if (i < n - 1) // если у нас добавляется НЕ последняя прямая,
K[i] = b[i]
B[i] = dp[i]
x = -inf
while (1) {
j = st[sz - 1]
x = divide(B[j] - B[i], K[i] - K[j])
if (x > from[sz - 1]) break
--sz
}
st[sz] = i
from[sz++] = x
}
(Здесь функция divide(a, b) возвращает нужное округление a / b) Такая реализация будет работать за O(n).
Динамический convex hull trick
Заметим, что условия на прямые, что возрастает/убывает и убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf). Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за или быстрее можем найти , но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине (рис. 4). Т.е. нужно уметь быстро (за ?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) примую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить (или любой аналог в других языках) пар = . Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей. Ассимптотика решения составит на каждый из n запросов «добавить прямую» + суммарно на удаление прямых. Итго .
Альтернативный подход
Другой способ интерпретировать выражение по всем их заключается в следующем: давайте перепишем выражение , т.е. запишем ка скалярное произведение векторов . Вектора хотелось бы организовать так, чтобы за O(logn) находить максимизирующий выражение . Посмотрим на рис. 5. Заметим довольно очевидный факт : красная точка(вектор) j не может давать более оптимальное значение v[j] * u[i] одновременно чем обе синие точки, т.к. v[j] * u[i] - это на самом деле проекция вектора v[j] на u[i]. По этой причине нам достаточно оставить выпуклую оболочку векторов v[j], а ответ на запрос - это поиск v[j], максимизирующего проекцию на u[i]. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из (0, 0) в (1, a[i])). Ее можно решить за O(logn) двумя бинарными или одним тернарным поиском Ассимптотика алгоритма по-прежнему составит
