Convex hull trick — различия между версиями
(→Альтернативный подход) |
(→Альтернативный подход) |
||
Строка 130: | Строка 130: | ||
|id=th12392. | |id=th12392. | ||
|statement=Если есть <tex>3</tex> вектора <tex>a, b, c</tex>, таких что <tex>[a-b, b-c] < 0</tex> то либо <math>(a, u) < (b, u)</math>, либо <math>(c, u) < (b, u)</math>, где вектор <math>u = (1; k)</math>. | |statement=Если есть <tex>3</tex> вектора <tex>a, b, c</tex>, таких что <tex>[a-b, b-c] < 0</tex> то либо <math>(a, u) < (b, u)</math>, либо <math>(c, u) < (b, u)</math>, где вектор <math>u = (1; k)</math>. | ||
− | |proof=По условию теоремы известно, что <tex>[a-b, b-c] < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u) < (a, u) \Leftrightarrow b_{x} + k \cdot b_{y} < a_{x} + k \cdot a_{y} \Leftrightarrow (b_{x} - a_{x}) < k \cdot ( | + | |proof=По условию теоремы известно, что <tex>[a-b, b-c] < 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) < (a_{y} - b_{y}) \cdot (b_{x} - c_{x})</tex> (*). Предположим (от противного), что <tex>(b, u) < (a, u) \Leftrightarrow b_{x} + k \cdot b_{y} < a_{x} + k \cdot a_{y} \Leftrightarrow (b_{x} - a_{x}) < k \cdot (a_{y} - b_{y})</tex> и при этом <tex>(b, u) < (c, u) \Leftrightarrow b_{x} + k \cdot b_{y} < c_{x} + k \cdot c_{y} \Leftrightarrow (c_{x} - b_{x}) > k \cdot (b_{y} - c_{y})</tex>. |
Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = k</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд. | Подставим эти неравенства в (*). Получим цепочку неравенств : <tex>k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y}) = k</tex><tex> \cdot (b_{y} - a_{y}) \cdot </tex><tex>(b_{y} - c_{y})</tex> <tex> < (a_{x} - b_{x})</tex><tex> \cdot (b_{y} - c_{y})</tex><tex> < (a_{y} - b_{y}) \cdot </tex><tex>(b_{x} - c_{x})</tex> <tex>< k \cdot (a_{y} - b_{y})</tex><tex> \cdot (c_{y} - b_{y})</tex>. Получили противоречие : <tex>k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) < k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})</tex>. Значит предположение неверно, чтд. |
Версия 20:56, 2 октября 2020
Convex hull trick — один из методов оптимизации динамического программирования, использующий идею выпуклой оболочки. Позволяет улучшить асимптотику решения некоторых задач, решемых методом динамического программирования, с до . Техника впервые появилась в 1995 году (задачу на нее предложили в USACO — национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.
Содержание
Пример задачи, решаемой методом convex hull trick
Рассмотрим задачу на ДП:
Задача: |
Есть бензопилы. Но пила устроена так, что она может спиливать только по (убывание и возрастание нестрогие) метру от дерева, к которому ее применили. Также после срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенное кол-во монет. Причем стоимость бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен , то цена заправки равна . Изначально пила заправлена. Также известны следующие ограничения : возрастают, убывают. Изначально пила заправлена. | деревьев с высотами (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
(Задача H с Санкт-Петербургских сборов к РОИ 2016 [1])
Наивное решение
Сначала заметим важный факт : т.к. жадных алгоритмов, чем к теме данной статьи). Поэтому перед -м деревом мы обязательно срубили какое-то -е, причем . Поэтому чтобы найти нужно перебрать все и попытаться использовать ответ для дерева номер . Итак, пусть перед -м деревом мы полностью срубили -е, причем высота -го дерева составляет , а т.к. последнее дерево, которое мы срубили, имеет индекс , то стоимость каждого метра -го дерева составит . Поэтому на сруб -го дерева мы потратим монет. Также не стоит забывать, что ситуацию, когда -е дерево полностью срублено, мы получили не бесплатно, а за монет. Итоговая формула пересчета : .
убывают (нестрого) и , то все неотрицательны. Понятно, что нужно затратив минимальную стоимость срубить последнее ( -е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. ). Посчитаем следующую динамику : — минимальная стоимость, заплатив которую можно добиться того, что дерево номер будет срублено. База динамики : , т.к. изначально пила заправлена и высота первого дерева равна , по условию задачи. Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к темеПосмотрим на код вышеописанного решения:
int(int a[n], int c[n]) dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = for i = 2 = 1..n dp[i] = for j = 1..i - 1 if (dp[j] + a[i] c[j] < dp[i]) dp[i] = dp[j] + a[i] c[j] return dp[n]
Нетрудно видеть, что такая динамика работает за
.Ключевая идея оптимизации
Для начала сделаем замену обозначений. Давайте обозначим
за , за , а за .Теперь формула приняла вид
. Выражение — это в точности уравнение прямой вида .Сопоставим каждому
, обработанному ранее, прямую . Из условия « убывают уменьшаются с номером » следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :Выделим множество точек
, таких что все они принадлежат одной из прямых и при этом нету ни одной прямой , такой что . Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней огибающей множества прямых на плоскости). Назовем ее « ». Видно, что множество точек представляет собой выпуклую вверх функцию.Цель нижней огибающей множества прямых
Пусть мы считаем динамику для бинарным поиском. Это потребует времени на поиск такого , что . Теперь осталось научиться поддерживать множество прямых и быстро добавлять -ю прямую после того, как мы посчитали .
-го дерева. Его задает . Итак, нам нужно для данного найти . Это выражение есть . Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координатам x следует то, что отрезок, который пересекает прямую , можно найтиВоспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека
и , которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую ( -тую) прямую в множество. Пусть сейчас в множестве лежит прямых (нумерация с 1). Пусть — точка пересечения -й прямой множества и -й, а — точка пересечения новой прямой, которую мы хотим добавить в конец множества и -й. Нас будут интересовать только их -овые координаты и , соответственно. Если оказалось, что новая прямая пересекает -ю прямую выпуклой оболочки позже, чем -я -ю, т.е. , то -ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо число прямых в стеке не станет равным 2, либо не станет меньшеАсимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно
раз добавится в стек и максимум раз удалится. Значит время работы перестройки выпуклой оболочки займет суммарно.Теорема: |
Алгоритм построения нижней огибающей множества прямых корректен. |
Доказательство: |
Достаточно показать, что последнюю прямую нужно удалить из множества Пусть , когда наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю. — уравнение новой прямой, — уравнения прямых множества. Тогда т.к. , то при , а т.к. , то при . Если , то при , т.е. на отрезке прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же , то она ниже всех на отрезке , т.е. её можно удалить из множества. |
Детали реализации:
Будем хранить 2 массива :
— -координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при ) и — номера деревьев, соответствующих прямым (т.е. -я прямая множества, где соответствует дереву номер ). Также воспользуемся тем, что возрастают (по условию задачи), а значит мы можем искать первое такое , что не бинарным поиском, а методом двух указателей за операций суммарно. Также массив можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые , а значит если -я прямая пересекается с -й в точке ( -целое, ), то мы будем подставлять в их уравнения или . Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная сРеализация
int(int a[n], int c[n]) st[1] = 1 front[1] = - // первая прямая покрывает все x-ы, начиная с -∞ sz = 1 // текущий размер выпуклой оболочки pos = 1 // текущая позиция первого такого j, что x[i] \geqslant front[st[j]] for i = 2..n while (front[pos] < x[i]) // метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой pos = pos + 1 j = st[pos] dp[i] = K[j] a[i] + B[j] if (i < n) // если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку K[i] = c[i] // наши переобозначения переменных B[i] = dp[i] // наши переобозначения переменных x = - while true j = st[sz] x = divide(B[j] - B[i], K[i] - K[j]) // x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) if (x > from[sz]) break // перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" sz = sz - 1// удаляем последнюю прямую, если она лишняя st[sz + 1] = i front[sz + 1] = x // добавили новую прямую sz = sz + 1 return dp[n]
Здесь функция
возвращает нужное(*) округление . Приведем её код :int
(int a, int b)
delta = 0
if (a mod b ≠ 0) delta = 1
if ((a > 0 and b > 0) or (a < 0 and b < 0)) return [a / b] + delta
return -[|a| / |b|]
Такая реализация будет работать за
.Динамический convex hull trick
Заметим, что условия на возрастание/убывание [2]).
на убывание/возрастание и выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, с помощью которой мы за
можем найти , но теперь вставку -й прямой в оболочку уже нельзя выполнить описанным ранее способом за в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при , где - точки пересечения с некоторыми прямыми, причем не обязательно равноЧтобы уметь вставлять прямую в множество будем хранить двоичное дерево поиска, в вершинах которого будут пары = (коэффицент прямой, ее номер в глобальной нумерации). Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает . Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).
Асимптотика решения составит
на каждый из запросов «добавить прямую» + суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает времени. Итого .Альтернативный подход
Другой способ интерпретировать выражение
заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : , т.е. запишем как скалярное произведение векторов и . Вектора хотелось бы организовать так, чтобы за находить вектор, максимизирующий выражение . Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) не может давать более оптимальное значение одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов , а ответ на запрос — это поиск , максимизирующего проекцию на . Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из в ). Ее можно решить за двумя бинарными или одним тернарным поиском Асимптотика алгоритма по-прежнему составитДокажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются
вектора , расположенные как на рис. 5, т.е. точка не лежит на выпуклой оболочке векторов : , то либо оптимальнее, чем , либо оптимальнее, чем .Теорема: |
Если есть вектора , таких что то либо , либо , где вектор . |
Доказательство: |
По условию теоремы известно, что Подставим эти неравенства в (*). Получим цепочку неравенств : (*). Предположим (от противного), что и при этом . . Получили противоречие : . Значит предположение неверно, чтд. |
Из доказанной теоремы и следует корректность алгоритма.