Convex hull trick

Что такое convex hull trick

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 метру от дерева, к которому ее применили. Также после
  срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенной кол-во монет. Причем стоимость 
  бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен i, то цена заправки 
  равна ci.  Изначально пила заправлена.
  Также известны следующие ограничения : [math]c[n] = 0, a[1] = 1, a[i][/math] возрастают, [math]c[i][/math] убывают. Изначально пила заправлена.
 (убывание и возрастание нестрогие)

(Задача H отсюда : http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf)

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

Сначала заметим важный факт : т.к. c[i] убывают(нестрого) и c[n] = 0, то все c[i] неотрицательны. Понятно, что нужно затратив минимальную стоимость срубить последнее ([math]n[/math]-е) дерево, т.к. после него все деревья можно будет рубить бесплатно (т.к. [math]c[n] = 0[/math]). Посчитаем следующую динамику : [math]dp[i][/math] - минимальная стоимость, заплатив которую можно добиться того, что дерево номер [math]i.[/math] будет срублено. База динамики : [math]dp[1] = 0[/math], т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи. Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед [math]i[/math]-м деревом мы обязательно срубили какое-то [math]j[/math]-е, причем [math]j \lt i[/math]. Поэтому чтобы найти [math]dp[i][/math] нужно перебрать все [math]1 \lt = j \lt 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] монет. Итогвая формула пересчета : [math]dp[i] = min_{j=0...i-1}(dp[j] + a[i] * c[j])[/math]. 
 Посмотрим на код выше описанного решения:

dp[1] = 0
dp[2] = dp[3] = ... = dp[n] = [math]\infty[/math]
for  i = 1..n-1  {
       dp[i] = +[math]\infty[/math] 
       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].

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

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

2) Теперь формула приняла вид [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].

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

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

Для чего нужна нижняя ошибающая множества прямых

Пусть мы считаем динамику для [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].

Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 2 стека [math]k[][/math] и [math]b[][/math], которые задают прямые в отсортированном порядке их угловыми коэффицентами и свободными членами. Рассмотрим ситуацию, когда мы хотим добавить новую ([math]i[/math]-тую) прямую в множество. Найдем точки пересечения с последними 2мя прямыми из стека. Нас будут интересовать только их [math]x[/math]-овые координаты. Назовем их [math]xL[/math] и [math]xR[/math], соответственно. Если оказалось, что новая прямая пересекает предпоследнюю прямую выпуклой оболочки позже, чем последнюю [math](xL \gt = xR)[/math], то последнюю удалим из нашего множества. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо [math]xL[/math] не станет меньше [math]xR.[/math]

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

Корректность : достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем предпоследнюю.

План доказательства : пусть новая прямая пересекает последнюю прямую множества позже, чем предпоследнюю (рис.2 - красная прямая новая, фиолетовая - предпоследняя, желтая - последняя), тогда найдется такой отрезок [math][x1;x2][/math], что последняя (желтая) прямая при [math]x \in [x1;x2][/math] лежит ниже всех остальных и ее следует оставить в множестве. А если новая прямая пересекает последнюю прямую множества раньше, чем предпоследнюю (рис.1), последняя прямая при любых x лежит выше какой-то другой прямой множества и значит ее нужно удалить.

Более формально. Пусть [math]xL \lt = [/math]

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

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

Реализация

 void Convex-hull-trick
 st[1] = 1
 from[1] = -[math]\infty[/math]// первая прямая покрывает все x-ы, начиная с -∞ 
 sz = 1 // текущий размер выпуклой оболочки 
 pos = 1 // текущая позиция первого такого j, что x[i] >= front[st[j]] 
 for  i = 2..n  {
      while (front[pos] < x[i]) // метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой 
           pos = pos + 1
      j = st[pos]
      dp[i] = K[j] * a[i] + B[j] 
      if (i < n) {  // если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку 
            K[i] = c[i]  // наши переобозначения переменных 
            B[i] = dp[i] // наши переобозначения переменных 
            x = -[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  
             from[sz + 1] = x // добавили новую прямую 
             sz = sz + 1
      }                       
 }          

(Здесь функция divide(a, b) возвращает нужное(*) округление a / b) Такая реализация будет работать за O(n).

Динамический convex hull trick

Заметим, что условия на прямые, что [math]k[i][/math] возрастает/убывает и [math]x[i][/math] убывает/возрастает выглядят не достаточно общими. Как же быть, если в задаче таких ограничений нет. Иногда можно отсортировать прямые нужным образом, не испортив свойств задачи (пример : задача G отсюда http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf). Но рассмотрим общий случай. Наша задача поменялась следующим образом : по-прежнему у нас есть выпуклая оболочка, имея которую мы за [math]O(logn)[/math] или быстрее можем найти [math]dp[i][/math], но теперь вставку i-й прямой в оболочку уже нельзя выполнить старым способом за [math]O(1)[/math] (в среднем). У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отрезая» несколько отрезков выпуклой оболочки в середине (рис. 4).

Т.е. нужно уметь быстро (за [math]O(logn)[/math]?) назодить, после какой прямой стоит пытаться вставить текущую (красную рис.4) прямую и удалять лишние справа, начиная с нее, потом проводить аналогичные операции слева. Итак, давайте хранить [math]std::set[/math] (или любой аналог в других языках) пар [math]\lt k, st\gt [/math] = <коэффицент прямой, ее номер в глобальной нумерации>. Когда приходит новая прямая, делаем lower_bound - 1 в сете, т.е. ищем ближайшую прямую с меньшим углом наклона, и начиная с нее повторяем старый алгоритм (удаляем, пока прямая бесполезная). И симметричный алгоритм применяем ко всем прямым справа от нашей. Асимптотика решения составит [math]O(logn)[/math] на каждый из n запросов «добавить прямую» + [math]O(n)[/math] суммарно на удаление прямых. Итого [math]O(nlogn)[/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) двумя бинарными или одним тернарным поиском Асимптотика алгоритма по-прежнему составит [math]O(n*log(n))[/math]