Convex hull trick — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Наивное решение)
м (rollbackEdits.php mass rollback)
 
(не показано 175 промежуточных версий 9 участников)
Строка 1: Строка 1:
==Что такое 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 - выпуклая оболочка; Convex hull trick - один из методов оптимизации динамического программирования, использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задач, решемых методом динамического программирования с <math>O(n^2)</math> до <math>O(n*logn)</math>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO - национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002
 
  
==Постановка примера задачи==
+
==Пример задачи, решаемой методом convex hull trick==
 
Рассмотрим задачу на ДП:
 
Рассмотрим задачу на ДП:
  Есть n деревьев с высотами <math>a1, a2, \dots an</math> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
+
{{Задача
  бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
+
|definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, \dots, a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
  срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенной кол-во монет. Причем стоимость  
+
бензопилы. Но пила устроена так, что она может спиливать только по <math>1</math> метру от дерева, к которому ее применили. Также после
  бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки  
+
срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенное кол-во монет. Причем стоимость  
  равна ci.  Изначально пила заправлена.
+
бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки  
  Также известны следующие ограничения : <math>c[n] = 0, a[1] = 1, a[i]</math> возрастают, <math>c[i]</math> убывают. Изначально пила заправлена.
+
равна <tex>c_i</tex>.  Изначально пила заправлена.
  (убывание и возрастание нестрогие)
+
Также известны следующие ограничения : <tex>c_n = 0, a_1 = 1, a_i</tex> возрастают, <tex>c_i</tex> убывают. Изначально пила заправлена.
(Задача H отсюда : http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf)
+
(убывание и возрастание нестрогие)
 +
}}
 +
(Задача H с Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 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>
  
 
==Наивное решение==
 
==Наивное решение==
Сначала заметим важный факт : т.к. c[i] убывают(нестрого) и c[n] = 0, то все c[i] неотрицательны.
+
Сначала заметим важный факт : т.к. <tex>c[i]</tex> убывают (нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i]</tex> неотрицательны.
Понятно, что нужно затратив минимальную стоимость срубить последнее (<math>n</math>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <math>c[n] = 0</math>). Посчитаем следующую динамику : <math>dp[i]</math> - минимальная стоимость, заплатив которую можно добиться того, что дерево номер <math>i.</math> будет срублено.  
+
Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c[n] = 0</tex>). Посчитаем следующую динамику : <tex>dp[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i</tex> будет срублено.
База динамики : <math>dp[1] = 0</math>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.
+
База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна <math>1</math>, по условию задачи.
Переход динамики :  понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед  <math>i</math>-м деревом мы обязательно срубили какое-то <math>j</math>-е, причем <math>j < i</math>. Поэтому чтобы найти <math>dp[i]</math> нужно перебрать все <math>1 <= j < i</math> и попытаться использовать ответ для дерева намер <math>j</math>. Итак, пусть перед <math>i</math>-м деревом мы полностью срубили <math>j</math>-е, причем высота <math>i</math>-го дерева составляет <math>a[i]</math>, а т.к. последнее дерево, которое мы срубили имеет индекс <math>j</math>, то стоимость каждого метра <math>i</math>-го дерева составит <math>c[j]</math>.  Поэтому на сруб <math>i</math>-го дерева мы потратим <math>a[i] * c[j]</math> монет. Также не стоит забывать, ситуацию, когда  <math>j</math>-е дерево полностью срублено, мы получили не бесплатно, а за <math>dp[j]</math> монет.
+
Переход динамики :  понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадных алгоритмов]], чем к теме данной статьи). Поэтому перед  <tex>i</tex>-м деревом мы обязательно срубили какое-то <tex>j</tex>-е, причем <tex>j \leqslant i - 1</tex>. Поэтому чтобы найти <tex>dp[i]</tex> нужно перебрать все <tex>1 \leqslant j \leqslant i - 1</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] \cdot c[j]</tex> монет. Также не стоит забывать, что ситуацию, когда  <tex>j</tex>-е дерево полностью срублено, мы получили не бесплатно, а за <tex>dp[j]</tex> монет.
Итогвая формула пересчета : <math>dp[i] = min_{j=0...i-1}(dp[j] + a[i] * c[j])</math>. 

+
Итоговая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[j])</tex>.
Посмотрим на код выше описанного решения:
 
dp[1] = 0
 
dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
 
''for''  i = 1..n-1  {
 
        dp[i] = +<tex>\infty</tex>
 
        ''for'' j = 0..i-1 {
 
              ''if'' (dp[j] + a[i] * c[j] < dp[i])
 
                      dp[i] = dp[j] + a[i] * c[j]
 
        }
 
  }
 
Нетрудно видеть, что такая динамика работает за <math>O(n^2)</math>.
 
  
==О-Оптимизация==
+
Посмотрим на код вышеописанного решения:
Давайте обозначим <math>dp[j]</math> за <math>b[j]</math>, <math>a[i]</math> за <math>x[i]</math>, а <math>c[j]</math> за <math>k[j]</math>.
+
'''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n])
Теперь формула приняла вид <math>dp[i] = min_{j=0...i-1}(k[j]*x[i] + b[j])</math>. Выражение <math>k[j]*x + b[j]</math> напоминает уравнение прямой <math>y = kx + b</math>. Сопоставим каждому <math>j</math>, обработанному ранее прямую <math>y[j](x) = k[j]*x + b[j]</math>. Из условия «<math>c[i]</math> убывают <math><=>  k[j]</math> уменьшаются с номером <math>j</math>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :
+
    dp[1] = 0
 +
    dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
 +
    '''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]]
 
[[Файл:picture1convexhull.png]]
  
Итак, давайте выделим множество точек <math>(x0, y0)</math> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <math>y’(x)</math>, такой что <math>y’(x0) < y0</math>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых. На картинке множество точек выделено жирным оранжевым цветом и представляет собой выпуклую вверх функцию. Назовем ее «<math>y = convex(x)</math>»
+
Выделим множество точек <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> представляет собой выпуклую вверх функцию.
  
==Для чего нам нужна эта выпуклая оболочка прямых?==
+
==Цель нижней огибающей множества прямых==
Пусть мы считаем динамику для <math>i</math>-го дерева. Его задает <math>x[i]</math>. Итак, нам нужно для данного <math>x[i]</math> найти минимум по всем <math>min_{j=0..i-1}(k[j]*x[i] + b[i]) = min_{j=0..i-1}(y[j](x[i]))</math>. Нетрудно видеть, что это есть convex(x[i]). Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координаты x следует то, что отрезок, который пересекает прямую <math>x = x[i]</math>, можно найти бинарным поиском. Это потребует <math>O(logn)</math> времени на поиск такого j, что dp[i] = k[j] * x[i] + b[j]. Теперь осталось научиться быстро поддерживать множество прямых и добавлять <math>i</math>-ю прямую после того, как мы посчитали <math>b[i] = dp[i]</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 стека <math>k[] и b[]</math>, которые задают прямые в отсортированном порядке. Пусть пришла новая прямая. Найдем точки пересечения (по x) с последними 2мя прямыми из стека. Назовем их <math>xL</math> и <math>xR</math>. Если оказалось, что новая прямая пересекает предпоследнюю прямую выпуклой оболочки позже, чем последнюю (xL >= xR), то последнюю можно удалить из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2 или <math>xL</math> не станет меньше <math>xR.</math>
+
 
Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно 1 раз добавится в стек и максимум 1 раз удалится. Значит время работы перестройки выпуклой оболочки займет <math>O(n)</math> суммарно.
+
Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 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>
Корректность : достаточно показать, что прямую нужно удалить из множества т.и т.т., когда она последнюю прямую множества наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю.
+
 
[[Файл:picture2convexhull.png]]  
+
Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
 +
 
 +
[[Файл:picture2convexhull.png]]
 
[[Файл:picture3convexhull.png]]
 
[[Файл:picture3convexhull.png]]
  
Действительно, пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), то найдется такой отрезок <math>[x1;x2]</math>, что последняя(желтая) прямая при этих x-ах лежит ниже всех остальных и ее следует оставить в множестве.
+
{{Теорема
Теперь пусть новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1),  последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее можно удалить, чтд.
+
|id=th1239.
 +
|statement=Алгоритм построения нижней огибающей множества прямых корректен.
 +
|proof=Достаточно показать, что последнюю прямую нужно удалить из множества <tex>\Leftrightarrow</tex>, когда наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.
 +
 
 +
Пусть <tex>Y(x) = Kx + B</tex> {{---}} уравнение новой прямой, <tex>y[i](x) = K[i]x + B[i]</tex> {{---}} уравнения прямых множества. Тогда т.к. <tex>K < K[sz]</tex>, то при <tex>x \in [- \infty; x_R]  : y[sz](x) <= Y(x)</tex>, а т.к. <tex> K[sz] < K[sz - 1]</tex>, то при <tex>x \in [x_L; + \infty]  : y[sz - 1](x) \geqslant y[sz](x)</tex>. Если <tex>x_L < x_R</tex>, то при <tex>x \in [x_L; x_R]  : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)</tex>, т.е. на отрезке <tex>[x_L; x_R]</tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <tex>x_L > x_R</tex>, то она ниже всех на отрезке <tex>[x_L; x_R] = \varnothing </tex>, т.е. её можно удалить из множества.
 +
}}
  
 
==Детали реализации:==
 
==Детали реализации:==
Будем хранить 2 массива (имитирующих стеки) : <math>front[]</math> и <math>st[]</math> - начало (по x) соответствующей прямой выпуклой оболочки и номер этой прямой (в глобальной нумерации). Также воспользуемся тем, что <math>x[i] = a[i]</math> возрастают (по условию задачи), а значит мы можем искать первое такое <math>j</math>, что <math>x[i] >= front[j]</math> не бинарным поиском, а методом указателей за <math>O(n)</math> суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*). Почему так? На самом деле мы, считая динамику, подставляем в уравнения прямых только целые <math>x[i]</math>, а значит если <math>k</math>-я прямая пересекается с <math>k+1</math>-й в точке <math>z +</math> <tex>\alpha</tex> (z-целое,  <tex>\alpha</tex>  <tex>\in</tex> <math>[0;1)</math>), то мы будем подставлять <math>z</math>  или <math>z + 1</math>. Поэтому можно считать, что новая прямая имеет "область действия", начиная с <math>z+1</math>
+
Будем хранить 2 массива : <tex>front[]</tex> {{---}} <tex>x</tex>-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при <tex>x</tex> <tex>\in</tex> <tex>[front[i]; front[i + 1])</tex> ) и <tex>st[]</tex> {{---}} номера деревьев, соответствующих прямым (т.е. <tex>i</tex>-я прямая множества, где <tex>i</tex> <tex>\in</tex> <tex>[1; sz]</tex> соответствует дереву номер <tex>sz[i]</tex>). Также воспользуемся тем, что <tex>x[i] = a[i]</tex> возрастают (по условию задачи), а значит мы можем искать первое такое <tex>j</tex>, что <tex>x[i] \geqslant front[j]</tex> не бинарным поиском, а методом двух указателей за <tex>O(n)</tex> операций суммарно. Также массив <math>front[]</math> можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые <tex>x[i]</tex>, а значит если <tex>k</tex>-я прямая пересекается с <tex>k+1</tex>-й в точке <tex>z +</tex> <tex>\alpha</tex> (<math>z</math>-целое,  <tex>\alpha</tex>  <tex>\in</tex> <tex>[0;1)</tex>), то мы будем подставлять в их уравнения <tex>z</tex>  или <tex>z + 1</tex>. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с <tex>x = z+1</tex>
 +
 
 +
==Реализация==
 +
  '''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n])
 +
    st[1] = 1
 +
    front[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
 +
    sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
 +
    pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font >
 +
    '''for'''  i = 2..n 
 +
          '''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
 +
              pos = pos + 1
 +
          j = st[pos]
 +
          dp[i] = K[j] <math>\cdot</math> a[i] + B[j]
 +
          '''if''' (i < n)  <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
 +
                K[i] = c[i]  <font color=green>// наши переобозначения переменных </font >
 +
                B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
 +
                x = -<tex>\infty</tex>
 +
                '''while''' ''true''
 +
                      j = st[sz]
 +
                      x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
 +
                      '''if''' (x > from[sz]) '''break'''  <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font >
 +
                      sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
 +
                st[sz + 1] = i 
 +
                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>.
  '''void''' Convex-hull-trick
 
  st[0] = 0
 
  from[0] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
 
  sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
 
  pos = 0 <font color=green>// текущая позиция первого такого j, что x[i] >= front[st[j]] </font >
 
  '''for'''  i = 1..n-1  {
 
      '''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
 
            ++pos
 
      j = st[pos]
 
      dp[i] = K[j] * a[i] + B[j]
 
      '''if''' (i < n - 1) {  <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
 
            K[i] = c[i]  <font color=green>// наши переобозначения переменных </font >
 
              B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
 
              x = -<tex>\infty</tex>
 
            '''while''' (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 <font color=green>// удаляем последнюю прямую, если она лишняя </font >
 
              }
 
              st[sz] = i 
 
              from[sz++] = x <font color=green>// добавили новую прямую </font >
 
      }                     
 
  }         
 
(Здесь функция divide(a, b) возвращает нужное(*) округление a / b)
 
Такая реализация будет работать за O(n).
 
  
 
==Динамический convex hull trick==
 
==Динамический convex hull trick==
Заметим, что условия на прямые, что <math>k[i]</math> возрастает/убывает и <math>x[i]</math> убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf).
+
Заметим, что условия на возрастание/убывание <tex>k[i]</tex> на убывание/возрастание и <tex>x[i]</tex> выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>).
Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за <math>O(logn)</math> или быстрее можем найти <math>dp[i]</math>, но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за <math>O(1)</math> (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине (рис. 4).  
+
 
 +
Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, с помощью которой мы за <tex>O(\log(n))</tex> можем найти   <tex>dp[i]</tex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить описанным ранее способом за <tex>O(1)</tex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x_1; x_2]</tex>, где <tex>x_1, x_2 \in R</tex> - точки пересечения с некоторыми прямыми, причем <tex>x_2</tex> не обязательно равно <tex>+ \infty</tex>
 
[[Файл:picture4convexhull.png]]
 
[[Файл:picture4convexhull.png]]
  
Т.е. нужно уметь быстро (за <math>O(logn)</math>?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) прямую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить <math>std::set</math> (или любой аналог в других языках) пар <math><k, st></math> =  <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей.
+
Чтобы уметь вставлять прямую в множество будем хранить [[Красно-черное_дерево|двоичное дерево поиска]], в вершинах которого будут пары <tex>(k, st)</tex> =  (коэффицент прямой, ее номер в глобальной нумерации). Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(\log(n))</tex>. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).
Асимптотика решения составит <math>O(logn)</math> на каждый из n запросов «добавить прямую» + <math>O(n)</math> суммарно на удаление прямых. Итого <math>O(nlogn)</math>.
+
 +
Асимптотика решения составит <tex>O(\log(n))</tex> на каждый из <tex>n</tex> запросов «добавить прямую» + <tex>O(n\cdot\log(n))</tex> суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает <tex>O(\log(n))</tex> времени. Итого <math>O(n\cdot\log(n))</math>.
  
 
== Альтернативный подход ==
 
== Альтернативный подход ==
Другой способ интерпретировать выражение <math>dp[i] = min_{j=0...i-1}(c[j]*a[i] + dp[j])</math>  заключается в следующем: давайте перепишем выражение <math>dp[j] + a[i] * c[j] = (dp[j], c[j]) * (1, a[i])</math>, т.е. запишем как скалярное произведение векторов <math>v[j] = (dp[j], c[j])</math> и <math>u[i] = (1, a[i])</math>. Вектора <math>v[j] =  (dp[j], c[j])</math> хотелось бы организовать так, чтобы за <math>O(logn)</math> находить максимизирующий выражение <math>v[j] * u[i]</math>. Посмотрим на рис. 5. Заметим довольно очевидный факт : красная точка(вектор) <math>j</math> не может давать более оптимальное значение <math>v[j] * u[i]</math> одновременно чем обе синие точки, т.к. <math>v[j] * u[i]</math> - это на самом деле проекция вектора <math>v[j]</math> на <math>u[i]</math>. По этой причине нам достаточно оставить выпуклую оболочку векторов <math>v[j]</math>, а ответ на запрос - это поиск <math>v[j]</math>, максимизирующего проекцию на <math>u[i]</math>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <math>(0, 0)</math> в <math>(1, a[i])</math>).  Ее можно решить за O(logn) двумя бинарными или одним тернарным поиском
+
Другой способ интерпретировать выражение <tex>dp[i] = \min\limits_{j=0...i-1}(c[j] \cdot a[i] + dp[j])</tex>  заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : <tex>dp[j] + a[i] \cdot c[j] = (dp[j], c[j]) \cdot (1, a[i])</tex>, т.е. запишем как скалярное произведение векторов <tex>v[j] = (dp[j], c[j])</tex> и <tex >u[i] = (1, a[i])</tex >. Вектора <tex >v[j] =  (dp[j], c[j])</tex> хотелось бы организовать так, чтобы за <tex >O(\log(n))</tex> находить вектор, максимизирующий выражение <tex>v[j] \cdot u[i]</tex>. Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) <tex>j</tex> не может давать более оптимальное значение <tex>v[j] \cdot u[i]</tex> одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов <tex>v[j]</tex>, а ответ на запрос {{---}} это поиск <tex>v[j]</tex>, максимизирующего проекцию на <tex>u[i]</tex>. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из <tex>(0, 0)</tex> в <tex>(1, a[i])</tex>).  Ее можно решить за <tex>O(\log(n))</tex> двумя бинарными или одним тернарным поиском
Асимптотика алгоритма по-прежнему составит <math>O(n*log(n))</math>
+
Асимптотика алгоритма по-прежнему составит <tex>O(n \cdot \log(n))</tex>
  
 
[[Файл:picture5convexhull.png]]
 
[[Файл:picture5convexhull.png]]
 +
 +
Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <math>3</math> вектора <math>a, b, c</math>, расположенные как на рис. 5, т.е. точка <math>b</math> не лежит на выпуклой оболочке векторов <tex>0, a, b, c </tex> : <tex> \Leftrightarrow [a-b, b-c] < 0 </tex>, то либо  <tex>(a, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>,  либо <tex>(c, u[i])</tex> оптимальнее, чем <tex>(b, u[i])</tex>.
 +
{{Теорема
 +
|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>.
 +
|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>. Значит предположение неверно, чтд.
 +
}}
 +
 +
Из доказанной теоремы и следует корректность алгоритма.
 +
 +
==См. также==
 +
 +
*[[:Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|Выпуклая оболочка]]
 +
 +
*[[:Динамическое_программирование|Динамическое программирование]]
 +
 +
== Примечания ==
 +
<references/>
 +
 +
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория: Динамическое программирование]]
 +
[[Категория: Способы оптимизации методов динамического программирования]]

Текущая версия на 19:21, 4 сентября 2022

Convex hull trick — один из методов оптимизации динамического программирования, использующий идею выпуклой оболочки. Позволяет улучшить асимптотику решения некоторых задач, решемых методом динамического программирования, с [math]O(n^2)[/math] до [math]O(n\cdot\log(n))[/math]. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO — национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.

Пример задачи, решаемой методом convex hull trick

Рассмотрим задачу на ДП:

Задача:
Есть [math]n[/math] деревьев с высотами [math]a_1, a_2, \dots, a_n[/math] (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку

бензопилы. Но пила устроена так, что она может спиливать только по [math]1[/math] метру от дерева, к которому ее применили. Также после срубленного метра (любого дерева) пилу нужно заправлять, платя за бензин определенное кол-во монет. Причем стоимость бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен [math]i[/math], то цена заправки равна [math]c_i[/math]. Изначально пила заправлена. Также известны следующие ограничения : [math]c_n = 0, a_1 = 1, a_i[/math] возрастают, [math]c_i[/math] убывают. Изначально пила заправлена.

(убывание и возрастание нестрогие)

(Задача H с Санкт-Петербургских сборов к РОИ 2016 [1])


Наивное решение

Сначала заметим важный факт : т.к. [math]c[i][/math] убывают (нестрого) и [math]c[n] = 0[/math], то все [math]c[i][/math] неотрицательны. Понятно, что нужно затратив минимальную стоимость срубить последнее ([math]n[/math]-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. [math]c[n] = 0[/math]). Посчитаем следующую динамику : [math]dp[i][/math] — минимальная стоимость, заплатив которую можно добиться того, что дерево номер [math]i[/math] будет срублено. База динамики : [math]dp[1] = 0[/math], т.к. изначально пила заправлена и высота первого дерева равна [math]1[/math], по условию задачи. Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмов, чем к теме данной статьи). Поэтому перед [math]i[/math]-м деревом мы обязательно срубили какое-то [math]j[/math]-е, причем [math]j \leqslant i - 1[/math]. Поэтому чтобы найти [math]dp[i][/math] нужно перебрать все [math]1 \leqslant j \leqslant i - 1[/math] и попытаться использовать ответ для дерева номер [math]j[/math]. Итак, пусть перед [math]i[/math]-м деревом мы полностью срубили [math]j[/math]-е, причем высота [math]i[/math]-го дерева составляет [math]a[i][/math], а т.к. последнее дерево, которое мы срубили, имеет индекс [math]j[/math], то стоимость каждого метра [math]i[/math]-го дерева составит [math]c[j][/math]. Поэтому на сруб [math]i[/math]-го дерева мы потратим [math]a[i] \cdot c[j][/math] монет. Также не стоит забывать, что ситуацию, когда [math]j[/math]-е дерево полностью срублено, мы получили не бесплатно, а за [math]dp[j][/math] монет. Итоговая формула пересчета : [math]dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[j])[/math].

Посмотрим на код вышеописанного решения:

int [math]\mathtt{simpleDP}[/math](int a[n], int c[n])
   dp[1] = 0
   dp[2] = dp[3] = ... = dp[n] = [math]\infty[/math]
   for i = 2 = 1..n  
      dp[i] = [math]+\infty[/math]
      for j = 1..i - 1 
          if (dp[j] + a[i] [math]\cdot[/math] c[j] < dp[i])
              dp[i] = dp[j] + a[i] [math]\cdot[/math] c[j]
return dp[n]

Нетрудно видеть, что такая динамика работает за [math]O(n^2)[/math].

Ключевая идея оптимизации

Для начала сделаем замену обозначений. Давайте обозначим [math]dp[j][/math] за [math]b[j][/math], [math]a[i][/math] за [math]x[i][/math], а [math]c[j][/math] за [math]k[j][/math].

Теперь формула приняла вид [math]dp[i] = \min\limits_{j=0...i-1}(k[j] \cdot x[i] + b[j])[/math]. Выражение [math]k[j] \cdot x + b[j][/math] — это в точности уравнение прямой вида [math]y = kx + b[/math].

Сопоставим каждому [math]j[/math], обработанному ранее, прямую [math]y[j](x) = k[j] \cdot x + b[j][/math]. Из условия «[math]c[i][/math] убывают [math]\Leftrightarrow k[j][/math] уменьшаются с номером [math]j[/math]» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :

Picture1convexhull.png

Выделим множество точек [math](x_0, y_0)[/math] , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой [math]y’(x)[/math], такой что [math]y’(x_0) \lt y_0[/math]. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней огибающей множества прямых на плоскости). Назовем ее «[math]y = convex(x)[/math]». Видно, что множество точек [math](x, convex(x))[/math] представляет собой выпуклую вверх функцию.

Цель нижней огибающей множества прямых

Пусть мы считаем динамику для [math]i[/math]-го дерева. Его задает [math]x[i][/math]. Итак, нам нужно для данного [math]x[i][/math] найти [math]\min\limits_{j=0..i-1}(k[j] \cdot x[i] + b[j]) = \min\limits_{j=0..i-1}(y[j](x[i]))[/math]. Это выражение есть [math]convex(x[i])[/math]. Из монотонности угловых коэффицентов отрезков, задающих выпуклую оболочку, и их расположения по координатам x следует то, что отрезок, который пересекает прямую [math]x = x[i][/math], можно найти бинарным поиском. Это потребует [math]O(\log(n))[/math] времени на поиск такого [math]j[/math], что [math]dp[i] = k[j] \cdot x[i] + b[j][/math]. Теперь осталось научиться поддерживать множество прямых и быстро добавлять [math]i[/math]-ю прямую после того, как мы посчитали [math]b[i] = dp[i][/math].

Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека [math]k[][/math] и [math]b[][/math], которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую ([math]i[/math]-тую) прямую в множество. Пусть сейчас в множестве лежит [math]sz[/math] прямых (нумерация с 1). Пусть [math](x_L, y_L)[/math] — точка пересечения [math]sz - 1[/math]-й прямой множества и [math]sz[/math]-й, а [math](x_R, y_R)[/math] — точка пересечения новой прямой, которую мы хотим добавить в конец множества и [math]sz[/math]-й. Нас будут интересовать только их [math]x[/math]-овые координаты [math]x_L[/math] и [math]x_R[/math], соответственно. Если оказалось, что новая прямая пересекает [math]sz[/math]-ю прямую выпуклой оболочки позже, чем [math]sz[/math][math]sz - 1[/math]-ю, т.е. [math](x_L \geqslant x_R)[/math], то [math]sz[/math]-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо число прямых в стеке не станет равным 2, либо [math]x_L[/math] не станет меньше [math]x_R.[/math]

Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно [math]1[/math] раз добавится в стек и максимум [math]1[/math] раз удалится. Значит время работы перестройки выпуклой оболочки займет [math]O(n)[/math] суммарно.

Picture2convexhull.png Picture3convexhull.png

Теорема:
Алгоритм построения нижней огибающей множества прямых корректен.
Доказательство:
[math]\triangleright[/math]

Достаточно показать, что последнюю прямую нужно удалить из множества [math]\Leftrightarrow[/math], когда наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.

Пусть [math]Y(x) = Kx + B[/math] — уравнение новой прямой, [math]y[i](x) = K[i]x + B[i][/math] — уравнения прямых множества. Тогда т.к. [math]K \lt K[sz][/math], то при [math]x \in [- \infty; x_R] : y[sz](x) \lt = Y(x)[/math], а т.к. [math] K[sz] \lt K[sz - 1][/math], то при [math]x \in [x_L; + \infty] : y[sz - 1](x) \geqslant y[sz](x)[/math]. Если [math]x_L \lt x_R[/math], то при [math]x \in [x_L; x_R] : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)[/math], т.е. на отрезке [math][x_L; x_R][/math] прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же [math]x_L \gt x_R[/math], то она ниже всех на отрезке [math][x_L; x_R] = \varnothing [/math], т.е. её можно удалить из множества.
[math]\triangleleft[/math]

Детали реализации:

Будем хранить 2 массива : [math]front[][/math][math]x[/math]-координаты, начиная с которых прямые совпадают с выпуклой оболочкой (т.е. i-я прямая совпадает с выпуклой оболочкой текущего множества прямых при [math]x[/math] [math]\in[/math] [math][front[i]; front[i + 1])[/math] ) и [math]st[][/math] — номера деревьев, соответствующих прямым (т.е. [math]i[/math]-я прямая множества, где [math]i[/math] [math]\in[/math] [math][1; sz][/math] соответствует дереву номер [math]sz[i][/math]). Также воспользуемся тем, что [math]x[i] = a[i][/math] возрастают (по условию задачи), а значит мы можем искать первое такое [math]j[/math], что [math]x[i] \geqslant front[j][/math] не бинарным поиском, а методом двух указателей за [math]O(n)[/math] операций суммарно. Также массив [math]front[][/math] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси x до ближайшего целого (*), т.к. на самом деле мы, считая динамику, подставляем в уравнения прямых только целые [math]x[i][/math], а значит если [math]k[/math]-я прямая пересекается с [math]k+1[/math]-й в точке [math]z +[/math] [math]\alpha[/math] ([math]z[/math]-целое, [math]\alpha[/math] [math]\in[/math] [math][0;1)[/math]), то мы будем подставлять в их уравнения [math]z[/math] или [math]z + 1[/math]. Поэтому можно считать, что новая прямая начинает совпадать с выпуклой оболочкой, начиная с [math]x = z+1[/math]

Реализация

 int [math]\mathtt{ConvexHullTrick}[/math](int a[n], int c[n])
    st[1] = 1
    front[1] = -[math]\infty[/math]// первая прямая покрывает все 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] [math]\cdot[/math] a[i] + B[j] 
         if (i < n)   // если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку 
               K[i] = c[i]  // наши переобозначения переменных 
               B[i] = dp[i] // наши переобозначения переменных 
               x = -[math]\infty[/math] 
               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] 

Здесь функция [math]\mathtt{divide(a, b)}[/math] возвращает нужное(*) округление [math]\frac{a}{b}[/math]. Приведем её код :

int [math]\mathtt{divide}[/math](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

Заметим, что условия на возрастание/убывание [math]k[i][/math] на убывание/возрастание и [math]x[i][/math] выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016 [2]).

Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, с помощью которой мы за [math]O(\log(n))[/math] можем найти [math]dp[i][/math], но теперь вставку [math]i[/math]-й прямой в оболочку уже нельзя выполнить описанным ранее способом за [math]O(1)[/math] в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при [math]x \in [x_1; x_2][/math], где [math]x_1, x_2 \in R[/math] - точки пересечения с некоторыми прямыми, причем [math]x_2[/math] не обязательно равно [math]+ \infty[/math] Picture4convexhull.png

Чтобы уметь вставлять прямую в множество будем хранить двоичное дерево поиска, в вершинах которого будут пары [math](k, st)[/math] = (коэффицент прямой, ее номер в глобальной нумерации). Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает [math]O(\log(n))[/math]. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).

Асимптотика решения составит [math]O(\log(n))[/math] на каждый из [math]n[/math] запросов «добавить прямую» + [math]O(n\cdot\log(n))[/math] суммарно на удаление прямых, т.к. по-прежнему каждая прямая не более одного раза удалится из множества, а каждое удаление из std::set занимает [math]O(\log(n))[/math] времени. Итого [math]O(n\cdot\log(n))[/math].

Альтернативный подход

Другой способ интерпретировать выражение [math]dp[i] = \min\limits_{j=0...i-1}(c[j] \cdot a[i] + dp[j])[/math] заключается в том, что мы будем пытаться свести задачу к стандартной выпуклой оболочке множества точек. Перепишем выражение средующим образом : [math]dp[j] + a[i] \cdot c[j] = (dp[j], c[j]) \cdot (1, a[i])[/math], т.е. запишем как скалярное произведение векторов [math]v[j] = (dp[j], c[j])[/math] и [math]u[i] = (1, a[i])[/math]. Вектора [math]v[j] = (dp[j], c[j])[/math] хотелось бы организовать так, чтобы за [math]O(\log(n))[/math] находить вектор, максимизирующий выражение [math]v[j] \cdot u[i][/math]. Посмотрим на рис. 5. Заметим интуитивно очевидный факт : красная точка (вектор) [math]j[/math] не может давать более оптимальное значение [math]v[j] \cdot u[i][/math] одновременно чем обе синие точки. По этой причине нам достаточно оставить выпуклую оболочку векторов [math]v[j][/math], а ответ на запрос — это поиск [math]v[j][/math], максимизирующего проекцию на [math]u[i][/math]. Это задача поиска ближайшей точки выпуклого многоугольника (составленного из точек выпуклой оболочки) к заданной прямой (из [math](0, 0)[/math] в [math](1, a[i])[/math]). Ее можно решить за [math]O(\log(n))[/math] двумя бинарными или одним тернарным поиском Асимптотика алгоритма по-прежнему составит [math]O(n \cdot \log(n))[/math]

Picture5convexhull.png

Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются [math]3[/math] вектора [math]a, b, c[/math], расположенные как на рис. 5, т.е. точка [math]b[/math] не лежит на выпуклой оболочке векторов [math]0, a, b, c [/math] : [math] \Leftrightarrow [a-b, b-c] \lt 0 [/math], то либо [math](a, u[i])[/math] оптимальнее, чем [math](b, u[i])[/math], либо [math](c, u[i])[/math] оптимальнее, чем [math](b, u[i])[/math].

Теорема:
Если есть [math]3[/math] вектора [math]a, b, c[/math], таких что [math][a-b, b-c] \lt 0[/math] то либо [math](a, u) \lt (b, u)[/math], либо [math](c, u) \lt (b, u)[/math], где вектор [math]u = (1; k)[/math].
Доказательство:
[math]\triangleright[/math]

По условию теоремы известно, что [math][a-b, b-c] \lt 0 \Leftrightarrow (a_{x} - b_{x})\cdot(b_{y} - c_{y}) \lt (a_{y} - b_{y}) \cdot (b_{x} - c_{x})[/math] (*). Предположим (от противного), что [math](b, u) \lt (a, u) \Leftrightarrow b_{x} + k \cdot b_{y} \lt a_{x} + k \cdot a_{y} \Leftrightarrow (b_{x} - a_{x}) \lt k \cdot (a_{y} - b_{y})[/math] и при этом [math](b, u) \lt (c, u) \Leftrightarrow b_{x} + k \cdot b_{y} \lt c_{x} + k \cdot c_{y} \Leftrightarrow (c_{x} - b_{x}) \gt k \cdot (b_{y} - c_{y})[/math].

Подставим эти неравенства в (*). Получим цепочку неравенств : [math]k \cdot (a_{y} - b_{y})[/math][math] \cdot (c_{y} - b_{y}) = k[/math][math] \cdot (b_{y} - a_{y}) \cdot [/math][math](b_{y} - c_{y})[/math] [math] \lt (a_{x} - b_{x})[/math][math] \cdot (b_{y} - c_{y})[/math][math] \lt (a_{y} - b_{y}) \cdot [/math][math](b_{x} - c_{x})[/math] [math]\lt k \cdot (a_{y} - b_{y})[/math][math] \cdot (c_{y} - b_{y})[/math]. Получили противоречие : [math]k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y}) \lt k \cdot (a_{y} - b_{y}) \cdot (c_{y} - b_{y})[/math]. Значит предположение неверно, чтд.
[math]\triangleleft[/math]

Из доказанной теоремы и следует корректность алгоритма.

См. также

Примечания