Арифметическое кодирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Забыли обновить l)
Строка 1: Строка 1:
'''Арифметическое кодирование''' (англ. ''Arithmetic coding'') {{---}} алгоритм сжатия информации без потерь, который при кодировании ставит в соответствие тексту вещественное число из отрезка <tex>[0; 1)</tex>.
+
Convex hull trick {{---}} один из методов оптимизации динамического программирования [[http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование]], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задачь, решемых методом динамического программирования с <math>O(n^2)</math> до <tex>O(n\cdot\log(n))</tex>. Техника впервые появилась в 1995 году (задачу на нее предложили в USACO {{---}} национальной олимпиаде США по программированию). Массовую известность получила после IOI (международной олимпиады по программированию для школьников) 2002.
Данный метод, как и [[Алгоритм Хаффмана|алгоритм Хаффмана]], является [[Энтропия случайного источника|энтропийным]], т.е. длина кода конкретного символа зависит от частоты встречаемости этого символа в тексте. Арифметическое кодирование показывает более высокие результаты сжатия, чем алгоритм Хаффмана, для данных с неравномерными распределениями вероятностей кодируемых символов. Кроме того, при арифметическом кодировании каждый символ кодируется нецелым числом бит, что эффективнее кода Хаффмана (теоретически, символу <tex>a</tex> с вероятностью появления <tex>p(a)</tex> допустимо ставить в соответствие код длины <tex>-\log_2 p(a)</tex>, следовательно, при кодировании алгоритмом Хаффмана это достигается только с вероятностями, равными обратным степеням двойки).
+
                                                                                 
 
+
                                                                                  ==Пример задачи, решаемой методом convex hull trick==
== Принцип действия ==
+
                                                                                  Рассмотрим задачу на ДП:
=== Кодирование ===
+
                                                                                  {{Задача
На вход алгоритму передаются текст для кодирования и список частот встречаемости символов.
+
                                                                                  |definition = Есть <math>n</math> деревьев с высотами <tex>a_1, a_2, \dots, a_n</tex> (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
# Рассмотрим отрезок <tex>[0; 1)</tex> на координатной прямой.
+
                                                                                  бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
# Поставим каждому символу текста в соответствие отрезок, длина которого равна частоте его появления.
+
                                                                                  срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенной кол-во монет. Причем стоимость
# Считаем символ из входного потока и рассмотрим отрезок, соответствующий этому символу. Разделим этот отрезок на части, пропорциональные частотам встречаемости символов.
+
                                                                                  бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен <tex>i</tex>, то цена заправки
# Повторим пункт (3) до конца входного потока.
+
                                                                                  равна <tex>c_i</tex>.  Изначально пила заправлена.
# Выберем любое число из получившегося отрезка, которое и будет результатом арифметического кодирования.
+
                                                                                  Также известны следующие ограничения : <tex>c_n = 0, a_1 = 1, a_i</tex> возрастают, <tex>c_i</tex> убывают. Изначально пила заправлена.
 
+
                                                                                  (убывание и возрастание нестрогие)
=== Псевдокод ===
+
                                                                                  }}
 
+
                                                                                  (Задача H с Санкт-Петербургских сборов к РОИ 2016[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf])
*<math>\mathtt{s}\,</math> {{---}} текст, подаваемый на вход;
+
                                                                                                                                    </noinclude>
*<math>\mathtt{n}\,</math> {{---}} длина исходного текста;
+
                                                                                                                                    <includeonly>{{#if: {{{neat|}}}|
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
+
                                                                                                                                    <div style="background-color: #fcfcfc; float:left;">
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
+
                                                                                                                                    <div style="background-color: #ddd;">'''Задача:'''</div>
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
+
                                                                                                                                    <div style="border:1px dashed #2f6fab; padding: 8px; font-style: italic;">{{{definition}}}</div>
*<math>\mathtt{Segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
+
                                                                                                                                    </div>|
**<math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
+
                                                                                                                                    <table border="0" width="100%">
**<math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;
+
                                                                                                                                    <tr><td style="background-color: #ddd">'''Задача:'''</td></tr>
*<math>\mathtt{left}\,</math>, <math>\mathtt{right}\,</math> {{---}} границы отрезка, содержащего возможный результат арифметического кодирования.
+
                                                                                                                                    <tr><td style="border:1px dashed #2f6fab; padding: 8px; background-color: #fcfcfc; font-style: italic;">{{{definition}}}</td></tr>
 
+
                                                                                                                                    </table>}}
<code>
+
                                                                                                                                    </includeonly>
'''struct''' Segment:
+
                                                                                                                                   
    '''double''' left
+
                                                                                                                                    ==Наивное решение==
    '''double''' right
+
                                                                                                                                    Сначала заметим важный факт : т.к. <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> будет срублено.
'''Segment'''[m] defineSegments(letters: '''char'''[m], probability: '''double'''[m]):
+
                                                                                                                                    База динамики : <tex>dp[1] = 0</tex>, т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.
    '''Segment'''[m] segment
+
                                                                                                                                    Переход динамики : понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед  <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> монет.
    '''double''' l = 0
+
                                                                                                                                    Итогвая формула пересчета : <tex>dp[i] = \min\limits_{j=1...i-1} (dp[j] + a[i] \cdot c[j])</tex>.
    '''for''' i = 0 '''to''' m - 1
+
                                                                                                                                   
        segment[letters[i]].left = l
+
                                                                                                                                    Посмотрим на код выше описанного решения:
        segment[letters[i]].right = l + probability[i]
+
                                                                                                                                    '''int''' <tex>\mathtt{simpleDP}</tex>('''int''' a[n], '''int''' c[n])
        l = segment[letters[i]].right
+
                                                                                                                                    dp[1] = 0
    '''return''' segment
+
                                                                                                                                    dp[2] = dp[3] = ... = dp[n] = <tex>\infty</tex>
 
+
                                                                                                                                    '''for'''  i = 1..n-1
'''double''' arithmeticCoding(letters: '''char'''[m], probability: '''double'''[m], s: '''char'''[n]):
+
                                                                                                                                    dp[i] = <tex>+\infty</tex>
    '''Segment'''[m] segment = defineSegments(letters, probability)
+
                                                                                                                                    '''for''' j = 0..i-1
    '''double''' left = 0
+
                                                                                                                                    '''if''' (dp[j] + a[i] <tex>\cdot</tex> c[j] < dp[i])
    '''double''' right = 1
+
                                                                                                                                    dp[i] = dp[j] + a[i] <tex>\cdot</tex> c[j]
    '''for''' i = 0 '''to''' n - 1
+
                                                                                                                                    '''return''' dp[n]
        '''char''' symb = s[i]
+
                                                                                                                                    Нетрудно видеть, что такая динамика работает за <tex>O(n^2)</tex>.
        '''double''' newRight = left + (right - left) * segment[symb].right
+
                                                                                                                                   
        '''double''' newLeft = left + (right - left) * segment[symb].left
+
                                                                                                                                    ==Ключевая идея оптимизации==
        left = newLeft
+
                                                                                                                                    Для начала сделаем замену обозначений. Давайте обозначим <tex>dp[j]</tex> за <tex>b[j]</tex>, <tex>a[i]</tex> за <tex>x[i]</tex>, а <tex>c[j]</tex> за <tex>k[j]</tex>.
        right = newRight
+
                                                                                                                                   
    '''return''' (left + right) / 2
+
                                                                                                                                    Теперь формула приняла вид <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>.
</code>
+
                                                                                                                                   
 
+
                                                                                                                                    Сопоставим каждому <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>[left; right]</tex> число, содержащее наименьшее количество знаков в двоичной записи.
+
                                                                                                                                   
 
+
                                                                                                                                    [[Файл: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>[0; 1)</tex>, разделенном на части, длины которых равны вероятностям появления символов в тексте, подотрезок, содержащий входное вещественное число. Символ, соответствующий этому подотрезку, дописываем в ответ.
+
                                                                                                                                   
# Нормируем подотрезок и вещественное число.
+
                                                                                                                                    ==Цель нижней огибающей множества прямых==
# Повторим пункты 1{{---}}2 до тех пор, пока не получим ответ.
+
                                                                                                                                    Пусть мы считаем динамику для <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>.
 
+
                                                                                                                                   
=== Псевдокод ===
+
                                                                                                                                    Воспользуемся идеей алгоритма построения выпуклой оболочки множества точек. Заведем 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>
 
+
                                                                                                                                   
*<math>\mathtt{code}\,</math> {{---}} вещественное число, подаваемое на вход;
+
                                                                                                                                    Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
*<math>\mathtt{n}\,</math> {{---}} длина восстанавливаемого текста;
+
                                                                                                                                   
*<math>\mathtt{m}\,</math> {{---}} мощность алфавита исходного текста;
+
                                                                                                                                    [[Файл:picture2convexhull.png]]
*<math>\mathtt{letters[m]}\,</math> {{---}} массив символов, составляющих алфавит исходного текста;
+
                                                                                                                                    [[Файл:picture3convexhull.png]]
*<math>\mathtt{probability[m]}\,</math> {{---}} массив вероятностей обнаружения символа в тексте;
+
                                                                                                                                   
*<math>\mathtt{segment}\,</math> {{---}} структура, задающая подотрезок отрезка <tex>[0; 1)</tex>, соответствующего конкретному символу на основе частотного анализа. Имеет поля:
+
                                                                                                                                    {{Теорема
** <math>\mathtt{left}\,</math> {{---}} левая граница подотрезка;
+
                                                                                                                                    |id=th1239.
** <math>\mathtt{right}\,</math> {{---}} правая граница подотрезка;
+
                                                                                                                                    |statement=Алгоритм построения нижней огибающей множества прямых корректен.
** <math>\mathtt{character}\,</math> {{---}} значение символа.
+
                                                                                                                                    |proof=Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя {{---}} предпоследнюю.
 
+
                                                                                                                                   
<code>
+
                                                                                                                                    Пусть <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>, т.е. её можно удалить из множества
'''struct''' Segment:
+
                                                                                                                                    }}
    '''double''' left
+
                                                                                                                                   
    '''double''' right
+
                                                                                                                                    ==Детали реализации:==
    '''char''' character
+
                                                                                                                                    Будем хранить 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>
 
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
'''Segment'''[m] defineSegments(letters: '''char'''[n], probability: '''double'''[n]):
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ==Реализация==
    '''Segment'''[m] segment
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''int''' <tex>\mathtt{ConvexHullTrick}</tex>('''int''' a[n], '''int''' c[n])
    '''double''' l = 0
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    st[1] = 1
    '''for''' i = 0 '''to''' m - 1
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    from[1] = -<tex>\infty</tex><font color=green>// первая прямая покрывает все x-ы, начиная с -∞ </font>
        segment[i].left = l
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = 1 <font color=green>// текущий размер выпуклой оболочки </font>
        segment[i].right = l + probability[i]
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    pos = 1 <font color=green>// текущая позиция первого такого j, что x[i] \geqslant front[st[j]] </font >
        segment[i].character = letters[i]
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''for'''  i = 2..n 
        l = segment[i].right
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''while''' (front[pos] < x[i]) <font color=green>// метод 1 указателя (ищем первое pos, такое что x[i] покрывается "областью действия" st[pos]-той прямой </font >
    '''return''' segment
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    pos = pos + 1
 
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    j = st[pos]
'''string''' arithmeticDecoding(letters: '''char'''[m], probability: '''double'''[m], code: '''double''', n: '''int'''):
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    dp[i] = K[j]<math>\cdot</math>a[i] + B[j]
    '''Segment'''[m] segment = defineSegments(letters, probability)  
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' (i < n)  <font color=green>// если у нас добавляется НЕ последняя прямая, то придется пересчитать выпуклую оболочку </font >
    '''string''' s = ""
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    K[i] = c[i]  <font color=green>// наши переобозначения переменных </font >
    '''for''' i = 0 '''to''' n - 1
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
        '''for''' j = 0 '''to''' m - 1
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    x = -<tex>\infty</tex>  
            '''if''' code >= segment[j].left '''and''' code < segment[j].right
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''while''' ''true''  
                s += segment[j].character
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    j = st[sz]
                code = (code – segment[j].left) / (segment[j].right – segment[j].left)
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
                '''break'''
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' (x > from[sz]) '''break'''  <font color=green>// перестаем удалять последнюю прямую из множества, если новая прямая пересекает ее позже, чем начинается ее "область действия" </font >
    '''return''' s
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = sz - 1<font color=green>// удаляем последнюю прямую, если она лишняя </font >
</code>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    st[sz + 1] = i 
 
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    from[sz + 1] = x <font color=green>// добавили новую прямую </font >
'''Замечание:''' кодировщику и декодировщику должно быть известно, когда завершать работу. Для этого можно передавать в качестве аргумента длину текста или символ конца файла, после которого процесс должен быть остановлен.
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = sz + 1
 
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''return''' dp[n]
'''Замечание:''' Несмотря на преимущества арифметического кодирования, существует проблема при его практическом применении из-за несовершенства представления чисел с плавающей точкой в памяти компьютера {{---}} поскольку некоторые дробные числа не могут быть точно представлены в двоичном коде, используемом современными процессорами (например, <tex>\dfrac{1}{3}</tex>), границы символов будут округлены, что может повлечь за собой неверную работу алгоритма при больших объёмах данных. В общем случае, алгоритм можно модифицировать так, чтобы результатом было дробное число. В такой реализации вероятность встречи символа представляется в виде рационального числа. Поскольку в каждой итерации будет переход из текущего отрезка в один из его <tex>m</tex> подотрезков, кратных по длине <tex>n</tex>, а всего итераций <tex>n</tex>, в конечном результате знаменатель дроби не превысит <tex>n^{n}</tex>, а поскольку сумма всех вероятностей встречи символов равна <tex>1</tex>, полученная дробь будет находиться в промежутке <tex>[0; 1)</tex>.
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Здесь функция <tex>\mathtt{divide}</tex>(a, b) возвращает нужное(*) округление a / b. Приведем её код :
 
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''int''' <tex>\mathtt{divide}</tex>('''int''' a, '''int''' b)
== Пример работы ==
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    delta = 0
Рассмотрим в качестве примера строку <tex>abacaba</tex>:
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' (a '''mod''' b ≠ 0) delta = 1
=== Кодирование ===
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''if''' ((a > 0 '''and''' b > 0) '''or''' (a < 0 '''and''' b < 0)) '''return''' [a / b] + delta
{|class="wikitable"
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    '''return''' -[|a| / |b|]
!Символ||Частота появления
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Такая реализация будет работать за O(n).
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.285714</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ==Динамический convex hull trick==
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Заметим, что условия на прямые, что <tex>k[i]</tex> возрастает/убывает и <tex>x[i]</tex> убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой {{---}} отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016[http://neerc.ifmo.ru/school/camp-2016/problems/20160318a.pdf]).
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.142857</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|}
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за <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>
[[Файл:Code_png.png|thumb|right|200px|Пример работы кодировщика ]]
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Файл:picture4convexhull.png]]
{|class="wikitable"
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
!Считанный символ||Левая граница отрезка||Правая граница отрезка
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Чтобы уметь вставлять прямую в множество будем хранить <math>std::set</math> (или любой аналог в других языках программирования) пар <tex>(k, st)</tex> <tex>(коэффицент прямой, ее номер в глобальной нумерации)</tex>. Когда приходит новая прямая, ищем последнюю прямую с меньшим угловым коэффицентом, чем у той прямой, которую мы хотим добавить в множество. Поиск такой прямой занимает <tex>O(\log(n))</tex>. Начиная с найденной прямой выполняем "старый" алгоритм (удаляем, пока текущая прямая множества бесполезна). И симметричный алгоритм применяем ко всем прямым справа от нашей (удаляем правого соседа нашей прямой, пока она пересекает нас позже, чем своего правого соседа).
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>1</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Асимптотика решения составит <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>.
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      == Альтернативный подход ==
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Другой способ интерпретировать выражение <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> двумя бинарными или одним тернарным поиском
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.489796</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Асимптотика алгоритма по-прежнему составит <tex>O(n \cdot \log(n))</tex>
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Файл:picture5convexhull.png]]
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Докажем то, что описанный выше алгоритм корректен. Для этого достаточно показать, что если имеются <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>.
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      {{Теорема
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.414113</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |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>.
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.413025</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      |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>.
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.412093</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Подставим эти неравенства в (*). Получим цепочку неравенств : <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>0.411471</tex>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
 
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      Из доказанной теоремы и следует корректность алгоритма.
=== Декодирование ===
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
Код: <tex>0.411471</tex>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      ==См. также==
[[Файл:decode1_png.png|thumb|right|200px|Пример работы декодировщика ]]
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull
{|class="wikitable"
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
!Декодируемый символ||Код
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.411471</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Категория:Дискретная математика и алгоритмы]]
|-
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Категория: Динамическое программирование]]
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.720074</tex></p>
+
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      [[Категория: Способы оптимизации методов динамического программирования]]
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.520259</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.910454</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.373178</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.653061</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.285714</tex></p>
 
|}
 
 
 
'''Замечание:''' при декодировании текста можно не только нормализовывать рабочий отрезок и текущий код, но и уменьшать рабочий отрезок (аналогично кодированию), не изменяя значение кода.
 
=== Декодирование (второй способ)===
 
Код: <tex>0.411471</tex>
 
[[Файл:decode2_png.png|thumb|right|200px|Пример работы декодировщика (второй способ) ]]
 
{|class="wikitable"
 
!Декодируемый символ||colspan="4" |Границы отрезка
 
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>||<p style="text-align:center;"><tex>0.857143</tex></p>||<p style="text-align:center;"><tex>1</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.489796 </tex></p>||<p style="text-align:center;"><tex>0.571429</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.326531 </tex></p>||<p style="text-align:center;"><tex>0.419825 </tex></p>||<p style="text-align:center;"><tex>0.466472 </tex></p>||<p style="text-align:center;"><tex>0.489796 </tex></p>
 
|-
 
|<p style="text-align:center;"><tex>c</tex></p>||<p style="text-align:center;"><tex>0.326531</tex></p>||<p style="text-align:center;"><tex>0.379842</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.414113</tex></p>||<p style="text-align:center;"><tex>0.417921 </tex></p>||<p style="text-align:center;"><tex>0.419825</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>b</tex></p>||<p style="text-align:center;"><tex>0.406497</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.413025</tex></p>||<p style="text-align:center;"><tex>0.414113</tex></p>
 
|-
 
|<p style="text-align:center;"><tex>a</tex></p>||<p style="text-align:center;"><tex>0.410849</tex></p>||<p style="text-align:center;"><tex>0.412093</tex></p>||<p style="text-align:center;"><tex>0.412714</tex></p>||<p style="text-align:center;"><tex>0.413025</tex></p>
 
 
 
|}
 
== Оценка длины кодового слова ==
 
{{Теорема  
 
|statement=При арифметическом кодировании длина кодового слова не превышает энтропии исходного текста.
 
 
 
 
 
||proof=Введём следующие обозначения:
 
*<tex>l</tex> {{---}} длина текста,
 
*<tex>n</tex> {{---}} размер алфавита,
 
*<tex>f_i</tex> {{---}} частота встречаемости символа,
 
*<tex>p_i</tex> {{---}} вероятность вхождения символа.
 
 
 
Размер сообщения <tex>L</tex> можно найти по формуле:
 
<div style="text-align: center;"><tex> L = \prod\limits_{i=1}^l p_{fi} = \prod\limits_{i=1}^n p_{i}^{f_{i}}</tex></div>
 
 
 
Число бит в закодированном тексте:
 
<div style="text-align: center;"><tex>\log_2 L = \sum\limits_{i=1}^n f_i\cdot \log_2 p_i =  l \cdot \sum\limits_{i=1}^n p_i\cdot \log_2 p_i = -l \cdot H(p_1...p_n)</tex></div>
 
}}
 
 
 
== См. также ==
 
* [[Алгоритм_Хаффмана | Алгоритм Хаффмана]]
 
* [[Алгоритмы_LZ77_и_LZ78 | Алгоритмы LZ77 и LZ78]]
 
* [[Энтропия_случайного_источника | Энтропия случайного источника]]
 
 
 
== Источники информации ==
 
* [http://ru.wikipedia.org/wiki/%D0%90%D1%80%D0%B8%D1%84%D0%BC%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BA%D0%BE%D0%B4%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5 Википедия {{---}} Арифметическое кодирование]
 
* [https://en.wikipedia.org/wiki/Arithmetic_coding Wikipedia {{---}} Arithmetic coding]
 
* [http://www.sernam.ru/cod_3.php Арифметическое кодирование]
 
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/arithmetic-coding-2006 Визуализатор арифметического кодирования]
 
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Теория вероятности]]
 
[[Категория: Алгоритмы сжатия]]
 

Версия 21:16, 18 января 2017

Convex hull trick — один из методов оптимизации динамического программирования [[1]], использующий идею выпуклой оболочки. Позволяет улучшить ассимптотику решения некоторых задачь, решемых методом динамического программирования с [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] (в метрах). Требуется спилить их все, потратив минимальное количество монет на заправку
                                                                                 бензопилы. Но пила устроена так, что она может спиливать только по 1 метру от дерева, к которому ее применили. Также после
                                                                                 срубленного метра (любого дерева) пилу нужно заправлять, платя за  бензин определенной кол-во монет. Причем стоимость
                                                                                 бензина зависит от срубленных (полностью) деревьев. Если сейчас максимальный индекс срубленного дерева равен [math]i[/math], то цена заправки
                                                                                 равна [math]c_i[/math].  Изначально пила заправлена.
                                                                                 Также известны следующие ограничения : [math]c_n = 0, a_1 = 1, a_i[/math] возрастают, [math]c_i[/math] убывают. Изначально пила заправлена.
(убывание и возрастание нестрогие)
                                                                                 (Задача H с Санкт-Петербургских сборов к РОИ 2016[2])
                                                                                                                                   
                                                                                                                                   
                                                                                                                                   
                                                                                                                                   ==Наивное решение==
                                                                                                                                   Сначала заметим важный факт : т.к. [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], т.к. изначально пила заправлена и высота первого дерева равна 1, по условию задачи.
                                                                                                                                   Переход динамики :  понятно, что выгодно рубить сначала более дорогие и низкие деревья, а потом более высокие и дешевые (док-во этого факта оставляется читателям как несложное упражнение, т.к. эта идея относится скорее к теме жадных алгоритмнов, чем к теме данной статьи). Поэтому перед  [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 = 1..n-1
                                                                                                                                   dp[i] = [math]+\infty[/math]
                                                                                                                                   for j = 0..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](x0, y0)[/math] , таких что все они принадлежат одной из прямых и при этом нету ни одной прямой [math]y’(x)[/math], такой что [math]y’(x0) \lt  y0[/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[i]) = \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](xL, yL)[/math] — точка пересечения [math]sz - 1[/math]-й прямой множества и [math]sz[/math]-й, а [math](xR, yR)[/math] — точка пересечения новой прямой, которую мы хотим добавить в конец множества и [math]sz[/math]-й. Нас будут интересовать только их [math]x[/math]-овые координаты [math]xL[/math] и [math]xR[/math], соответственно. Если оказалось, что новая прямая пересекает [math]sz[/math]-ю прямую выпуклой оболочки позже, чем [math]sz[/math][math]sz - 1[/math]-ю, т.е. [math](xL \geqslant xR)[/math], то [math]sz[/math]-ю удалим из нашего множества, иначе — остановимся. Так будем делать, пока либо кол-во прямых в стеке не станет равным 2, либо [math]xL[/math] не станет меньше [math]xR.[/math]
                                                                                                                                   
                                                                                                                                   Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно [math]1[/math] раз добавится в стек и максимум [math]1[/math] раз удалится. Значит время работы перестройки выпуклой оболочки займет [math]O(n)[/math] суммарно.
                                                                                                                                   
                                                                                                                                   Picture2convexhull.png
                                                                                                                                   Picture3convexhull.png
                                                                                                                                   
Теорема:
Алгоритм построения нижней огибающей множества прямых корректен.
Доказательство:
[math]\triangleright[/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; xR] : y[sz](x) \lt = Y(x)[/math], а т.к. [math] K[sz] \lt K[sz - 1][/math], то при [math]x \in [xL; + \infty] : y[sz - 1](x) \geqslant y[sz](x)[/math]. Если [math]xL \lt xR[/math], то при [math]x \in [xL; xR] : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)[/math], т.е. на отрезке [math][xL; xR][/math] прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же [math]xL \gt xR[/math], то она ниже всех на отрезке [math][xL; xR] = \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] операций суммарно. Также массив front[] можно хранить в целых числах, округляя х-координаты в сторону лежащих правее по оси 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
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    from[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  
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    from[sz + 1] = x // добавили новую прямую 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    sz = sz + 1
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    return dp[n] 
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Здесь функция [math]\mathtt{divide}[/math](a, b) возвращает нужное(*) округление a / b. Приведем её код :
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    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|]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Такая реализация будет работать за O(n).
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ==Динамический convex hull trick==
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    Заметим, что условия на прямые, что [math]k[i][/math] возрастает/убывает и [math]x[i][/math] убывает/возрастает выглядят достаточно редкими для большинства задач. Пусть в задаче таких ограничений нет. Первый способ борьбы с этой проблемой — отсортировать входные данные нужным образом, не испортив свойств задачи (пример : задача G c Санкт-Петербургских сборов к РОИ 2016[3]).
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     Но рассмотрим общий случай. По-прежнему у нас есть выпуклая оболочка прямых, имея которую мы за [math]O(\log(n))[/math] можем найти   [math]dp[i][/math], но теперь вставку [math]i[/math]-й прямой в оболочку уже нельзя выполнить описанным ранее способом за [math]O(1)[/math] в среднем. У нас есть выпуклая оболочка, наша прямая пересекает ее, возможно, «отсекая» несколько отрезков выпуклой оболочки в середине (рис. 4 : красная прямая — та, которую мы хотим вставить в наше множество). Более формально : теперь наша новая прямая будет ниже остальных при [math]x \in [x1; x2][/math], где [math]x1, x2 \in R[/math] — точки пересечения с некоторыми прямыми, причем [math]x2[/math] не обязательно равно [math]+ \infty[/math]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     Picture4convexhull.png
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     Чтобы уметь вставлять прямую в множество будем хранить [math]std::set[/math] (или любой аналог в других языках программирования) пар [math](k, st)[/math] =  [math](коэффицент прямой, ее номер в глобальной нумерации)[/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 c_{x} + k \cdot c_{y} \Leftrightarrow (b_{x} - c_{x}) \lt k \cdot (c_{y} - b_{y})[/math] и [math](b, u) \lt (c, u) \Leftrightarrow b_{x} + k \cdot b_{y} \lt a_{x} + k \cdot a_{y} \Leftrightarrow (a_{x} - b_{x}) \gt k \cdot (b_{y} - a_{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]
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     Из доказанной теоремы и следует корректность алгоритма.
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     ==См. также==
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     1) http://neerc.ifmo.ru/wiki/index.php?title=Статические_выпуклые_оболочки:_Джарвис,_Грэхем,_Эндрю,_Чен,_QuickHull
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     
                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     2) http://neerc.ifmo.ru/wiki/index.php?title=Динамическое_программирование