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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Пример задачи, решаемой методом convex hull trick)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 8 участников)
Строка 1: Строка 1:
Convex hull trick {{---}} один из методов оптимизации [[Динамическое_программирование | динамического программирования]], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задачь, решемых методом динамического программирования с <math>O(n^2)</math> до <tex>O(n\cdot\log(n))</tex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.
+
Convex hull trick {{---}} один из методов оптимизации [[Динамическое_программирование | динамического программирования]], использующий идею [[Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|выпуклой оболочки]]. Позволяет улучшить асимптотику решения некоторых задач, решемых методом динамического программирования, с <math>O(n^2)</math> до <tex>O(n\cdot\log(n))</tex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.
  
 
==Пример задачи, решаемой методом convex hull trick==
 
==Пример задачи, решаемой методом convex hull trick==
Строка 5: Строка 5:
 
{{Задача
 
{{Задача
 
|definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, \dots, a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
 
|definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, \dots, a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
+
бензопилы. Но пила устроена так, что она может спиливать только по <math>1</math> метру от дерева, к которому ее применили. Также после
срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенной кол-во монет. Причем стоимость  
+
срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенное кол-во монет. Причем стоимость  
 
бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки  
 
бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки  
 
равна <tex>c_i</tex>.  Изначально пила заправлена.
 
равна <tex>c_i</tex>.  Изначально пила заправлена.
Строка 12: Строка 12:
 
(убывание и возрастание нестрогие)
 
(убывание и возрастание нестрогие)
 
}}
 
}}
(Задача H с Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf {{---}} Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>)
+
(Задача H с Санкт-Петербургских сборов к РОИ 2016 <ref>[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf Сайт с задачами Санкт-Петербургских сборов к РОИ 2016]</ref>)
 
</noinclude>
 
</noinclude>
 
<includeonly>{{#if: {{{neat|}}}|
 
<includeonly>{{#if: {{{neat|}}}|
Строка 27: Строка 27:
 
==Наивное решение==
 
==Наивное решение==
 
Сначала заметим важный факт : т.к. <tex>c[i]</tex> убывают (нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i]</tex> неотрицательны.
 
Сначала заметим важный факт : т.к. <tex>c[i]</tex> убывают (нестрого) и <tex>c[n] = 0</tex>, то все <tex>c[i]</tex> неотрицательны.
Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c[n] = 0</tex>). Посчитаем следующую динамику : <tex>dp[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i.</tex> будет срублено.
+
Понятно, что нужно затратив минимальную стоимость срубить последнее (<tex>n</tex>-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. <tex>c[n] = 0</tex>). Посчитаем следующую динамику : <tex>dp[i]</tex> {{---}} минимальная стоимость, заплатив которую можно добиться того, что дерево номер <tex>i</tex> будет срублено.
База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.
+
База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна <math>1</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> монет.
+
Переход динамики :  понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме [[Теорема_Радо-Эдмондса_(жадный_алгоритм)|жадных алгоритмов]], чем к теме данной статьи). Поэтому перед  <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> монет.
Итогвая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[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])
 
  '''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n])
 
     dp[1] = 0
 
     dp[1] = 0
 
     dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
 
     dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
     '''for''' 2 = 1..n   
+
     '''for''' i = 2 = 1..n   
 
       dp[i] = <tex>+\infty</tex>
 
       dp[i] = <tex>+\infty</tex>
       '''for''' j = 1..i-1  
+
       '''for''' j = 1..i - 1  
 
           '''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i])
 
           '''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i])
 
               dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j]
 
               dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j]
Строка 47: Строка 47:
 
Для начала сделаем замену обозначений. Давайте обозначим <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[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>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>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :
 
Сопоставим каждому <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>» следует то, что прямые, полученные ранее отсортированы в порядке убывания углового коэффициент. Давайте нарисуем несколько таких прямых :
Строка 53: Строка 53:
 
[[Файл:picture1convexhull.png]]
 
[[Файл:picture1convexhull.png]]
  
Выделим множество точек <tex>(x0, y0)</tex> , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой <tex>y’(x)</tex>, такой что <tex>y’(x0) < y0</tex>. Иными словами возьмем «выпуклую (вверх) оболочку» нашего множества прямых (её еще называют нижней ошибающей множества прямых на плоскости). Назовем ее «<tex>y = convex(x)</tex>». Видно, что множество точек <math>(x, 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> представляет собой выпуклую вверх функцию.
  
 
==Цель нижней огибающей множества прямых==
 
==Цель нижней огибающей множества прямых==
Пусть мы считаем динамику для <tex>i</tex>-го дерева. Его задает <tex>x[i]</tex>. Итак, нам нужно для данного <tex>x[i]</tex> найти <tex>\min\limits_{j=0..i-1}(k[j] \cdot x[i] + b[i]) = \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>.
+
Пусть мы считаем динамику для <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>(xL, yL)</tex> - точка пересечения <tex>sz - 1</tex>-й прямой множества и <tex>sz</tex>-й, а <tex>(xR, yR)</tex> - точка пересечения новой прямой, которую мы хотим добавить в конец множества и <tex>sz</tex>-й. Нас будут интересовать только их <tex>x</tex>-овые координаты <tex>xL</tex> и <tex>xR</tex>, соответственно. Если оказалось, что новая прямая пересекает <tex>sz</tex>-ю прямую выпуклой оболочки позже, чем <tex>sz</tex>-я <tex>sz - 1</tex>-ю, т.е. <tex>(xL \geqslant xR)</tex>, то <tex>sz</tex>-ю удалим из нашего множества, иначе - остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо <tex>xL</tex> не станет меньше <tex>xR.</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> суммарно.
 
Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
Строка 68: Строка 68:
 
|id=th1239.  
 
|id=th1239.  
 
|statement=Алгоритм построения нижней огибающей множества прямых корректен.
 
|statement=Алгоритм построения нижней огибающей множества прямых корректен.
|proof=Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.
+
|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; xR]  : y[sz](x) <= Y(x)</tex>, а т.к. <tex> K[sz] < K[sz - 1]</tex>, то при <tex>x \in [xL; + \infty]  : y[sz - 1](x) \geqslant y[sz](x)</tex>. Если <tex>xL < xR</tex>, то при <tex>x \in [xL; xR]  : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)</tex>, т.е. на отрезке <tex>[xL; xR]</tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <tex>xL > xR</tex>, то она ниже всех на отрезке <tex>[xL; xR] = \varnothing </tex>, т.е. её можно удалить из множества
+
Пусть <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 массива : <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> операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси 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>
+
Будем хранить 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])
 
   '''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n])
 
     st[1] = 1
 
     st[1] = 1
     from[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
+
     front[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
 
     sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
 
     sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
 
     pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font >
 
     pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font >
Строка 86: Строка 86:
 
               pos = pos + 1
 
               pos = pos + 1
 
           j = st[pos]
 
           j = st[pos]
           dp[i] = K[j]<math>\cdot</math>a[i] + B[j]  
+
           dp[i] = K[j] <math>\cdot</math> a[i] + B[j]  
 
           '''if''' (i < n)  <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
 
           '''if''' (i < n)  <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
 
                 K[i] = c[i]  <font color=green>// наши переобозначения переменных </font >
 
                 K[i] = c[i]  <font color=green>// наши переобозначения переменных </font >
Строка 97: Строка 97:
 
                       sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
 
                       sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
 
                 st[sz + 1] = i   
 
                 st[sz + 1] = i   
                 from[sz + 1] = x <font color=green>// добавили новую прямую </font >
+
                 front[sz + 1] = x <font color=green>// добавили новую прямую </font >
 
                 sz = sz + 1
 
                 sz = sz + 1
 
   '''return''' dp[n]  
 
   '''return''' dp[n]  
Здесь функция <tex>\mathtt{divide}</tex>(a, b) возвращает нужное(*) округление a / b. Приведем её код :
+
Здесь функция <tex>\mathtt{divide(a, b)}</tex> возвращает нужное(*) округление <tex>\frac{a}{b}</tex>. Приведем её код :
 
  '''int''' <tex>\mathtt{divide}</tex>('''int''' a, '''int''' b)
 
  '''int''' <tex>\mathtt{divide}</tex>('''int''' a, '''int''' b)
 
         delta = 0
 
         delta = 0
Строка 108: Строка 108:
 
   
 
   
  
Такая реализация будет работать за O(n).
+
Такая реализация будет работать за <math>O(n)</math>.
  
 
==Динамический convex hull trick==
 
==Динамический convex hull trick==
Заметим, что условия на прямые, что <tex>k[i]</tex> возрастает/убывает и <tex>x[i]</tex> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой - отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016[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>).
  
Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за <tex>O(\log(n))</tex> можем найти  <tex>dp[i]</tex>, но теперь вставку <tex>i</tex>-й прямой в оболочку уже нельзя выполнить описанным ранее способом за <tex>O(1)</tex> в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая - та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при <tex>x \in [x1; x2]</tex>, где <tex>x1, x2 \in R</tex> - точки пересечения с некоторыми прямыми, причем <tex>x2</tex> не обязательно равно <tex>+ \infty</tex>
+
Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, с помощью которой мы за <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>std::set</math> (или любой аналог в других языках программирования) пар <tex>(k, st)</tex> =  <tex>(коэффицент прямой, ее номер в глобальной нумерации)</tex>. Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(\log(n))</tex>. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).
+
Чтобы уметь вставлять прямую в множество будем хранить [[Красно-черное_дерево|двоичное дерево поиска]], в вершинах которого будут пары <tex>(k, st)</tex> =  (коэффицент прямой, ее номер в глобальной нумерации). Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(\log(n))</tex>. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).
 
 
 
Асимптотика решения составит <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>.
 
Асимптотика решения составит <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>.
  
 
== Альтернативный подход ==
 
== Альтернативный подход ==
Другой способ интерпретировать выражение <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> двумя бинарными или одним тернарным поиском
+
Другой способ интерпретировать выражение <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> двумя бинарными или одним тернарным поиском
 
Асимптотика алгоритма по-прежнему составит <tex>O(n \cdot \log(n))</tex>
 
Асимптотика алгоритма по-прежнему составит <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>.
+
Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <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.  
 
|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} < c_{x} + k \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) < k \cdot (c_{y} - b_{y})</tex> и <tex>(b, u) < (c, u) \Leftrightarrow b_{x}  + k \cdot b_{y} < a_{x} + k \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) > k \cdot (b_{y} - a_{y})</tex>.
+
|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>. Значит предположение неверно, чтд.
Строка 138: Строка 138:
  
 
==См. также==
 
==См. также==
1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull
 
  
2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование
+
*[[:Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull|Выпуклая оболочка]]
 +
 
 +
*[[:Динамическое_программирование|Динамическое программирование]]
  
 
== Примечания ==
 
== Примечания ==

Текущая версия на 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]

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

См. также

Примечания