Дискретный метод Лагранжа - Алгоритмика
Дискретный метод Лагранжа

Дискретный метод Лагранжа

Эта статья — одна из серии. Рекомендуется сначала прочитать все предыдущие.

В качестве финальной оптимизации мы рассмотрим метод, вдохновленный методом множителей Лагранжа, также в олимпиадной среде называемый «лямбда-оптимизацией».

Модификация задачи

Рассмотрим немного измененную версию исходной задачи. Пусть нам нужно покрыть те же точки, но теперь нас не ограничивают жёстко в количестве отрезков, а просто штрафуют на какую-то константу $\lambda$ за использование каждого дополнительного отрезка.

Нашу оптимизируемую функцию $g$ тогда можно выразить через $f$ следующим образом:

$$ g[i] = \min_{k < i} \{f[i, k] + k \cdot \lambda \} $$ Однако её можно считать по более оптимальной формуле, не сводя к вычислению $f$: $$ g[i] = \lambda + \min_{k < i} \{g[k] + (x_{i-1} - x_k)^2 \} $$

Эту динамику можно посчитать за $O(n)$: мы ровно это и делали в прошлой статье про Convex Hull Trick.

Идея

Наблюдение 1. Если в оптимальном решении для $g_i$ мы для какого-то $\lambda$ использовали ровно $k$ отрезков, то это же решение будет оптимальным и для $f[i, k]$.

Наблюдение 2. Если уменьшать $\lambda$, то оптимальное количество отрезков для $g_i$ будет увеличиваться.

Основная идея оптимизации: сделаем бинпоиск по $\lambda$, внутри которого будем находить оптимальное решение для $g_i$ с заданным $\lambda$. Если оптимальное $k^\star$ получилось больше $k$, то следующая $\lambda$ должна быть меньше, а в противном случае наоборот. Когда $k^\star$ совпадёт с $k$, просто выведем чистую стоимость получившегося решения без штрафов.

Таким образом, задача решается за $O(n \log n + n \log m)$, если сортировку точек для CHT делать заранее, а не внутри бинпоиска.

Реализация

pair<ll, int> dp[maxn]; // dp[i] - (ответ, число отрезков)

void init() {
    for (int i = 0; i < maxn; i++) {
        dp[i] = make_pair(inf, 0);
    }
}

pair<ll, int> check(ll x) { // это можно соптимизировать
    init();
    dp[0] = make_pair(0ll, 0); // 1-индексация
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = min(dp[i], {dp[j].first + cost[j + 1][i] + x, dp[j].second + 1});
        }
    }
    return dp[n];
}

ll solve() {
    ll l = -1e14; // границы надо подбирать очень аккуратно!
    ll r = 1;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        pair<ll, int> x = check(mid);
        if (x.second >= k)
            l = mid;
        else
            r = mid;
    }
    pair<ll, int> result = check(l);
    return result.first - l * return.second; // вычитаем штрафы
}

Автор извиняется за качество реализации и призывать читателя её переписать и закомитить.

Существование решения

Мы пропустили один нюанс: почему вообще существует такая $\lambda$, что оптимальное $k^\star = k$?

В общем случае возможно, что функция $k^\star(\lambda)$ через него «перескакивает», и это действительно проблема: одной лишь монотонности не достаточно, чтобы решать подобным образом произвольные задачи с ограничением на число объектов.

Но в нашей задаче можно заметить следующее: функция $f[i, j]$ нестрого вогнутая (выпуклая вверх) по своему второму аргументу, то есть

$$ f[i, j] - f[i, j-1] \leq f[i, j+1] - f[i, j] $$

Иными словами, дополнительная «выгода» от добавления каждого следующего отрезка не увеличивается.

Теперь, на выражение для модифицированной динамики

$$ g[i] = \min_{k < i} \{f[i, k] + k \cdot \lambda \} $$

можно смотреть как на минимизацию скалярного произведение точек $(f[i, k], k)$ и вектора $(1, \lambda)$.

Так как верхняя огибающая точек $(f[i, k], k)$ выпукла, для каждой точки будет существовать $\lambda$, которая упирается в него, и следовательно $k^\star = k$ гарантированно найдется.