Изменения
→Пример задачи, решаемой методом convex hull trick
Convex hull trick {{---}} один из методов оптимизации [[Динамическое_программирование | динамического программирования]], использующий идею [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклой оболочки]]. Позволяет улучшить асимптотику решения некоторых задач, решемых методом динамического программирования, с <math>O(n^2)</math> до <tex>O(n\cdot\log(n))</tex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002. ==Постановка примера Пример задачи, решаемой методом convex hull trick==Рассмотрим задачу на ДП:{{Задача|definition = Есть <math>n </math> деревьев с высотами <mathtex>a1a_1, a2a_2, … an\dots, a_n</mathtex>(в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку бензопилы. Но пила устроена так, что она может спиливать только по <math>1</math> метру от дерева, к которому ее применили. Также после уменьшения высоты спиливаемого срубленного метра (любого дерева на 1 ее надо заправить) пилу нужно заправлять, платя за бензин определенное кол-во монет. Причем стоимость заправки бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки равна ci<tex>c_i</tex>. Изначально пила заправлена.И Также известны следующие ограничения : <mathtex>c[n] c_n = 0, a[1] a_1 = 1, a[i]a_i</mathtex> возрастают, <mathtex>c[i]c_i</mathtex> убывают. Изначально пила заправлена.(убывание и возрастание нестрогие)}}(Задача H с codeforcesСанкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.compdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>)</noinclude><includeonly>{{#if: {{{neat|}}}|<div style="background-color: #fcfcfc; float:left;"><div style="background-color: #ddd;">'''Задача:'''</div><div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div></div>|<table border="0" width="100%"><tr><td style="background-color: #ddd">'''Задача:'''</td></tr><tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr></table>}}</includeonly>
==Наивное решение==
Сначала заметим важный факт : т.к. <tex>c[i]</tex> убывают (нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i]</tex> неотрицательны.Понятно, что нужно затратив минимальную стоимость срубить последнее (<mathtex>n</mathtex>-е) дерево, т.к. после него все деревья можно будет пилить рубить бесплатно (т.к. <mathtex>c[n] = 0</mathtex>). Посчитаем следующую динамику : <mathtex>dp[i]</mathtex> {{--- }} минимальная стоимость, заплатив которую будет срублено можно добиться того, что дерево номер <mathtex>i.</mathtex> Тогда будет срублено.База динамики : <mathtex>dp[i1] = min_{j=0</tex>, т.к..i-изначально пила заправлена и высота первого дерева равна <math>1}(dp[j] + a[i] * c[j])</math>, по условию задачи. То есть Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешвые дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадных алгоритмов]], чем к теме данной статьи). Тогда переберем Поэтому перед <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <mathtex>j \leqslant i - 1< /tex>. Поэтому чтобы найти <tex>dp[i]</mathtex> нужно перебрать все <tex> 1 \leqslant j \leqslant i - индекс предыдущего срубленного 1</tex> и попытаться использовать ответ для дереваномер <tex>j</tex>. Пусть Итак, пусть перед <tex>i</tex>-м деревом мы его полностью срубили отптимальным (в смысле денег) способом. Тогда просто <mathtex>j</tex>-е, причем высота <tex>i</tex>-го дерева составляет <tex>a[i]</mathtex>, а т.к. последнее дерево, которое мы срубили, имеет индекс <tex>j</tex>, то стоимость каждого метра <tex>i</tex> раз уменьшим высоту -го дерева i на 1. Каждый такой раз будем платить составит <mathtex>c[j]</mathtex> за последующую заправку пилы. Итак, Поэтому на сруб <mathtex>i</mathtex>-го дерева мы заплатили потратим <tex>a[i] \cdot c[j]<math/tex> монет. Также не стоит забывать, что ситуацию, когда <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет.Итоговая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i]*\cdot c[j])</tex>. Посмотрим на код вышеописанного решения: '''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n]) dp[1] = 0 dp[2] = dp[3] = ... = dp[n] = <tex>\infty</mathtex> '''for''' i = 2 = 1..n dp[i] = <tex>+\infty</tex> '''for''' j = 1..
Нетрудно i - 1 '''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i]) dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j] '''return''' dp[n]Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>. ==Ключевая идея оптимизации==Для начала сделаем замену обозначений. Давайте обозначим <tex>dp[j]</tex> за <tex>b[j]</tex>, <tex>a[i]</tex> за <tex>x[i]</tex>, а <tex>c[j]</tex> за <tex>k[j]</tex>. Теперь формула приняла вид <tex>dp[i] = \min\limits_{j=0...i-1}(k[j] \cdot x[i] + b[j])</tex>. Выражение <tex>k[j] \cdot x + b[j]</tex> {{---}} это в точности уравнение прямой вида <tex>y = kx + b</tex>. Сопоставим каждому <tex>j</tex>, обработанному ранее, прямую <tex>y[j](x) = k[j] \cdot x + b[j]</tex>. Из условия «<tex>c[i]</tex> убывают <tex>\Leftrightarrow k[j]</tex> уменьшаются с номером <tex>j</tex>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых : [[Файл:picture1convexhull.png]] Выделим множество точек <tex>(x_0, y_0)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x_0) < y_0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней огибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек <math>(x, convex(x))</math> представляет собой выпуклую вверх функцию. ==Цель нижней огибающей множества прямых==Пусть мы считаем динамику для <tex>i</tex>-го дерева. Его задает <tex>x[i]</tex>. Итак, нам нужно для данного <tex>x[i]</tex> найти <tex>\min\limits_{j=0..i-1}(k[j] \cdot x[i] + b[j]) = \min\limits_{j=0..i-1}(y[j](x[i]))</tex>. Это выражение есть <math>convex(x[i])</math>. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координатам x следует то, что отрезок, который пересекает прямую <tex>x = x[i]</tex>, можно найти [[Целочисленный_двоичный_поиск|бинарным поиском]]. Это потребует <tex>O(\log(n^))</tex> времени на поиск такого <tex>j</tex>, что <tex>dp[i] = k[j] \cdot x[i] + b[j]</tex>. Теперь осталось научиться поддерживать множество прямых и быстро добавлять <tex>i</tex>-ю прямую после того, как мы посчитали <tex>b[i] = dp[i]</tex>. Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2стека <tex>k[]</tex> и <tex>b[]</tex>, которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую (<tex>i</tex>-тую)прямую в множество. Пусть сейчас в множестве лежит <tex>sz</tex> прямых (нумерация с 1). Пусть <tex>(x_L, y_L)</tex> {{---}} точка пересечения <tex>sz - 1</tex>-й прямой множества и <tex>sz</tex>-й, а <tex>(x_R, y_R)</tex> {{---}} точка пересечения новой прямой, которую мы хотим добавить в конец множества и <tex>sz</tex>-й. Нас будут интересовать только их <tex>x</tex>-овые координаты <tex>x_L</tex> и <tex>x_R</tex>, соответственно. Если оказалось, что новая прямая пересекает <tex>sz</tex>-ю прямую выпуклой оболочки позже, чем <tex>sz</tex>-я <tex>sz - 1</tex>-ю, т.е. <tex>(x_L \geqslant x_R)</tex>, то <tex>sz</tex>-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо число прямых в стеке не станет равным 2, либо <tex>x_L</tex> не станет меньше <tex>x_R.</tex> Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
{{Теорема|id=th1239. |statement=Для чего нам нужна эта выпуклая оболочка Алгоритм построения нижней огибающей множества прямых?корректен.|proof== Пусть мы считаем динамику для Достаточно показать, что последнюю прямую нужно удалить из множества <mathtex>i\Leftrightarrow</mathtex>, когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя -го деревапредпоследнюю. Его задает Пусть <mathtex>Y(x[i]) = Kx + B</mathtex>. Итак{{---}} уравнение новой прямой, нам нужно для данного <mathtex>xy[i]</math> найти минимум по всем <math>min_{j=0..i-1}(k[j]*x[i] + b[i]) = min_{j=0..K[i-1}(y[j](x+ B[i]))</mathtex>{{---}} уравнения прямых множества. Тогда т. Нетрудно видеть, что это есть convex(x[i])к. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <mathtex>x = xK < K[isz]</mathtex>, можно найти бинарным поиском. Это потребует O(logn) времени на поиск такого j, что dpто при <tex>x \in [i- \infty; x_R] = k : y[jsz] * (x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять ) <math>i= Y(x)</mathtex>-ю прямую после того, как мы посчитали а т.к. <mathtex>bK[isz] = dp< K[isz - 1]</mathtex>. Название статьи подсказывает, что нужно воспользоваться алгоритмом построения выпуклой оболочки множества точек. Но (внезапно) у нас не точки, а прямые… Но что меняется??? Пусть есть 2 стека то при <mathtex>kx \in [x_L; + \infty] и b : y[sz - 1](x) \geqslant y[sz]</math>, которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их <math/tex>xL. Если </mathtex> и x_L <math>xRx_R</math>. Если оказалось, что новая прямая пересекает предпосл еднюю прямую выпуклой оболочки позже, чем последнюю (xL tex>= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или при <mathtex>xL</math> не станет меньше <math>xR.</math> Ассимптотика x \in [x_L; x_R] : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно y[sz - 1 раз добавится в стек ] \geqslant y[sz](x) и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет <math>OY(x) \geqslant y[sz](nx)</mathtex> суммарно. Корректность : достаточно показать, что прямую нужно удалить из множества т.и те.т., когда она последнюю прямую множества наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю. Действительно, пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то найдется такой отрезок на отрезке <mathtex>[x1x_L;x2x_R]</mathtex>, что последняя(желтая) прямая при этих x-ах номер sz лежит ниже всех остальных и ее следует её нужно оставить в множестве. Теперь пусть новая прямая пересекает последнюю прямую множества раньшеЕсли же <tex>x_L > x_R</tex>, то она ниже всех на отрезке <tex>[x_L; x_R] = \varnothing </tex>, чем предпоследнюю (рист.е.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее её можно удалить, чтдиз множества.}}
==Детали реализации:==
==Р.Реализация== '''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n]) st[01] = 01 from front[01] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞</font> sz = 1 <font color=green>// текущий размер выпуклой оболочки</font> pos = 0 1 <font color=green>// текущая позиция первго первого такого j, что x[i] >= \geqslant front[st[j]]</font > '''for ''' i = 12..n-1 { '''while ''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font > pos = pos ++pos1 j = st[pos] dp[i] = K[j] * <math>\cdot</math> a[i] + B[j] '''if ''' (i < n - 1) <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font > K[i] = bc[i] <font color=green>// наши переобозначения переменных </font > B[i] = dp[i]<font color=green>// наши переобозначения переменных </font > x = -inf<tex>\infty</tex> '''while (1) {''' ''true'' j = st[sz - 1] x = divide(B[j] - B[i], K[i] - K[j])<font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font > '''if ''' (x > from[sz - 1]) '''break''' <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font > sz = sz --sz }1<font color=green>// удаляем последнюю прямую, если она лишняя </font > st[sz+ 1] = i from front[sz++1] = x<font color=green>// добавили новую прямую </font > sz = sz + 1 } '''return''' dp[n] (Здесь функция <tex>\mathtt{divide(a, b) }</tex> возвращает нужное (*) округление <tex>\frac{a }{b}</ tex>. Приведем её код : '''int''' <tex>\mathtt{divide}</tex>('''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|] Такая реализация будет работать за <math>O(n)</math>.
==Динамический convex hull trick==
Заметим, что условия на прямые, что возрастание/убывание <mathtex>k[i]</mathtex> возрастаетна убывание/убывает возрастание и <mathtex>x[i]</mathtex> убывает/возрастает выглядят не достаточно общимиредкими для большинства задач. Как же быть, если Пусть в задаче таких ограничений нет. Иногда можно Первый способ борьбы с этой проблемой - отсортировать прямые входные данные нужным образом, не испортив свойств задачи (пример : задача G отсюда c Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdfСайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>). Но рассмотрим общий случай. Наша задача поменялась следующим образом : поПо-прежнему у нас есть выпуклая оболочкапрямых, имея которую с помощью которой мы за <mathtex>O(logn\log(n))</mathtex> или быстрее можем найти <mathtex>dp[i]</mathtex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить старым описанным ранее способом за <mathtex>O(1)</mathtex> (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4: красная прямая - та, которую мы хотим вставить в наше множество). Т.е. нужно уметь быстро (за Более формально : теперь наша новая прямая будет ниже остальных при <mathtex>O(logn)x \in [x_1; x_2]</mathtex>?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) примую и удалять лишние справагде <tex>x_1, начиная x_2 \in R</tex> - точки пересечения с неенекоторыми прямыми, потом проводить аналогичные операции слева. Итак, давайте хранить причем <tex>x_2</tex> не обязательно равно <mathtex>std::set+ \infty</mathtex> (или любой аналог [[Файл:picture4convexhull.png]] Чтобы уметь вставлять прямую в множество будем хранить [[Красно-черное_дерево|двоичное дерево поиска]], в других языках) пар вершинах которого будут пары <mathtex><(k, st>)</mathtex> = <math><(коэффицент прямой, ее номер в глобальной нумерации></math>). Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую последнюю прямую с меньшим углом наклонаугловым коэффицентом, и начиная чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(\log(n))</tex>. Начиная с нее повторяем найденной прямой выполняем "старый " алгоритм (удаляем, пока текущая прямая бесполезнаямножества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей(удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа). Ассимптотика Асимптотика решения составит <mathtex>O(logn\log(n))</mathtex> на каждый из <tex>n </tex> запросов «добавить прямую» + <mathtex>O(n\cdot\log(n))</mathtex> суммарно на удаление прямых, т.к. Итго по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает <tex>O(\log(n))</tex> времени. Итого <math>O(nlognn\cdot\log(n))</math>.
== Альтернативный подход ==