\Section{Оптимизации к динамике}{3 марта 2017}{Сергей Копелиович}

\down
Цель лекции -- дойти до популярных оптимизаций ``convex hull trick'', ``divide \&{} conquer'' и т.д.

Для разминки мы сперва разберём пару простых примеров.

В большинстве динамик я буду описывать только переход, считая базу очевидной.

\Subsection{Умный пересчёт}

\Subsubsection{Числа Фибоначчи}

Все вы умеете считать числа Фибоначчи $f_n = f_{n-1} + f_{n-2}$.

Обобщёнными $k$-числами Фибоначчи назовём $f_n = f_{n-1} + f_{n-2} + \dots + f_{n-k}$.

Если считать ``в лоб'', получится время $\O(nk)$:

\begin{code}
for (int i = k; i <= n; i++)
	f[i] = 0;
	for (int j = 1; j <= k; j++)
		f[i] += f[i - j];
\end{code}

Чтобы получить $\O(n)$, можно заметить ``\t{f[i] = сумма на отрезке}'',\\
а сумму на отрезке мы умеем считать за $\O(1)$.

\Subsubsection{Максимальная по сумме подпоследовательность}

{\it Задача:} найти подпоследовательность с началом в $1$, концом в $n$, 
у которой расстояние между соседними элементами не более $k$,
из таких выбрать подпосл-ть с максимальной суммой.

\down
Пусть $f[i]$ -- max подпосл-ть с концом в $i$. Решение ``в лоб'' будет работать за $\O(nk)$:

\begin{code}
for (int i = k; i <= n; i++)
	f[i] = INT_MIN;
	for (int j = 1; j <= k; j++)
		f[i] = max(f[i], f[i - j] + a[i]);
\end{code}

Чтобы получить $\O(n)$, можно заметить ``\t{f[i] = минимум на очереди}'',\\
а минимум на очереди мы умеем считать за $\O(1)$.

\Subsubsection{Обобщим}

Чтобы получить линейное решение, мы сперва выписываем хоть какую-нибудь динамику, затем пытаемся её оптимизировать.
Стандартная оптимизация: увидеть функцию на отрезке.\\
В обоих примерах мы записывали ``динамику назад''.
Иногда, чтобы получилось соптимизировать, нужно записать ``динамику вперёд''.

\Subsubsection{Динамика ли?}

{\it Задача:} даны $n$ точек на прямой,
найти $k$ отрезков минимальной суммарной длины, покрывающие все точки.

\down
Можно пытаться решать задачу так: $f[i,j]$ -- минимальная стоимость покрыть левые $i$ точек $j$ отрезками.
Получится решение за $\O(n^2k)$, можно даже его соптимизировать до $\O(nk)$...
Вот только на самом деле задача решается жадно: отсортируем точки, возьмём $n-1$ расстояний между соседними
и удалим $k-1$ максимальных из них.
Увидеть, что задача имеет жадное решение, -- высокое искусство.
При решении задач важно себе всегда задавать вопрос ``динамика или жадность''.
К сожалению, этот вопрос выходит за рамки нашей лекции.

\Subsubsection{Два указателя}
\label{chapter@pointers}

{\it Задача:}
даны $n$ точек с весами $w_i$ на прямой, для каждого отрезка точек $[L,R]$ найти $m[L,R]$
минимизирующий сумму взвешенных расстояний на $[L..R]$ до точки $m$: $\sum_i w_i|x_i - m| \to \min$.

\down
Решение ``в лоб'' будет работать за $\O(n^4)$: 
для каждого отрезка перебрали $m$, для каждого $m$ посчитали сумму.
Чтобы получить $\O(n^3)$, достаточно раскрыть скобки и разделить $\sum_i w_i|x_i - m|$ на $4$ частичные суммы,
каждая считается за $\O(1)$.

\down
Интересная часть задачи -- выбор оптимального $m$. Здесь нам поможет метод двух указателей:
\begin{code}
for (int l = 0; l < n; l++)
	int m = l;
	for (int r = l; r < n; r++)
		while (m + 1 < r && F(l, r, m + 1) < F(l, r, m))
			m++;
\end{code}
Здесь $F$ вычисляется за $\O(1)$ через частичные суммы, получили решение за $\O(n^2)$.
На самом деле точка $m$ обладает свойством ``самая левая, что сумма весов слева $\ge$ суммы весов справа''.
Из этого факта следует корректность применения двух указателей к данной задаче.

\down
Вопрос: ``дана произвольная динамика, работает ли метод двух указателей?''.
Общий способ проверки мне не известен, но опыт подсказывает, что обычно быстрее всего написать две функции 
(в лоб и с двумя указателями) и ``пострессить их на рандоме''.

\Subsubsection{Convex Hull Trick (CHT): сведение}

{\it Задача:} даны $n$ точек на прямой, найти $k$ отрезков, покрывающие все точки,\\
минимизировать {\it сумму квадратов} длин отрезков.

\down
Решение ``в лоб'': $f[j,i]$ -- минимальная стоимость покрыть левые $i$ точек $j$ отрезками.\\
$nk$ состояний, из каждого $n$ переходов, итого $\O(n^2k)$.
\begin{code}
// `точки имеют номера 1..n, используя 0 отрезков, можем покрыть 0 точек`
f[0] = {0, INF, INF, ...}; 
for (int j = 0; j < k; j++) 
	for (int i = 0; i <= n; i++)
		f[j+1][i] = INF;
		for (int r = 1; r <= i; r++)
			relax(f[j+1][i], f[j][r-1] + cost(r, i)) // `relax делает 'min=', как '+='`
answer = f[k][n]; // `пусть k <= n`
\end{code}
Чтобы применить CHT нужно расписать функцию \t{cost} и увидеть линейную функцию:

\t{f[j][r-1] + cost(r, i) = f[j][r-1] + (r-i)$^2$ = f[j][r-1] + r$^2$ - 2ri + i$^2$}

Мы минимизируем эту величину для данного $i$. Отбросим $i^2$, он для всех $r$ один и тот же. Оставшееся сгруппируем:
\t{(f[j][r-1] + r$^2$) - 2ri = B$_r$ + A$_r\cdot$i} -- линейная от $i$ функция.

{\it Замечание:} в некоторых динамиках нам прямо в условии дают готовые линейные функции.

\down
Теперь получили задачу, решение которой и называется ``Convex Hull Trick'': \\
поочерёдно добавлять линейные функции и искать максимум по всем добавленным в точке $i$. 

\pagebreak
\begin{code}
// `точки имеют номера 1..n, используя 0 отрезков, можем покрыть 0 точек`
f[0] = {0, INF, INF, ...}; 
for (int j = 0; j < k; j++) 
	CHT.init();
	for (int i = 0; i <= n; i++)
		f[j+1][i] = CHT.getMin(i) + i*i; // `мы его отбросили при минимизации, теперь вернули`
		int r = i + 1; // `для всех следующих $i$ мы будем просматривать такое $r$`
		CHT.addLinear(f[j][r-1] + r*r, -2*r); 
answer = f[k][n]; // `пусть k <= n`
\end{code}

\Subsubsection{Convex Hull Trick (CHT): реализация}

Здесь должна быть картинка: \TODO\ (пока представьте себе параболу ветвями вверх).

\down
Казалось бы в общем случае нам нужно пересекать произвольные полуплоскости, добавлять новые, что не очень приятно.
К счастью обычно задача гораздо проще.\\
Будем решать её в такой формулировке: есть прямые вида $y = k_ix + b_i$, все $k_i > 0$.\\
Прямые уже отсортированы в порядке возрастания $k_i$.
Нужно добавлять прямые {\it в отсортированном порядке} и уметь считать $get(x) = max_i(k_ix + b_i)$ для $x \ge 0$.\\
При этом все $k_i$, $b_i$, $x$ целочисленны.
Добавим фиктивную прямую $(k_0 = {-}\infty, b_0 = {-}\infty)$.

\begin{code}
struct CHT {
	vector<line> l;
	vector<points> p;
	void init() {
		l = {line(-INF, -INF)};
		p = {};
	}
	void addLine( int k, int b ) {
		line new_line(k, b)
		while (!p.empty() && p.back() is under new_line)
			p.pop_back(), l.pop_back();
		p.push_back(l.back() intersect with new_line) // `вещественные числа!`
		l.push_back(new line)
	}
	int getMax( int x ) {
		// `\t{i} -- первая точка пересечения правее \t{x}`
		int i = lower_bound(p.begin(), p.end(), Point(x, -INF)); 
		return l[i].value(x); // `значение прямой \t{l[i]} в точке \t{x}`
	}
};
\end{code}
При желании можно $\mathbb{R}$ числа заменить на рациональные и все вычисления провести без погрешности.
Суммарное время работы всех \t{addLine} -- $\O(n)$, каждый \t{getMax} работает за $\O(\log n)$.\\
Иногда $x$-ы возрастают, тогда можно применить метод двух указателей и получить суммарное время всех \t{getMax} и
\t{addLine} $\O(n + m)$, где $m$ -- число запросов.

\pagebreak
\vspace*{-1.5em}
\Subsection{Рюкзак}

\vspace*{-0.2em}
\Subsubsection{Обычный рюкзак с линией памяти}

{\it Задача:} даны $n$ предметов с положительными целыми размерами (весами) $a_i$ и рюкзак размера $W$, 
выбрать подмножество предметов $i_1, i_2, \dots i_k \colon f = \sum a_{i_j} \le W$ и среди таких $f \to \max$.

\down
Есть три стандартных решения такой задачи -- перебор за $\O(2^n)$, meet in the middle за $\O(2^{n/2}n)$ и 
динамика за $\O(nW)$. Мы сейчас сосредоточимся именно на третьем. 
Для экономии времени опустим вопрос восстановления ответа $\{i_1, \dots, i_k\}$, будем искать $f$.

\begin{code}
vector<bool> f(W + 1); // `инициализируется нулями`
f[0] = 1; 
for (int i = 0; i < n; i++)
	for (int x = W - a[i]; x >= 0; x--)
		f[x + a[i]] |= f[x];
\end{code}

\Subsubsection{Добавим bitset}

\t{unsigned long long} можно рассматривать как массив из $64$ бит, 
операции ``\t{|=}'', ``\t{<{}<{}}'' происходят за один такт. \t{bitset<n>} -- 
аналогичный объект на $n$ битах, все операции происходят за $\mfrac{n}{64}$.

\begin{code}
bitset<W+1> f; // `инициализируется нулями, \t{W} -- обязательно константа`
f[0] = 1; 
for (int i = 0; i < n; i++)
	f |= f << a[i];
\end{code}

И код укоротился, и время улучшилось. При желании к этому способому можно добавить восстановление
ответа без потерь во времени.

\Subsubsection{Рюкзак на отрезке}

{\it Более крутая задача:} запрос ``можно ли отрезком предметов \t{[L..R]} набрать вес ровно \t{X}''.

\down
Можно пойти лобовым путём: модифицируем стандартную динамику, добавим параметр \t{L}: \t{f[X,L]} -- 
можно ли набрать \t{X} предметами индексами не менее \t{L}. \\
Тогда к моменту \t{R} мы для каждой пары $\q{\t{L},\t{X}}$ знаем ответ.

\down
В нашей динамике есть некая не оптимальность: мы храним $0$ или $1$.
Эта не оптимальность даёт возможность сделать следующую оптимизацию.
Давайте после обработки \t{R} первых предметов хранить \t{L[X]} -- максимальное число такое,
что предметами \t{[L[X]..R]} можно набрать \t{X}.

\begin{code}
vector<int> f(W + 1, -1);
for (int R = 0; R < n; R++) {
	f[0] = R; // `всегда можем набрать $0$`
	for (int x = W - a[i]; x >= 0; x--)
		relax(f[x + a[i]], f[x]);
	// `Здесь можно отвечать на все запросы с правым концом $R$`
	get(L, X) = (f[X] >= L);
}
\end{code}

\pagebreak
\vspace*{-1.5em}
\Subsubsection{Мостостроение: тренируемся грамотно выбирать состояние}

{\it Задача:} даны $a$ брёвен длины $x$, $b$ брёвен длины $y$, число $l$,
хотим построить мост из $l$ не обязательно равных рядов брёвен,
вопрос -- какой максимальной ширины будет самое узкое место моста?
$a, x, b, y, l \le n$.

\down
Решение за $\O(n^5)$: \t{f[a,b,l]} -- ответ на задачу, 
переход -- перебрать, сколько брёвен первого и второго типа будем брать для очередного ряда.

\down
Оптимизация \NO{1}: бинпоиск по ответу (обозначим ответ $x$). Сделаем бинпоиск,
получим динамику \t{l[a,b]} -- сколько максимум рядов ширины $x$ можно положить.
При переходе теперь, зафиксировав число брёвен первого типа $i$,
можем однозначно посчитать минимальное число брёвен второго типа: $\lceil\mfrac{l - ai}{x}\rceil$.
Итого $\O(n^3 \log \t{ANS})$.

\down
Оптимизация \NO{2}: ``измельчение перехода'' \t{+} ``хранить сразу пару чисел в динамике''.\\
Мы по-прежнему делаем бинпоиск, и отталкиваемся от динамики из предыдущего пункта.
За один переход будет класть ровно одно бревно в текущий ряд.
Тогда перехода всего два: положить бревно первого типа, положить бревно второго типа.
Итого динамика следующая: $\q{\t{l,z}}$\t{[a,b]}, где $z$ -- длина последнего ряда, $l$ -- количество рядов.
$\O(n^2 \log \t{ANS})$.

\vspace*{1em}
\Subsection{Пересчёт ``по слоям'' в квадратичных динамиках}

\Subsubsection{Формулировка задачи, наивное решение}

{\it Задача:} даны $n$ точек на прямой, выбрать какие-то $k: i_1, i_2, \dots, i_k$,
минимизировать сумму по точкам взвешенных расстояний до ближайшей выбранной:
$\sum_j \big[ w_j\min_t |x_j - x_{p_t}|\big] \to \min$.

\down
Сразу замечаем, что задача на самом деле равносильна разбиению $n$ точек на $k$ отрезков,
а в каждом отрезке $[L,R]$ выборе точки $m[L,R]$, как мы делали в \autoref{chapter@pointers}.

\down
Сейчас предположим, что у нас уже посчитаны массивы $m[L,R]$ -- оптимальная точка и
$cost[L,R]$ -- сумма расстояний внутри отрезка $[L,R]$. В \autoref{chapter@pointers} мы научились это делать за $\O(n^2)$.
Как теперь разбить на отрезки? Решение ``в лоб'' даёт время $\O(n^2k)$:
\begin{code}
// `\t{f[i][j]} -- стоимость разбить точки $[0,j)$ на $i$ отрезков`
f[0] = {0, INF, INF, ...};
for (int i = 1; i <= k; i++)
	f[i][0] = 0; // `можем бесплатно покрыть $0$ точек`
	for (int j = 1; j <= n; j++)
		f[i][j] = INF; 
		// `\t{p} -- левый конец последнего отрезка`
		for (int p = 0; p < j; p++)
			relax(f[i][j], f[i-1][p] + cost[p][j-1])
\end{code}
Обозначим \t{p}, на котором достигается минимум в строках $7$ и $8$, за \t{p[i][j]}.
Следующие оптимизации будут основаны на том, что можно быстро искать оптимальное \t{p[i][j]}.\\
Зная \t{p[i][j]}, можно посчитать \t{f[i][j] = f[i-1][p[i][j]] + cost[p[i][j]][j-1]}.

%\pagebreak
%\vspace*{-1.5em}
\Subsubsection{Оптимизация Кнута}

{\it Утверждение без док-ва:} \t{p[i-1][j] $\le$ p[i][j] $\le$ p[i][j+1]}.

\down
Оптимизация Кнута заключается в том, что \t{p}-шки мы вычисляем в таком порядке, что
при подсчёте \t{p[i][j]} уже посчитаны \t{p[i-1][j]} и \t{p[i][j+1]}: $i \uparrow$, $j \downarrow$.\\
Тогда \t{p[i][j]} можно перебирать не в $[0,j)$, а в $[\t{p[i-1][j]},\t{p[i][j+1]}]$.

\down
Докажем, что время работы полученного алгоритма $\O(n^2)$.\\
$\t{Time} = \sum_{i,j}\q{\text{время на подсчёт \t{p[i][j]}}} = \sum_{i,j}\big[\t{p[i][j+1]} - \t{p[i-1][j]} + 1\big] = $\\
$ nk + \sum_{i,j}\big[\t{p[i][j+1]} - \t{p[i-1][j]}\big] \le (n+k)n$, так как не сократятся только $n+k$ слагаемых
 со знаком плюс и каждое из них не более $n$.

\Subsubsection{Разделяй и властвуй}

Воспользуемся почти такой же посылкой, как и в предыдущей оптимизации.\\
Кстати, на самом деле посылка для Кнута следует из этой.\\
{\it Утверждение без док-ва:} \t{p[i][j] $\le$ p[i][j+1]}.

\down
Пусть уже посчитаны слой динамики \t{p[i-1]} и слой \t{f[i-1]}.
Хотим за $\O(n \log n)$ насчитать все \t{p[i]}, будем это делать рекурсивной функцией,
которая считает ``в лоб'' \t{p}-шку от средней точки и запускается от левой и правой половины,
используя посчитанное значение, как ограничение:

\begin{code}
// `считаем \t{p[i][l..r]}, предполагая, что все они должны лежать в \t{[pl..pr]}`
void go( int l, int r, int pl, int pr ) {
	if (l > r) return; // `пустой отрезок`
	int m = (l + r) / 2, tmp;
	f[i][m] = INF;
	for (int p = pl; p <= min(pr, m - 1); p++)
		if (f[i][m] > (tmp = f[i-1][p] + cost[p][j-1]))
			f[i][m] = tmp, p[i][m] = p;
	go(l, m - 1, pl, p[i][m]);	
	go(m + 1, r, p[i][m], pr);	
}
\end{code}

Докажем, что время работы $\O(n \log n)$: глубина рекурсии $\log n$, на каждом уровне
рекурсии отрезки \t{[pl$_i$..pr$_i$]} обладают замечательным свойством \t{pr$_i$ = pl$_{i{+}1}$}.

\Subsubsection{Сравнение}

Сравним изученные оптимизации. \\
Насколько хорошо они справляются с задачей ``по данным \t{cost[l,r]} посчитать \t{p[i,j]}''?
\vspace*{-0.5em}

\begin{MyItemize}
\item Convex Hull Trick не помогает решить данную задачу
\item Divide \&{} Conquer даёт время $\O(nk \log n)$.
\item Метод Кнута даёт время $\O(n^2)$.
\end{MyItemize}

\vspace*{-0.5em}
Ясно, что при $k \le \mfrac{n}{\log n}$ нужно использовать Divide \&{} Conquer.

\Subsection{P.S.}

Чтобы получить более подробные объяснения можно было сходить на лекцию вживую,
можно пообщаться с присутствовавшими, а можно написать мне на почту \t{burunduk30@gmail.com}

\down
\color{dkgreen}{\bf Удачи!}
