Convex hull trick

Материал из Algocode wiki
Версия от 18:38, 27 сентября 2019; KiKoS (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Рассмотрим следующую задачу:

Вася надувает воздушный шар. Каждую секунду он может либо дополнительно надуть шар, либо ничего не делать. Если он надувает шар в $i$-ю секунду, то радиус увеличивается на $a_i$, но после этого радиус будет уменьшаться на $b_i$ в секунду до следующего поддува. Найдите максимальный радиус шара, который можно получить за $n$ секунд.

Данную задачу можно решить с помощью динамического программирования. $dp_i$ — это наилучший радиус, который можно получить через $i$ секунд. Тогдв $$dp_i = \max_{j=1}^{i-1} dp_j + a_j - b_j \cdot (i - j) = \max_{j=1}^{i-1} (-b_j) \cdot i + (dp_j + a_j + b_j \cdot j) = \max_{j=1}^{i-1} A_j \cdot i + B_j$$ где $A, B$ зависят только от $j$. То есть можно считать, что нам надо найти минимальное значение среди линейных функций в точке $i$.

Convex hull

Будем поддерживать структуру данных, которая позволяет:

  • добавить линейную функцию
  • найти максимальное значение в данном множестве функций в точке $x$

Заметим, что данная функция будет иметь вид верхней огибающей. Пересечение новой линейной функции и огибающей не может имметь больше двух точек. Тогда нам надо научиться удалить из огибающей все прямые, которые из нее целиком пропали, а после добавить новую прямую и точки пересечения.

Такие операции действительно можно делать, если сложить все прямые в std::set, находить бинпоиском те прямые, с которыми надо пересечь новую, и удалять все прямые между ними. Это будет работать за $O(n \log n)$, но пишется достаточно тяжело, и нужно редко. Кроме того, такую задачу можно решать, используя дерево Li Chao

Гораздо чаще в задаче бывает ограничение на монотонное изменение линейного коэффициента прямых (в нашем случае, $-b_i$). Тогда прямые нужно добавлять не в произвольное место структуры данных, а только в конец. В таком случае можно заменить std::set на стек. Тогда находить точки пересечения можно не бинпоиском, а постепенным удалением "бесполезных" прямых. Таким образом, структуру можно реалиизовать с суммарным временем работы $O(n)$, если запросы по $x$ тоже были отсортированы (если не были, то отвечать на запрос бы будем за $O(\log n)$.

Реализация

В раиках данной реализации мы храним две величины: массив прямых $lines$ и массив точек изменений $pr$. Считаем, что $lines_i$ является минимальной на промежутке $[pr_i, pr_{i + 1}]$.

 1 struct Line {
 2     int k, m;
 3 };
 4 
 5 vector<int> pr; // если округлять точку пересечения вниз, то можно хранить их в целых числах
 6 vector<Line> lines;
 7 
 8 int get(int x) {
 9 	int l = 0;
10 	int r = lines.size();
11 	while (l + 1 < r) {
12 		int mid = (l + r) / 2;
13 		if (pr[mid] <= x) {
14 			l = mid;
15 		}
16 		else {
17 			r = mid;
18 		}
19 	}
20 	return lines[l].k * x + lines[l].m;
21 }
22 
23 void upd(Line line) {
24 	while (lines.size() && line.k * pr.back() + line.m < lines.back().k * pr.back() + lines.back().m) {
25         pr.pop_back();
26         lines.pop_back();
27 	}
28     int coord;
29     if (lines.empty()) {
30         coord = -INF;
31     } else {
32         coord = cross(line, lines.back()); // нужно реализовать пересечение прямых
33     }
34     pr.push_back(coord);
35     lines.push_back(line);
36 }



Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s