Relajación lagrangiana

Recursos

Relajación lagrangiana

La relajación lagrangiana (Lagrangian Relaxation) consiste en transformar una restricción sobre una variable en un costo $\lambda$ y buscar de forma binaria el $\lambda$ óptimo.

El problema nos da un arreglo de longitud $N$ ($1 \le N \le 3 \cdot 10^5$) de enteros en el rango $[-10^9,10^9]$. Se nos da un $K$ ($1 \le K \le N$) y se pide elegir a lo sumo $K$ subarreglos disjuntos de modo que se maximice la suma de los elementos incluidos en algún subarreglo.

Intuición

El cuello de botella principal de cualquier solución de programación dinámica para este problema es tener que guardar cuántos subarreglos hemos creado hasta ahora.

Intentemos evitar eso. En lugar de guardar el número de subarreglos creados, asignamos una penalización de $\lambda$ por crear un subarreglo nuevo (es decir, cada vez que creamos un subarreglo penalizamos nuestra suma en $\lambda$).

Esto nos lleva al subproblema de hallar la suma máxima y el número de subarreglos usados si crear un subarreglo nuevo cuesta $\lambda$. Podemos resolverlo en $\mathcal{O}(N)$ con programación dinámica.

Sea $v$ la suma máxima alcanzable con penalización $\lambda$ y $c$ el número de subarreglos usados para lograr $v$. Entonces la suma máxima posible si usamos exactamente $c$ subarreglos es $v+\lambda c$. Observar que sumamos $\lambda c$ para deshacer la penalización.

Nuestro objetivo es hallar algún $\lambda$ tal que $c=K$ (asumiendo que $K$ es a lo sumo el número de elementos positivos). A medida que aumentamos $\lambda$, tiene sentido que $c$ disminuya porque estamos penalizando más los subarreglos. Así, podemos intentar buscar de forma binaria un $\lambda$ que haga $c=K$ y tomar como respuesta $v+\lambda c$ en el $\lambda$ óptimo.

Esta idea casi funciona, pero todavía hay algunas advertencias y condiciones muy importantes que no hemos considerado.

Geometría

Sea $f(x)$ la suma máxima si usamos a lo sumo $x$ subarreglos. Queremos hallar $f(K)$.

La primera condición es que $f(x)$ debe ser cóncava o convexa. Como $f(x)$ es creciente en este problema, esto significa que necesitamos que $f(x)$ sea cóncava: $f(x) - f(x - 1) \ge f(x + 1) - f(x)$. En otras palabras, cuanto más subarreglos agregamos, menos incrementamos la suma. Intuitivamente se ve que esto es cierto.

Consideremos las siguientes gráficas de $f(x)$ y $f(x)-\lambda x$. En este ejemplo, tenemos $\lambda=5$.

Aquí entra el hecho de que $f(x)$ es cóncava. Como la pendiente no es creciente, sabemos que $f(x) - \lambda x$ primero crece, luego se mantiene igual y finalmente decrece.

Sea $v(\lambda)$ la suma máxima óptima alcanzable con penalización $\lambda$ y $c(\lambda)$ el número de subarreglos usados para lograr $v(\lambda)$ (notar que si hay varias posibilidades, fijamos $c(\lambda)$ como el número máximo de subarreglos para lograr $v(\lambda)$). Estos valores se pueden calcular en $\mathcal{O}(N)$ con el enfoque de programación dinámica descrito arriba.

Cuando asignamos la penalización $\lambda$, estamos intentando hallar la suma máxima si crear un subarreglo reduce nuestra suma en $\lambda$. Así, $v(\lambda)$ será el máximo de $f(x) - \lambda x$ y $c(\lambda)$ será igual al $x$ más a la derecha que maximiza $f(x) - \lambda x$.

Dada la forma de $f(x) - \lambda x$, sabemos que $f(x) - \lambda x$ se maximiza en todos los puntos donde $\lambda$ es igual a la pendiente de $f(x)$ (estos puntos son rojos en la gráfica de arriba). Si no hay tales puntos, se maximiza en el punto más a la derecha donde la pendiente es menor que $\lambda$. Así, $c(\lambda)$ será el $x$ más a la derecha en el que la pendiente de $f(x)$ sigue siendo mayor o igual que $\lambda$.

Ahora sabemos exactamente qué representa $\lambda$: $\lambda$ es la pendiente y $c(\lambda)$ es el $x$ más a la derecha en el que la pendiente de $f(x)$ sigue siendo mayor o igual que $\lambda$.

Buscamos de forma binaria $\lambda$ y hallamos el mayor $\lambda$ tal que $c(\lambda) \ge K$. Sea el valor óptimo $\lambda_{\texttt{opt}}$. Entonces nuestra respuesta es $v(\lambda_{\texttt{opt}}) + \lambda_{\texttt{opt}} K$. Observar que esto funciona incluso si $c(\lambda_{\texttt{opt}}) \neq K$, porque en ese caso $c(\lambda_{\texttt{opt}})$ y $K$ estarán sobre la misma recta de pendiente $\lambda_{\texttt{opt}}$.

Como calcular $v(\lambda)$ y $c(\lambda)$ con la solución de programación dinámica descrita arriba toma $\mathcal{O}(N)$, esta solución corre en $\mathcal{O}(N\log{\sum A[i]})$.

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int main() {
	int n, k;
	cin >> n >> k;
 
	int a[n];
	for (int &i : a) { cin >> i; }
 
	/**
	 * @return the maximum sum along with the number of subarrays used
	 * if creating a subarray penalizes the sum by "lmb" and
	 * there is no limit to the number of subarrays you can create
	 */
	auto solve_lambda = [&](ll lmb) {
		pair<ll, ll> dp[n][2];
 
		dp[0][0] = {0, 0};
		dp[0][1] = {a[0] - lmb, 1};
 
		for (int i = 1; i < n; i++) {
			dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
 
			dp[i][1] =
			    max(make_pair(dp[i - 1][0].first + a[i] - lmb, dp[i - 1][0].second + 1),
			        make_pair(dp[i - 1][1].first + a[i], dp[i - 1][1].second));
		}
 
		return max(dp[n - 1][0], dp[n - 1][1]);
	};
 
	ll lo = 0;
	ll hi = 1e18;
	while (lo < hi) {
		ll mid = (lo + hi + 1) / 2;
		solve_lambda(mid).second >= k ? lo = mid : hi = mid - 1;
	}
 
	cout << solve_lambda(lo).first + lo * k << endl;
}

Problemas