\documentclass[12pt]{article}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{amsthm, amsmath, amssymb}
\usepackage[russian]{hyperref}
\usepackage{datetime}
\usepackage{cmap}
\usepackage{enumerate}
\usepackage{color}
\usepackage{picture}
\usepackage{minted}          

\def\O{\mathcal{O}}

\usepackage[left=2cm,right=2cm,
    top=2cm,bottom=2cm,bindingoffset=0cm]{geometry}

\renewcommand{\baselinestretch}{1.1}

\def\letus{%
    \mathord{\setbox0=\hbox{$\exists$}%
             \hbox{\kern 0.125\wd0%
                   \vbox to \ht0{%
                      \hrule width 0.75\wd0%
                      \vfill%
                      \hrule width 0.75\wd0}%
                   \vrule height \ht0%
                   \kern 0.125\wd0}%
           }%
}

\makeatletter
\newcommand{\minted@write@detok}[1]{%
  \immediate\write\FV@OutFile{\detokenize{#1}}}%

\newcommand{\minted@FVB@VerbatimOut}[1]{%
  \@bsphack
  \begingroup
    \FV@UseKeyValues
    \FV@DefineWhiteSpace
    \def\FV@Space{\space}%
    \FV@DefineTabOut
    %\def\FV@ProcessLine{\immediate\write\FV@OutFile}% %Old, non-Unicode version
    \let\FV@ProcessLine\minted@write@detok %Patch for Unicode
    \immediate\openout\FV@OutFile #1\relax
    \let\FV@FontScanPrep\relax
%% DG/SR modification begin - May. 18, 1998 (to avoid problems with ligatures)
    \let\@noligs\relax
%% DG/SR modification end
    \FV@Scan}
    \let\FVB@VerbatimOut\minted@FVB@VerbatimOut

\renewcommand\minted@savecode[1]{
  \immediate\openout\minted@code\jobname.pyg
  \immediate\write\minted@code{\expandafter\detokenize\expandafter{#1}}%
  \immediate\closeout\minted@code}
\makeatother

\parindent=0mm

\begin{document}
	\section{Ford-Bellman Algorithm}

	Обозначения: \\
	$n$~--- количество вершин, $m$~--- количество рёбер.
    \subsection{Задачи}
	\begin{enumerate}
		
		\item $w_e \geqslant 0$ \\
		Dijkstra Algorithm \\ 
		$\O(n^2)$ \\
		$\O(m\log n)$ \\
		$\O(m\log_\frac{m}{n} n)$ \\
		$\O(m + n\log n)$ \\
		$\O(m + n\log C)$ \\
		$\O(m + n\sqrt{\log C})$ 

		Если $w_e \in \mathbb{Z}$: \\
		Для неориентированного графа: $\O(n+m)$ \\
		Для ориентированного графа: $\O(m + n\log\log\min(n, C))$ \\
		$\letus~\exists$ алгоритм для ориентированного графа за $\O(n+m) \Rightarrow \exists$ IntegerSorting за $\O(n+m)$ 

		\item $w_e \in [-N; +\infty] \cap \mathbb{Z}$: \\
		1958' Ford-Bellman $\O(nm)$ \\
		1983' Gabow $\O(mn^{\frac{3}{4}}\log{nN})$ \\
		1989' Gabow and Tarjan $\O(mn^{\frac{1}{2}}\log{nN})$ \\
		1993' Goldberg $\O(mn^{\frac{1}{2}}(\log N + 1))$ \\
  	\end{enumerate}
  	\subsection{Алгоритм}
  	Можем найти следующую информацию: \\
	
	$\left[ 
		\begin{array}{l}
			d[v] \\ 
    		\nexists\:path \\
    		\nexists\:minimum\:path \Rightarrow \exists\:negative\:cycle\:(\O(n)) 
	  	\end{array}
	\right.$ \\

	$start$~--- стартовая вершина.

	\begin{minted}[mathescape]{c}
d[0,start] = 0
for v = 0..n-1:
	if (v != start)
		d[0,v] = +INF
for k = 0..n-1:
{
	for v = 0..n-1:
		d[k+1,v] = d[k,v]
	for e = 0..m-1: // $e:a\xrightarrow{ w }b$
		if (d[k+1,b] > d[k,a] + w)
		{
			d[k+1,b] = d[k,a] + w
			if (k == n-1)
				printf("negative cycle detected")
		}
}
    \end{minted}
    $d[k,v]$~--- минимальный путь из не более, чем $k$ рёбер от $start$ до $v$. \\
    На самом деле индекс $k$ не нужен. \\
    \begin{minted}[mathescape]{c}
d[start] = 0
for v = 0..n-1:
	if (v != start)
		d[v] = +INF
for k = 0..n-1:
	for e = 0..m-1:  // $e:a\xrightarrow{ w }b$ 
    	if (d[b] > d[a] + w)
    	{
    		d[b] = d[a] + w
    		if (k == n-1)
    			printf("negative cycle detected")
    	}
    \end{minted}
    $d[v]$ на $k$-ой итерации~--- учтены все пути длины $\leqslant k$ и ещё какие-то (из-за if-а пути могут получиться более длинными). \\
    $d[v] = +\infty \Rightarrow \nexists\:path$ \\

    \begin{minted}[mathescape]{c}
if (k == n-1)
	is[b] = 1
    \end{minted}
    $is[v]$~--- пометка о том, что до вершины $\nexists$ кратчайшего пути.\\
    Достижимые из всех помеченных вершин не имеют кратчайшего пути. \\
    На каждом отрицательном цикле хотя бы одна вершина помечена. \\
	Два способа:
	\begin{enumerate}
	\item Если сделаем внешних итераций в 2 раза больше, то в конце отметим все нужные вершины.
    \begin{minted}[mathescape]{c}
if (k == n-1 || is[a])
	is[b] = 1
    \end{minted}
    
    \item После алгоритма Форда-Беллмана запустим dfs из всех помеченных вершин.
    \begin{minted}[mathescape]{c}
for v = 0..n-1:
	if (is[v] && !used[v])
		dfs(v)
    \end{minted}
 
    \end{enumerate}
    $T=\O(nm)$\\
    $M=\O(m)$

    \subsection{Оптимизации}

    \begin{enumerate}

    \item $\O(km)$, где $k$~--- максимальное число рёбер в кратчайшем пути. В худшем случае $k = n$.

    \item Random Shuffle рёбер \\
    $E = \frac{n}{2}$~--- матожидание \\
    $E = 1 + \frac{1}{2}E$, $\frac{1}{2}$~--- вероятность того, что прошли второе ребро после первого, $E$~--- матожидание от следующей вершины. \\
    $E = 1 + \frac{1}{2}\left(1 + \frac{1}{2}\left(1+\frac{1}{2}\left(...\right)\right)\right) = 1 + \frac{1}{2} + \frac{1}{4} + \dots + \frac{1}{2^k} + \dots = 2$ \\
    $E = 2 \Rightarrow$ нужно $\frac{n}{2}$ итераций. \\
    Асимптотика: $E(T) = \frac{km}{2}, T \leqslant km$, где $k$~--- длина наидлиннейшего кратчайшего пути. \\

    \item Добавляем break, если на итерации не релаксировано ни одно ребро.

    \begin{minted}[mathescape]{c}
run = 1
while (run):
{
	run = 0
	for e = 0..m-1  // $e:a\xrightarrow{ w }b$
    	if (d[b] > d[a] + w)
    	{
    		d[b] = d[a] + w
    		run = 1
    	}
}
    \end{minted}

   	Случайный граф~--- веса ребер равновероятно выбираются на $[L..R]$, каждое ребро есть в графе с вероятностью $p$. 

    \textit{Замечание.} В случайном графе $k$ мало.

    \item Убираем оптимизацию 1 про \text{random\_shuffle}, оставляем оптимизацию 3 про break. \\
	Рассматриваем только ребра из вершин, расстояние до которых поменялось на прошлой итерации.

	Идея:
    \begin{minted}[mathescape]{c}
run = 1
A={start}
while (run):
{
	run = 0, B = NULL
	for e = 0..m-1  // $e:a\xrightarrow{ w }b$ 
    	if (d[b] > d[a] + w)
    	{
    		d[b] = d[a] + w
    		run = 1
    		B += {b}
    	}
	A = B
}
    \end{minted}
	
	Реализация:
    \begin{minted}[mathescape]{c}
queue<int> q;
q.push(start)
in_queue[start] = 1
while (q.size()):
{
	int v = q.top(), q.pop()
	in_queue[v] = 0  
	for e = 0..m-1  // $e:a\xrightarrow{ w }b$ 
    	if (d[b] > d[a] + w)
    	{
    		d[b] = d[a] + w
    		if (!in_queue[b]) 
// можем не добавлять $b$ в очередь, 
//потому что $b$ уже лежит там $\Rightarrow$ всё равно обработаем позже
    		{
    			q.push(b)
    			in_queue[b] = 1
    		}
    		run = 1
    	}
}
    \end{minted}

    \item Ацикличные графы 

    Мы умеем искать кратчайшие пути для ацикличных графов за $\O(n+m)$ с помощью TopSort.\\
    Выделим компоненты сильной связности, будем обрабатывать их в порядке Topsort-а. Для отдельной компоненты связности, когда до нее дошла очередь, запустим Ford-Bellman, который будет работать за $\O(V'E')$, где $V'$~--- количество вершин в данной компоненте сильной связности, $E'$~--- количество рёбер в данной компоненте сильной связности.

    \item Levit

    Есть очередь, как и в оптимизации 3.

    \begin{minted}[mathescape]{c}
if (w <= 0 && is[b] == 0)
{
	is[b] = 1
	q.push_front(b)
}	 
    \end{minted}

    Асимптотика: $\O(nm)$    
    \end{enumerate}

    \subsection{Поиск отрицательного цикла}
    \begin{minted}[mathescape]{c}
for k = 0..n-1:
	for e = 0..m-1:  // $e:a\xrightarrow{ w }b$ 
    	if (d[b] > d[a] + w)
    	{
    		d[b] = d[a] + w
    		p[b] = e
    		if (k == n-1)
    			printf("negative cycle detected")
    	}
    \end{minted}
    \textbf{\underline{Лемма 1}} \\
    $\forall\:b\:d[b] \geqslant d[p[b].a] + p[b].w$ \\
    $b \xleftarrow{ p[b].w } p[b].a $ \\
    Посмотрим на момент, когда мы сохранили $p[b]$ последний раз. В этот момент было равенство: $d[b] = d[p[b].a] + p[b].w$ \\
    После этого $d[b]$ не менялось, а $d[p[b].a]$ могло уменьшиться. Значит, неравенство действительно выполнено. \\
    
    \textbf{\underline{Лемма 2}} \\
    Если мы пойдем по ссылкам, начиная с какой-то вершины, то зациклимся.\\
    Пусть это не так. \\
    Идём до вершины, у которой нет ссылки. Очевидно, это может быть только вершина $start$. Причём, если у неё нет ссылки, значит $d[start] = 0$. \\
    $b \xleftarrow{\text{  }w_1\text{  }} a_1 \xleftarrow{\text{  }w_2\text{  }} a_2 \xleftarrow{\text{  }w_3\text{  }} \dots \leftarrow start$ \\
    $d[b] \geqslant d[a_1] + w_1 \geqslant d[a_2] + w_1 + w_2 \geqslant \dots \geqslant d[start] + \sum\limits_i w_i$ \\
    $d[b] \geqslant \sum\limits_i w_i$ \\
    $d[b] <$ все пути из $\leqslant n-1$ ребра, т.к. на $n$-ой итерации расстояние улучшилось. \\
    $d[b] \geqslant$ конкретный путь из $\leqslant n-1$ ребра. Путь: $start, \dots, a_2, a_1, b$. \\
    
    \textbf{\underline{Лемма 3}} \\
    Любой цикл по ссылкам отрицателен. \\
    Просумммируем неравенство леммы 1 по всем ребрам цикла. \\
    $d[v] \geqslant d[p[v].a] + p[v].w$ \\
    $d[b] \geqslant d[p[b].a] + p[b].w \geqslant d[p[p[b].a].a] + p[p[b].a].w + p[b].w \geqslant \dots \geqslant d[b] + \sum\limits_e w_e$\\
	$0 \geqslant \sum\limits_e w_e$ \\
	Посмотрим на последнее прорелаксированное ребро в цикле. Пусть это ребро $(v, u)$. Следующая по циклу после $u$~--- вершина $w$. Тогда расстояние $d[u]$ уменьшилось, значит по ребру $(u, w)$ неравенство леммы 1 выполнено строго, а значит и цикл строго отрицательного веса. \\


\section{Два указателя}

$x_n, w_n$ -- координата и вес $n$-й точки ($x_i \le x_{i+1}, w_i \ge 0$)

$[n,k]$ -- состояние динамики, первые $n$ точек разбили на $k$ отрезков
 
$p_{n,k}$ -- граница последнего отрезка

$q_{n,k}$ -- центр последнего отрезка

$o_{l,r}$ -- оптимальный центр отрезке $[l,r]$

Алгоритм выбора $o_{l,r}$ -- самая левая точка, что $\sum[l,o_{l,r}] \ge \sum(o_{l,r},r]$

\textbf{\underline{Цель рассуждения}} \\
Доказать, что $p_{n,k-1} \le p_{n,k} \le p_{n+1,k}$ 

Последовательность утверждений: \\

\textbf{\underline{Лемма 1}} \\
$o_{l,r-1} \le o_{l, r} \le o_{l+1,r}$ \\
1) $o_{l,r-1} \le o_{l, r}$ Доказательство: $\sum(o_{l,r},r] \ge  \sum(o_{l,r},r-1]$, значит мы точно не будем двигать $o_{l,r-1}$ правее чем $o_{l,r}$ \\
2) $ o_{l, r} \le o_{l+1,r}$ Доказательство: $\sum[l,o_{l,r}] \ge \sum[l+1,o_{l,r}]$, значит мы точно не будем двигать $o_{l+1,r}$ левее чем $o_{l,r}$ \\

\textbf{\underline{Лемма 2}} \\
$q_{n+1,k} \ge q_{n, k}$ \\
Доказательство: перейдем от оптимального $(n,k)$ разбиения к $(n+1,k)$ разбиению, не поменяв положение центра последнего отрезка $q_{n,k}$, 
функция увеличилась на $\mathbb{X} = w_{n+1}(x_{n+1} - x_{q_{n,k}})$ \\

\begin{picture}(1000,60)
\multiput(0,55)(0,-10){2}%
{\line(1,0){300}}%
\multiput(0,45)(10,0){31}%
{\line(0,1){10}}%
\multiput(255,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(245,64){$q_{n,k}$}%
\multiput(295,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(289,64){$x_{n}$}%
\multiput(230, 60)(70,0){2}%
{\line(0, -1){20}}%
\multiput(0,20)(0,-10){2}%
{\line(1,0){310}}%
\multiput(0,10)(10,0){32}%
{\line(0,1){10}}%
\multiput(255,24)(0,0){1}%
{\vector(0,-1){10}}%
\put(245,29){$q_{n,k}$}%
\multiput(305,24)(0,0){1}%
{\vector(0,-1){10}}%
\put(295,29){$x_{n+1}$}%
\multiput(230, 25)(80,0){2}%
{\line(0, -1){20}}
\end{picture} \\

Теперь перейдем к оптимальному $(n+1,k)$ разбиению, функция уменьшилась.Теперь перейдем к $(n,k)$ разбиению, функция уменьшилась на $\mathbb{Y} = w_{n+1}(x_{n+1} - x_{q_{n+1,k}})$ \\

\begin{picture}(1000,75)
\multiput(0,55)(0,-10){2}%
{\line(1,0){300}}%
\multiput(0,45)(10,0){31}%
{\line(0,1){10}}%
\multiput(255,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(245,64){$q_{n,k}$}%
\multiput(295,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(289,64){$x_{n}$}%
\multiput(230, 60)(70,0){2}%
{\line(0, -1){20}}%
\multiput(0,20)(0,-10){2}%
{\line(1,0){310}}%
\multiput(0,10)(10,0){32}%
{\line(0,1){10}}%
\multiput(245,24)(0,0){1}%
{\vector(0,-1){10}}%
\put(235,29){$q_{n+1,k}$}%
\multiput(305,24)(0,0){1}%
{\vector(0,-1){10}}%
\put(297,29){$x_{n+1}$}%
\multiput(230, 25)(80,0){2}%
{\line(0, -1){20}}
\end{picture} \\

Если $q_{n+1,k} < q_{n,k}$, то $\mathbb{Y} > \mathbb{X}$,
и, мы получаем противоречие с предположением, что исходное разбиение $(n,k)$ было оптимальным.\\

\textbf{\underline{Лемма 3}} \\
$p_{n+1,k} \ge p_{n, k}$. Доказательство: Возьмем оптимальное разбиение для $(n,k)$, теперь возьмем разбиение для $(n+1, k)$, такое что $p_{n,k} = p_{n+1,k}$ при этом $q_{n,k} \le q_{n+1,k}$ из  Леммы 2. \\

\begin{picture}(1000,80)
\multiput(0,55)(0,-10){2}%
{\line(1,0){300}}%
\multiput(0,45)(10,0){31}%
{\line(0,1){10}}%
\multiput(255,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(245,64){$q_{n,k}$}%
\multiput(295,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(289,64){$x_{n}$}%
\multiput(200, 60)(100,0){2}%
{\line(0, -1){20}}%
\put(190,65){$p_{n,k}$}%
\multiput(0,10)(0,-10){2}%
{\line(1,0){310}}%
\multiput(0,0)(10,0){32}%
{\line(0,1){10}}%
\multiput(255,14)(0,0){1}%
{\vector(0,-1){10}}%
\multiput(255,14)(0,0){1}%
{\vector(4,-3){12}}%
\multiput(255,14)(0,0){1}%
{\vector(4,-1){30}}%
\put(237,22){$o_{p_{n,k},x_{n+1}}$}%
\multiput(305,14)(0,0){1}%
{\vector(0,-1){10}}%
\put(295,19){$x_{n+1}$}%
\multiput(200, 15)(110,0){2}%
{\line(0, -1){20}}%
\put(180,20){$p_{n,k}$}
\end{picture}\\

Пусть существует лучшее разбиение, такое что у него $p_{n+1,k} < p_{n,k}$ \\

\begin{picture}(1000, 60)
\multiput(0,55)(0,-10){2}%
{\line(1,0){300}}%
\multiput(0,45)(10,0){31}%
{\line(0,1){10}}%
\multiput(255,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(245,64){$q_{n,k}$}%
\multiput(295,59)(0,0){1}%
{\vector(0,-1){10}}%
\put(289,64){$x_{n}$}%
\multiput(200, 60)(100,0){2}%
{\line(0, -1){20}}%
\put(190,65){$p_{n,k}$}%
\multiput(0,10)(0,-10){2}%
{\line(1,0){310}}%
\multiput(0,0)(10,0){32}%
{\line(0,1){10}}%
\multiput(255,14)(0,0){1}%
{\vector(0,-1){10}}%
\multiput(255,14)(0,0){1}%
{\vector(4,-3){12}}%
\multiput(255,14)(0,0){1}%
{\vector(4,-1){30}}%
\put(245,19){$q_{n+1,k}$}%
\multiput(305,14)(0,0){1}%
{\vector(0,-1){10}}%
\put(295,19){$x_{n+1}$}%
\multiput(190, 15)(120,0){2}%
{\line(0, -1){20}}%
\put(180,20){$p_{n+1,k}$}
\end{picture}\\

Тогда из Леммы 1 следует, что $o_{p_{n,k},x{n+1}} \ge q_{n+1,k}$, значит $w_{n+1} (x_{n+1} - x_{q_{n+1,k}}) \ge w_{n+1} (x_{n+1} - x_{o_{p_{n,k},x_{n+1}}})$, противоречие с тем, что изначально у нас было оптимальное разбиение для $(n,k)$\\

\textbf{\underline{Лемма 4}} \\
$p_{n,k} \ge p_{n,k-1}$ \\
Пусть $k=3$ и $p_{n,k} < p_{n,k-1}$. \\
(ось $x$ направлена справа налево)\\
$l$ -- длина двух правых отрезков из первого разбиения\\

\begin{picture}(1000,75)
\multiput(160,55)(0,-10){2}%
{\line(1,0){140}}%
\multiput(160,45)(10,0){15}%
{\line(0,1){10}}%
\put(200,65){$p_{l,2}$}%
\put(295,64){$x_{n}$}%
\multiput(180, 60)(60,0){1}%
{\line(0, -1){20}}%
\multiput(160, 60)(60,0){1}%
{\line(0, -1){20}}%
\multiput(210, 60)(60,0){1}%
{\line(0, -1){20}}%
\multiput(300, 60)(60,0){1}%
{\line(0, -1){20}}%
\multiput(160,10)(0,-10){2}%
{\line(1,0){140}}%
\multiput(160,0)(10,0){15}%
{\line(0,1){10}}%
\put(220,20){$p_{n,2}$}%
\put(295,19){$x_{n}$}%
\multiput(160, 15)(70,0){3}%
{\line(0, -1){20}}%
\multiput(160, 42)(60,0){1}%
{\line(1, 0){20}}%
\put(158,33){$n-l$}
\end{picture}\\
Смотрим на правые два отрезка в обоих разбиениях, видим противоречие с Леммой 3, т.к. $l < n$, значит $p_{l,2} \le p_{n,2}$.\\

Теперь пусть $k$ -- произвольное и $p_{n,k} < p_{n,k-1}$. Т.к. в первом разбиении больше отрезков, в какой-то момент получится такая ситуация, что $i$ правых отрезков первого разбиения, меньше чем $i$ правых отрезков второго разбиения. Рассмотрим первую такую ситуацию.\\
$l_1$ -- длина $i$ правых отрезков первого разбиения\\
$l_2$ -- длина $i$ правых отрезков второго разбиения.\\
(ось $x$ направлена справа налево)\\

\begin{picture}(1000,85)
\multiput(0,55)(0,-10){2}%
{\line(1,0){500}}%
\multiput(0,45)(10,0){51}%
{\line(0,1){10}}%
\put(170,68){$p_{l_1,i}$}%
\multiput(180, 60)(60,0){5}%
{\line(0, -1){20}}%
\multiput(150, 60)(60,0){1}%
{\line(0, -1){20}}%
\multiput(500, 60)(60,0){1}%
{\line(0, -1){20}}%
\multiput(0,10)(0,-10){2}%
{\line(1,0){500}}%
\multiput(0,0)(10,0){51}%
{\line(0,1){10}}%
\put(190,20){$p_{l_2,i}$}%
\multiput(140, 15)(60,0){8}%
{\line(0, -1){20}}
\end{picture} \\

Получается противоречие: по Лемме 3 из того, что $ l_1 < l_2$ следует, что $p_{l_2,i} \ge p_{l_1,i}$
                       
\end{document}

                       
\end{document}