Convex hull trick — различия между версиями
(→Наивное решение) |
(→Наивное решение) |
||
Строка 30: | Строка 30: | ||
База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи. | База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи. | ||
Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <tex>j < i</tex>. Поэтому чтобы найти <tex>dp[i]</tex> нужно перебрать все <tex>1 \leqslant j < i</tex> и попытаться использовать ответ для дерева намер <tex>j</tex>. Итак, пусть перед <tex>i</tex>-м деревом мы полностью срубили <tex>j</tex>-е, причем высота <tex>i</tex>-го дерева составляет <tex>a[i]</tex>, а т.к. последнее дерево, которое мы срубили имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex>-го дерева составит <tex>c[j]</tex>. Поэтому на сруб <tex>i</tex>-го дерева мы потратим <tex>a[i] * c[j]</tex> монет. Также не стоит забывать, ситуацию, когда <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет. | Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <tex>j < i</tex>. Поэтому чтобы найти <tex>dp[i]</tex> нужно перебрать все <tex>1 \leqslant j < i</tex> и попытаться использовать ответ для дерева намер <tex>j</tex>. Итак, пусть перед <tex>i</tex>-м деревом мы полностью срубили <tex>j</tex>-е, причем высота <tex>i</tex>-го дерева составляет <tex>a[i]</tex>, а т.к. последнее дерево, которое мы срубили имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex>-го дерева составит <tex>c[j]</tex>. Поэтому на сруб <tex>i</tex>-го дерева мы потратим <tex>a[i] * c[j]</tex> монет. Также не стоит забывать, ситуацию, когда <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет. | ||
− | Итогвая формула пересчета : <tex>dp[i] = \ | + | Итогвая формула пересчета : <tex>dp[i] = \min_{j=1...i-1} (dp[j] + a[i] * c[j])</tex>. |
Посмотрим на код выше описанного решения: | Посмотрим на код выше описанного решения: |
Версия 00:46, 18 января 2017
Convex hull - выпуклая оболочка; Convex hull trick - один из методов оптимизации динамического программирования, использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задач, решемых методом динамического программирования с
до . Техника впервые появилась в 1995 году (задачу на нее предложили в USACO - национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002Содержание
Пример задачи, решаемой методом convex hull trick
Рассмотрим задачу на ДП:
Задача: |
Есть n деревьев с высотами бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенной кол-во монет. Причем стоимость бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки равна ci. Изначально пила заправлена. Также известны следующие ограничения : (убывание и возрастание нестрогие) возрастают, убывают. Изначально пила заправлена. | (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
(Задача H с Санкт-Петербургских сборов к РОИ [1])
Наивное решение
Сначала заметим важный факт : т.к.
убывают (нестрого) и , то все неотрицательны. Понятно, что нужно затратив минимальную стоимость срубить последнее ( -е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. ). Посчитаем следующую динамику : - минимальная стоимость, заплатив которую можно добиться того, что дерево номер будет срублено. База динамики : , т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи. Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед -м деревом мы обязательно срубили какое-то -е, причем . Поэтому чтобы найти нужно перебрать все и попытаться использовать ответ для дерева намер . Итак, пусть перед -м деревом мы полностью срубили -е, причем высота -го дерева составляет , а т.к. последнее дерево, которое мы срубили имеет индекс , то стоимость каждого метра -го дерева составит . Поэтому на сруб -го дерева мы потратим монет. Также не стоит забывать, ситуацию, когда -е дерево полностью срублено, мы получили не бесплатно, а за монет. Итогвая формула пересчета : .Посмотрим на код выше описанного решения:
int simple-dp(int a[], int c[], int n) dp[1] = 0 dp[2] = dp[3] = ... = dp[n] =for i = 1..n-1 { dp[i] = + for j = 0..i-1 { if (dp[j] + a[i] * c[j] < dp[i]) dp[i] = dp[j] + a[i] * c[j] } } return dp[n]
Нетрудно видеть, что такая динамика работает за
.Ключевая идея оптимизации
1) Сделаем замену обозначений. Давайте обозначим
за , за , а за .2) Теперь формула приняла вид
. Выражение - это в точности уравнение прямой вида .3) Сопоставим каждому
, обработанному ранее, прямую . Из условия « убывают уменьшаются с номером » следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :4) Выделим множество точек
, таких что все они принадлежат одной из прямых и при этом нету ни одной прямой , такой что . Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее « ». Видно, что множество точек (x, convex(x)) представляет собой выпуклую вверх функцию.Для чего нужна нижняя огибающая множества прямых
Пусть мы считаем динамику для
-го дерева. Его задает . Итак, нам нужно для данного найти . Это выражение есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую , можно найти бинарным поиском. Это потребует времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться поддерживать множество прямых и быстро добавлять -ю прямую после того, как мы посчитали .Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека
и , которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую ( -тую) прямую в множество. Пусть сейчас в множестве лежит прямых (нумерация с 1). Пусть - точка пересечения -й прямой множества и -й, а - точка пересечения новой прямой, которую мы хотим добавить в конец множества и -й. Нас будут интересовать только их -овые координаты и , соответственно. Если оказалось, что новая прямая пересекает -ю прямую выпуклой оболочки позже, чем -я -ю, т.е. , то -ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо не станет меньшеАсимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет
суммарно.Корректность : достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.
Доказательство : Пусть
- уравнение новой прямой, - уравнения прямых множества. Тогда т.к. , то при , а т.к. , то при . Если , то при , т.е. на отрезке прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же , то она ниже всех на отрезке , т.е. её можно удалить из множестваДетали реализации:
Будем хранить 2 массива :
- -координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при ) и - номера деревьев, соответствующих прямым (т.е. -я прямая множества, где соответствует дереву номер ). Также воспользуемся тем, что возрастают (по условию задачи), а значит мы можем искать первое такое , что не бинарным поиском, а методом двух указателей за операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые , а значит если -я прямая пересекается с -й в точке (z-целое, ), то мы будем подставлять в их уравнения или . Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная сРеализация
void Convex-hull-trick st[1] = 1 from[1] = -// первая прямая покрывает все x-ы, начиная с -∞ sz = 1 // текущий размер выпуклой оболочки pos = 1 // текущая позиция первого такого j, что x[i] >= 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 from[sz + 1] = x // добавили новую прямую sz = sz + 1 } }
Здесь функция divide(a, b) возвращает нужное(*) округление a / b. Приведем её код :
int divide (a, 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|]
Такая реализация будет работать за O(n).
Динамический convex hull trick
Заметим, что условия на прямые, что http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).
возрастает/убывает и убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G отсюда Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за
Чтобы уметь вставлять прямую в множество будем хранить
(или любой аналог в других языках программирования) пар = . Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает . Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).Асимптотика решения составит
на каждый из запросов «добавить прямую» + суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает времени. Итого .Альтернативный подход
Другой способ интерпретировать выражение
заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : , т.е. запишем как скалярное произведение векторов и . Вектора хотелось бы организовать так, чтобы за находить вектор, максимизирующий выражение . Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) не может давать более оптимальное значение одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов , а ответ на запрос - это поиск , максимизирующего проекцию на . Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из (1, a[i])</tex>). Ее можно решить за двумя бинарными или одним тернарным поиском Асимптотика алгоритма по-прежнему составитДоказательство : необходимо показать, что если есть 3 вектора a, b, c, расположенные как на рисунке 5 (т.е.
, где - модуль векторного произведения векторов и ), то либо (a, u[i]) \leqslant (b, u[i]), либо (c, u[i]) \leqslant (b, u[i]).Распишем условие того, что точка b не лежит на выпуклой оболочке векторов
: (*). Предположим (от противного), что и .Подставим эти неравенства в (*). Получим цепочку неравенств :
. Получили противоречие : . Значит предположение неверно, чтд.