Оптимизация разделяй-и-властвуй



Разделяй-и-властвуй (divide-and-conquer) — стандартная оптимизация динамики, позволяющая решать задачи об оптимальном разбиении массива из $n$ элементов на $k$ подотрезков за $O(n k \log n)$ (если эта динамика удовлетворяет некоторому условию, о котором мы поговорим позже), в то время как наивная динамика решает эту задачу за $O(n^2 k)$. Иными словами, мы оптимизируем динамику такого вида:

$$dp[ki][ni] = \min_{i < ni} dp[ki - 1][i] + w(i, ni)$$

где $dp[ki][ni]$ — оптимальная стоимость разбить первые $ni$ элементов массива на $ki$ подотрезков оптимальным образом, а $w(i, ni)$ — стоимость подотрезка $(i, ni]$.

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

Алгоритм

Задача: Дан массив неотрицательных чисел $a$ длины $n$. Назовем мощностью подотрезка квадрат суммы его элементов. Необходимо разбить массив $a$ на $k$ подотрезков таким образом, чтобы минимизировать сумму мощностей подотрезков разбиения. Иными словами, выделить такие $k - 1$ чисел (границы подотрезков разбиения) $i_1$, $i_2$, $\ldots$, $i_{k - 1}$, чтобы

$$(a_1 + a_2 + \ldots + a_{i_1 - 1})^2 + (a_{i_1} + a_{i_1 + 1} + \ldots + a_{i_2 - 1})^2 + \ldots + (a_{i_{k - 1}} + \ldots + a_{n})^2$$

было минимально.

В нашем случае $dp[ki][ni]$ — минимальная стоимость разбиения первых $n$ элементов на $ki$ подотрезков, а $w(i, ni)$ — мощность подотрезка $(i, ni]$, то есть $(a_{i + 1} + a_{i + 2} + \ldots + a_{ni})^2$. Далее везде мы будем подразумевать, что $w(i, ni)$ можно считать за $O(1)$. Для этого необходимо заранее посчитать префиксные суммы массива $a$ и выразить мощность подотрезка через квадрат разности префиксных сумм его концов.

Базовый алгоритм решает эту задачу за $O(n^2 k)$: мы перебираем количество отрезков по возрастанию, перебираем индекс $ni$, после чего перебираем все возможные индексы $i$ и выбираем среди них оптимальный ответ. Сходу совершенно не ясно, где здесь есть место для улучшения.

Нашу динамику можно представить как таблицу $k \times n$, и $ki$-й ее слой пересчитывается через $ki-1$-й. Тогда давайте заметим, что не обязательно перебирать индексы $ni$ по возрастанию, мы можем перебирать их в любом порядке, в котором нам захочется. Давайте научимся находить очередной слой нашей динамики за $O(n \log n)$, тогда на подсчет $k$ слоев нам как раз понадобится $O(n k \log n)$ времени.

Давайте заметим, что если бы мы для каждой точки $ni$ откуда-то узнали оптимальные точки $i$, через которые нужно пересчитываться, то мы бы могли просто для каждого $ni$ обновить ответ $dp[ki][ni] := dp[ki - 1][i] + w(i, ni)$. Давайте обозначим такое оптимальное $i$ как $opt[ki][ni]$ (если есть несколько индексов $i$, дающих оптимальный ответ, выберем среди них наименьший). Тогда зная $opt[ki][ni]$, мы можем за $O(1)$ найти $dp[ki][ni]$.

Но как же нам найти $opt[ki][ni]$? В этом нам поможет то самое условие, которое мы должны наложить на динамику, чтобы оптимизация разделяй-и-властвуй работала, о котором говорилось в начале статьи.

Условие монотонности точки разреза: Оптимизация разделяй-и-властвуй работает тогда и только тогда, когда $opt[ki][ni] \le opt[ki][ni + 1]$ для любых $ki$ и $ni$.

Иными словами, при фиксированном $ki$ точка пересчета $opt[ki][ni]$ должна не убывать по $ni$, то есть чем правее $ni$, тем правее левый конец последнего отрезка.

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

Но как же условие монотонности точки разреза поможет нам быстро найти все значения $opt[ki][ni]$? Давайте вернемся к нашему алгоритму, который вычислял значения $dp[ki][ni]$ последовательно. По умолчанию мы знаем, что $opt[ki][ni]$ — это какое-то число из интервала $[0, ni)$. Однако если мы уже посчитали $opt[ki][ni - 1]$, то так как $opt[ki][ni - 1] \le opt[ki][ni]$, то мы можем сократить интервал поиска до $[opt[ki][ni - 1], ni)$. С первого взгляда может показаться, что это уже помогает нам находить все значения $dp[ki][ni]$ за линейное время, но это не так. Представьте, что все значения $opt[ki][ni]$ равны нулю. Это никак не противоречит условию монотонности точки разреза, однако в этом случае наша оптимизация никак нам не помогает: мы все еще для каждого индекса $i$ перебираем все индексы от $0$ до $ni$.

Замечание: Здесь важно не путать метод разделяй-и-властвуй и метод двух указателей. Метод двух указателей работает при более сильных условиях на динамику. Ему кроме монотонности точки разреза также необходимо, чтобы при движении точки пересчета вправо ответ сначала улучшался, а потом после оптимальной точки пересчета начинал ухудшаться. В таком случае можно найти все оптимальные точки пересчета за $O(n)$. Однако в нашем случае никто не гарантирует нам, что стоимости пересчета убывают до оптимальной точки разреза и возрастают после нее. Нам лишь сказали, что для меньших индексов оптимальная точка разреза не может быть правее, чем для бóльших.

Что же нам делать, раз наш линейный алгоритм не сработал? Давайте попробуем найти оптимальную точку разреза для индекса $m = \left\lfloor \frac{n}{2} \right\rfloor$ ($\left\lfloor . \right\rfloor$ означает округление вниз). Тогда если мы нашли $opt[ki][m]$, то мы знаем, что для всех индексов $i$, меньших $m$, верно, что $opt[ki][i] \le opt[ki][m]$, а для всех индексов $i$, бóльших $m$, верно, что $opt[ki][i] \ge opt[ki][m]$. Тогда мы разбили облость поиска оптимальной точки разреза для левой и правой половин массива на два множества, которые пересекаются только по $opt[ki][m]$. Тогда, если как в примере выше все $opt[ki][ni]$ равны нулю, то мы выясним, что $opt[ki][m] = 0$, и для всей левой половины массива мы значем, что оптимальная точка разреза тогда точно равна $0$.

Мы нашли оптимальную точку разреза для индекса $m$, после чего на границы поиска оптимальной точки разреза для левой и правой половин массива появились ограничения. Тогда давайте рекурсивно запустим поиск для левой и правой половин. Там мы будем искать оптимальные точки разреза для индекса $\left\lfloor \frac{n}{4} \right\rfloor$ от $0$ до $\min (opt[ki][m], \left\lfloor \frac{n}{4} \right\rfloor - 1)$, и для индекса $\left\lfloor \frac{3n}{4} \right\rfloor$ от $opt[ki][m]$ до $\left\lfloor \frac{3n}{4} \right\rfloor - 1$, и так далее.

Каждый раз нам дают некоторый отрезок $[L, R)$ индексов массива, для которых надо найти оптимальные точки разреза, а также с более высоких уровней рекурсии у нас уже есть некоторые ограничения на эти точки разреза: мы точно знаем, что они не меньше $cl$ и меньше $cr$. Тогда мы выбираем индекс $M = \left\lfloor \frac{L + R}{2} \right\rfloor$, находим для него оптимальную точку разреза на интервале $[cl, \min(M, cr))$, после чего запускаемся рекурсивно для отрезка $[L, M)$, на котором нижнее ограничение — это все еще $cl$, а верхнее ограничение обновляется числом $opt[ki][M] + 1$ (ведь правая граница считается невключительно), потому что все индексы в левой половине отрезка меньше $M$; а также запускаемся рекурсивно из отрезка $[M + 1, R)$, на котором верхнее ограничение остается равным $cr$, а нижнее ограничение становится равно $opt[ki][M]$, потому что все индексы правой половины отрезка больше $M$.

Для большего понимания приведем код алгоритма:

// find dp[ki][ni] for all ni: l <= ni < r if cl <= opt[ki][ni] < cr
void divide(int ki, int L, int R, int cl, int cr) {
    if (L >= R) { // empty segment
        return;
    }
    int M = (L + R) / 2;
    int opt; // optimal partition point for dp[ki][M]
    for (int i = cl; i < min(M, cr); i++) {
        if (dp[ki][M] > dp[ki - 1][i] + w(i, M)) {
            dp[ki][M] = dp[ki - 1][i] + w(i, M);
            opt = i;
        }
    }
    divide(ki, L, M, cl, opt + 1);
    divide(ki, M + 1, R, opt, cr);
}

В конце такой рекурсивной процедуры мы найдем значения $dp[ki][ni]$ для всех индексов массива. Остается лишь понять, почему этот сложный рекурсивный процесс разделяй-и-властвуй работает за $O(n \log n)$.

Каждый раз мы делим длину рассматриваемых отрезков в два раза, поэтому глубина рекурсии будет равна $O(\log n)$. Давайте докажем, что все вызовы с одного уровня рекурсии суммарно отработают за $O(n)$.

В одном конкретном вызове мы делаем константное количество операций, а также запускаем цикл от $cl$ до $\min(cr, M)$. Можно считать, что один рекурсивный запуск работает за $O(cr - cl)$. На верхнем уровне рекурсии $cl = 0$ и $cr = n$, так что это $O(n)$. После чего на следующем уровне рекурсии полуинтервал $[cl, cr)$ делится на два: $[cl, opt]$ и $[opt, cr)$, и так далее. На каждом уровне рекурсии изначальный полуинтервал $[0, n)$ разбивается на несколько отрезков: $[0, i_1]$, $[i_1, i_2]$, $[i_2, i_3]$, $\ldots$ $[i_j, n)$. Соседние отрезки пересекаются по одному элементу, так что на одном уровне рекурсии каждый индекс $i$ будет использован для пересчета максимум два раза, поэтому всего мы сделаем $O(n)$ операций на одном уровне рекурсии, что в итоге даст нам $O(n \log n)$ на все уровни. Таким образом, итоговая асимптотика алгоритма — $O(n k \log n)$, что и требовалось доказать.

Замечание: Обратите внимание на то, что мы нигде не пользовались тем, чему собственно равны $opt[ki][ni]$, нам только важно, что они не убывают. С первого взгляда может показаться, что нам нужно, чтобы $opt$ тоже делил отрезок $[cl, cr]$ примерно пополам, но как видно из доказательства, это нигде не используется.

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

Достаточное условие для монотонности точки разреза

Как мы уже поняли, необходимым и достаточным условием для работы оптимизации разделяй-и-властвуй является условие монотонности точки разреза, то есть $opt[ki][ni] \le opt[ki][ni + 1]$ для любых $ki$ и $ni$. Однако практика показывает, что доказать это утверждение обычно сложно, если не знать, как к нему подступиться. В этом разделе мы познакомимся с достаточным условием на то, чтобы условие монотонности точки разреза выполнялось, которое чаще всего несложно проверить.

Это условие — неравенство четырехугольника для функции $w$. Определения и доказательства можно прочитать в специальной статье про неравенство четырехугольника.

Лямбда-оптимизация и 1D1D — не панацея

Если вы уже читали статью про лямбда-оптимизацию, вы могли заметить, что если функция $w$ удовлетворяет неравенству четырехугольника, то задачу оптимального разбиения на $k$ подотрезков можно решить при помощи комбинациии лямбда-оптимизации и 1D1D-оптимизации за $O(n \log n \log C)$, что чаще всего лучше, чем $O(n k \log n)$ у разделяй-и-властвуй. Получается, в большинтве ситуаций разделяй-и-властвуй бесполезна? Не совсем!

Во-первых, разделяй-и-властвуй находит ответ не только для какого-то фиксированного $k$, но и для всех меньших, в то время как лямбда-оптимизация помогает нам найти ответ только для конкретного $k$. Если в задаче нужно вывести ответ для всех $ki \le k$, то разделяй-и-властвуй будет работать быстрее.

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

В-третьих, стоит заметить, что решение лямбда-оптимизацией работает за $O(n \log n \log C)$ при условии, что функцию $w$ можно легко вычислять за $O(1)$, однако это не всегда так! Иногда вычисление функции $w$ — это сложно и может занимать хоть линейное время.

Но ведь разделяй-и-властвуй тоже пользуется тем, что функцию $w$ мы вычисляем быстро, скажете вы. На самом деле это необязательно, давайте разберемся с этим в следующем разделе.

Разделяй-и-властвуй для трудновычислимых стоимостей подотрезков разбиения

Когда мы раньше говорили про стоимость подотрезка $w(i, ni)$, мы всегда подразумевали, что эту стоимость можно легко вычислить за $O(1)$, но это не всегда так. Что делать в противном случае? Рассмотрим пример задачи:

Задача: Дан массив чисел длины $n$. Стоимостью подотрезка этого массива назовем количество пар элементов этого подотрезка, значения которых совпадают. Необходимо разбить массив на $k$ подотрезков, минимизировав суммарную стоимость подотрезков разбиения.

В нашем случае $w$ — это количество пар одинаковых элементов на подотрезке. Несложно доказать, что $w$ удовлетворяет неравенству четырехугольника, однако совершенно неясно, как находить $w$ для произвольного подотрезка быстро. Что же делать?

Первым делом стоит потратить $O(n \log n)$ времени и сжать элементы массива (можно и $O(n)$, но это непринципиально). Теперь все элементы массива не превосходят $n$, но при этом какие элементы были одинаковыми, такие и остались. Теперь можно легко вычислять $w(l, r)$ за $O(r - l)$: пройдемся по отрезку, посчитаем массив $cnt$, в котором для каждого значения сохраним количество элементов с таким значением, после чего ответом будет сумма $\frac{cnt[c] \cdot (cnt[c] - 1)}{2}$ по всем числам $c$. Тогда итоговая асимптотика разделяй-и-властвуй будет $O(n^2 k \log n)$ вместо $O(n k \log n)$. Нельзя ли сделать как-то лучше?

На самом деле можно. Давайте заметим, что если у нас есть массив $cnt$ и ответ для отрезка $[a, b]$, то мы можем легко пересчитать этот массив и ответ для подотрезка $[a - 1, b]$. Пусть на позиции $a - 1$ стоит элемент $x$. Тогда $w(a - 1, b) = w(a, b) + cnt[x]$, а в массиве $cnt$ нужно лишь прибавить единицу на позиции $x$. Давайте заметим, что для фиксированной правой границы $m$ в процессе работы разделяй-и-властвуй мы перебираем левую границу из динапазона $[cl, cr]$. Тогда если мы изначально за $O(n)$ посчитаем $w(cr, m)$, то далее все остальные $w(i, m)$ мы сможем посчитать суммарно за $O(cr - cl)$, что как раз таки совпадает с асимптотикой, если бы мы считали $w$ за константное время.

Посмотрим, какая в этом случае будет асимптотика: на каждом уровне динамики для каждой позиции массива мы один раз насчитываем $w(cr, m)$ за $O(n)$, а потом все остальное будет работать как и раньше суммарно за $O(n \log n)$. Поэтому итоговая асимптотика — $O(n^2 k + n k \log n) = O(n^2 k)$. Немного лучше, но все еще плохо. За такую же асимптотику работало бы решение динамикой без оптимизации, если бы мы воспользовались трюком с расширением отрезка. Нужно улучшать сильнее!

Давайте попробуем еще чаще переиспользовать уже посчитанные значения $w$. Давайте заметим, что аналогично переходу от отрезка $[a, b]$ к $[a - 1, b]$, мы можем перейти и к отрезку $[a + 1, b]$, а также мы аналогично можем двигать и правую границу. Тогда пускай мы сейчас ищем оптимальный ответ для позиции $m$ с отрезка $[l, r]$, пересчитываясь через все позиции из отрезка $[cl, cr]$. Мы перебрали все эти позиции, к примеру, по убыванию, поняли, что оптимальная среди них — это $cm$, и в данный момент у нас посчитан массив $cnt$ для отрезка $[cl, m]$. После чего нам нужно рекурсивно запуститься из левой и правой половин и искать оптимальные точки пересчета для индексов $m_l = \left\lfloor \frac{l + m - 1}{2} \right\rfloor$ и $m_r = \left\lfloor \frac{m + 1 + r}{2} \right\rfloor$ среди позиций $[cl, cm]$ и $[cm, cr]$ соответственно. Но ведь эти позиции не так далеко от текущего отрезка $[cl, m]$, для которого на данный момент посчитан массив $cnt$. Давайте будем двигать левую и правую границу текущего отрезка, пока он не станет равен $[cm, m_l]$, после чего мы сможем продолжить рекурсивно считать динамику для левой половины, затем, когда мы закончим рекурсивный вызов из левой половины, мы сможем подвинуть текущий отрезок в $[cr, m_r]$ и продолжить рекурсивное вычисление динамики из левой половины.

Таким образом, мы не начинаем считать массив $cnt$ для каждой правой границы по отдельности, а переиспользуем уже вычисленные значения. В любой момент времени если нам надо посчитать $w$ для отрезка $[a, b]$, а на данный момент у нас есть массив $cnt$ для отрезка $[c, d]$, мы просто постепенно двигаем левую и правую границу отрезка на $1$, пока не получим нужный отрезок.

Замечание: Обратите внимание, что если, к примеру, $a < b < c < d$, то если мы будем двигать сначала правую границу от $d$ до $b$, а потом левую от $c$ до $a$, то в какой-то момент у нас будет массив $cnt$ для отрезка $[c, b]$ отрицательной длины, что может привести к каким-то ошибкам. Аналогичная ситуация может произойти, если $c < d < a < b$. Чтобы избежать такой проблемы, стоит сначала применять операции, которые расширяют отрезок, а потом уже те, которые его укорачивают. То есть сначала нужно уменьшать левую границу и увеличивать правую, пока это нужно, а потом уже увеличивать левую и уменьшать правую.

Давайте оценим время работы получившегося алгоритма. Кроме стандартных $O(n k \log n)$ на разделяй-и-властвуй, мы теперь еще тратим время на передвижение левых и правых границ текущего отрезка, на котором посчитано $w$. Но при этом передвижение границы на $1$ занимает $O(1)$ времени, так что нам достаточно лишь посчитать количество таких перемещений.

Давайте докажем, что когда мы запустились от подотрезка $[l, r]$ и ищем для этих индексов оптимальные точки пересчета среди точек на отрезке $[cl, cr]$, на текущем уровне рекурсии мы сделаем $O((cr - cl) + (r - l))$ перемещений. Почему это так? Изначально границы отрезка стоят на $[cr, m]$, после чего мы постепенно передвигаем левую границу вплодь до $cl$, на что мы тратим $cr - cl$ перемещений. Затем нам нужно переместить границы в $[cm, m_l]$. При этом левая граница все еще остается на отрезке $[cl, cr]$, а правая все еще остается на отрезке $[l, r]$, поэтому количество перемещений не будет превышать $(cr - cl) + (r - l)$. После чего мы запустимся рекурсивно из левой половины массива, там мы будем как-то двигать границы, но это нас не касается, потому что эти перемещения учтутся на более глубоких уровнях рекурсии. После окончания рекурсивного вызова границы текущего отрезка $w$ могут быть абсолютно произвольными, однако мы точно знаем, что левая граница все еще лежит на отрезке $[cl, cr]$, а правая лежит на $[l, r]$, потому что внутри рекурсии мы пытаемся пересчитывать динамику для индексов с отрезка $[l, r]$ через отрезок $[cl, cr]$, поэтому чтобы от текущего отрезка перейти к отрезку $[cr, m_r]$, нам опять понадобится не более $(cr - cl) + (r - l)$ операций перемещения. Больше перемещений на текущем уровне рекурсии не будет, так что мы доказали, что мы сделаем $O((cr - cl) + (r - l))$ операций перемещения.

Раньше на одном уровне рекурсии мы работали за $O(cr - cl)$, поэтому добавление еще одного $O(cr - cl)$ будет все еще суммироваться в $O(n k \log n)$. Осталось лишь доказать то же самое про $O(r - l)$. Но это можно оценить точно так же! Это ведь длины отрезков нашего разделяй-и-властвуй. На каждом уровне сумма длин этих отрезков не превышает $n$, потому что эти отрезки не пересекаются. А так как уровней рекурсии будет $O(\log n)$, то итоговая асимптотика будет равна $O(n k \log n)$. Точно такая же, как и для $w$, вычисляемой за $O(1)$. С примером кода можно ознакомиться по ссылке.

Замечание: Как вы могли уже понять, никуда специально двигать границы запроса на самом деле не нужно. Просто когда мы хотим узнать стоимость какого-то подотрезка $[a, b]$, мы двигаем границы от той позиции, в которой они сейчас находятся, к нужному отрезку.

Источники

Задачи