Slope Trick

Tutoriales

Del último enlace (modificado):

El slope trick es una forma de representar una función que cumple las siguientes condiciones:

• Se puede dividir en varias secciones, donde cada sección es una función lineal (usualmente) con pendiente entera.
• Es una función convexa/cóncava. En otras palabras, la pendiente de cada sección es no decreciente o no creciente al escanear la función de izquierda a derecha.

En general es aplicable como una optimización de DP.

El resto de este módulo asume que se conoce la idea básica de este truco. En particular, se debería poder resolver el siguiente problema (es casi idéntico al primer problema del tutorial de zscoder):

Está bien si las explicaciones resultaron confusas; el ejemplo de abajo debería ayudar a aclarar.

Buy Low Sell High

Solución lenta

Sea $dp[i][j]$ la cantidad máxima de dinero que se puede tener el día $i$ si se tienen exactamente $j$ acciones ese día. La respuesta final será $dp[N][0]$. Esta solución corre en $\mathcal{O}(N^2)$.

vector<vl> dp = {{0}};
int N;
 
int main() {
	re(N);
	F0R(i, N) {
		int x;
		re(x);
		dp.pb(vl(i + 2, -INF));
		F0R(j, i + 1) {
			ckmax(dp.bk[j + 1], dp[sz(dp) - 2][j] - x);
			ckmax(dp.bk[j], dp[sz(dp) - 2][j]);
			if (j) ckmax(dp.bk[j - 1], dp[sz(dp) - 2][j] + x);
		}
	}
	int cnt = 0;
	trav(t, dp) {
		pr("dp[", cnt++, "] = ");
		pr('{');
		F0R(i, sz(t)) {
			if (i) cout << ", ";
			cout << setw(3) << t[i];
		}
		ps('}');
	}
}

Si corremos esto sobre el primer caso de ejemplo, obtenemos la siguiente tabla:

Input:

9
10 5 4 7 9 12 6 2 10

Output:

dp[0] = {  0}
dp[1] = {  0, -10}
dp[2] = {  0,  -5, -15}
dp[3] = {  0,  -4,  -9, -19}
dp[4] = {  3,  -2,  -9, -16, -26}
dp[5] = {  7,   0,  -7, -16, -25, -35}
dp[6] = { 12,   5,  -4, -13, -23, -35, -47}
dp[7] = { 12,   6,  -1, -10, -19, -29, -41, -53}
dp[8] = { 12,  10,   4,  -3, -12, -21, -31, -43, -55}
dp[9] = { 20,  14,   7,  -2, -11, -21, -31, -41, -53, -65}

Sin embargo, ¡los valores de DP se ven bastante especiales! Específicamente, sea

Entonces $dif[i][j]\le dif[i][j+1]$ para todo $j\ge 0$. En otras palabras, $dp[i][j]$ como función de $j$ es cóncava hacia abajo.

Solución completa

Procesaremos las acciones en orden. Supongamos que estamos considerando el $i$-ésimo día, donde las acciones valen $p_i$. Podemos reemplazar (comprar o vender una acción) en el enunciado por (comprar, y luego vender entre 0 y 2 acciones).

• Si actualmente tenemos $j$ acciones y balance global $b$, entonces después de comprar, $j$ aumenta en uno y $b$ disminuye en $p_i$. Así, fijamos $dp[i][j]=dp[i-1][j-1]-p_i$ para todo $j$. Observar que las diferencias entre cada dos elementos consecutivos de $dp[i]$ no han cambiado.

• Si elegimos vender una acción, esto es equivalente a fijar $dp[i][j]=\max(dp[i][j],dp[i][j+1]+p_i)$ para todo $j$ al mismo tiempo. Por la condición de concavidad, $dp[i][j]=dp[i][j+1]+p_i$ se cumplirá para todo $j$ menor que un cierto umbral, mientras que $dp[i][j]$ permanecerá sin cambios para todos los demás. Así, esto es equivalente a insertar $p_i$ en la lista de diferencias manteniendo la condición de que las diferencias estén en orden.

• Así, elegir vender entre 0 y 2 acciones se representa agregando $p_i$ a la lista de diferencias dos veces. Después de eso, deberíamos extraer la diferencia más chica de la lista porque no podemos terminar con una cantidad negativa de acciones.

dp[4]  = {  3,  -2,  -9, -16, -26}
dif[4] = {  5,   7,   7,  10}

dp[5]  = {  x,  -6, -11, -18, -25, -35}
dif[5] = {  x,   5,   7,   7,  10}

dp[5]  = {  3,  -2,  -9, -16, -25, -35}
dif[5] = {  5,   7,   7,   9,  10}

dp[5]  = {  7,   0,  -7, -16, -25, -35}
dif[5] = {  7,   7,   9,   9,  10}

La implementación es bastante simple; mantenemos una cola de prioridad que representa $dif[i]$ y permite extraer el elemento mínimo. Después de agregar $i$ elementos, $ans$ guarda el valor actual de $dp[i][i]$. Al final, sumamos todas las diferencias de $dif[N]$ para ir de $dp[N][N]$ a $dp[N][0]$.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N;
	cin >> N;
	priority_queue<int, vector<int>, greater<int>> pq;
	long long ans = 0;
	for (int i = 0; i < N; ++i) {
		int p;
		cin >> p;
		ans -= p;
		pq.push(p);
		pq.push(p);
		pq.pop();
	}
	for (int i = 0; i < N; ++i) {
		ans += pq.top();
		pq.pop();
	}
	cout << ans << "\n";
}

Extensión

Stock Trading (USACO Camp): ¿Qué pasa si la cantidad de acciones puede ser negativa, pero nunca se pueden tener más de $L$ acciones ni menos de $-L$?

Potatoes & Fertilizers

Simplificar el problema

En lugar de decir que mover fertilizante del segmento $i$ al segmento $j$ cuesta $|i-j|$, diremos que cuesta $1$ mover fertilizante de un segmento a un segmento adyacente.

Sean los valores de $a_1,a_2,\ldots,a_N$ después de todas las transferencias $a_1',a_2',\ldots,a_N'$. Si conocemos esta secuencia final, ¿cuánto costaron las transferencias (en el mejor escenario)? Resulta que esto es simplemente

Podemos mostrar que esta es una cota inferior y que es alcanzable. El término $D=\sum_{j=1}^i(a_j-a_j')$ denota el número de unidades de fertilizante que se mueven del segmento $i$ al segmento $i+1$. A saber, si $D$ es positivo entonces $D$ unidades de fertilizante se movieron del segmento $i$ al segmento $i+1$; en caso contrario, $-D$ unidades de fertilizante se movieron en la dirección opuesta. Observar que nunca es óptimo tener fertilizante moviéndose en ambas direcciones.

Sea $dif_i=a_i-b_i$ y definamos $d_j=\sum_{i=1}^jdif_i$ para cada $0\le j\le N$. De forma similar, definamos $dif_i'=a_i'-b_i$ y $d_j'=\sum_{i=1}^jdif_i'$. Como queremos $dif_i'\ge 0$ para todo $i$, deberíamos tener $d_0=d_0'\le d_1'\le \cdots\le d_N'=d_N.$ Recíprocamente, toda secuencia $(d_0',d_1',\ldots,d_N')$ que cumple esta propiedad corresponde a una forma válida de asignar valores de $(a_1',a_2',\ldots,a_N')$.

Ahora se puede verificar que $C=\sum_{i=1}^{N-1}|d_i-d_i'|$. Esto tiene sentido ya que mover una unidad de fertilizante una posición es equivalente a cambiar uno de los $d_i$ en uno (aunque $d_0,d_N$ siempre permanecen iguales).

Solución lenta

Para cada $0\le i\le N$ y $0\le j\le d_N$, sea $dp[i][j]$ el costo mínimo para determinar $d_0',d_1',\ldots,d_i'$ tales que $d_i'\le j$. Observar que por definición, $dp[i][j]\ge dp[i][j+1]$. Podemos calcular estos valores fácilmente en $\mathcal{O}(N\cdot d_N)$.

Solución completa

Similar a antes, ¡esta DP es cóncava hacia arriba para un $i$ fijo! Dada una función lineal a trozos $f_i(x)$ que toma como entrada $x$ y devuelve $dp[i][x]$, necesitamos soportar las siguientes dos operaciones para transformar esta función en $f_{i+1}$.

• Sumar $|x-k|$ a la función para algún $k$
• Fijar $f(x)=\min(f(x),f(x-1))$ para todo $x$

De nuevo, esto se puede hacer con una cola de prioridad. En lugar de guardar las diferencias consecutivas, guardamos los puntos donde la pendiente de la función lineal a trozos cambia en uno.

• La primera operación corresponde a insertar $k$ en la cola de prioridad dos veces porque la pendiente aumenta en dos en $x=k$.
• La última operación simplemente corresponde a quitar el elemento más grande de la cola de prioridad.

Esta solución corre en $\mathcal{O}(N\log N)$.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int N;
ll fst = 0;                 // value of DP function at 0
priority_queue<ll> points;  // points where DP function changes slope
 
int main() {
	cin >> N;
	vector<ll> dif(N + 1);
	for (int i = 1; i <= N; ++i) {
		int a, b;
		cin >> a >> b;
		dif[i] = a - b + dif[i - 1];
	}
	assert(dif[N] >= 0);  // assume solution exists
	for (int i = 1; i < N; ++i) {
		if (dif[i] < 0) fst -= dif[i], dif[i] = 0;
		fst += dif[i];
		points.push(dif[i]);
		points.push(dif[i]);
		points.pop();
	}
	while (points.size()) {
		ll a = points.top();
		points.pop();
		fst -= min(a, dif[N]);
	}
	cout << fst << "\n";
}

USACO Landscaping

Esto se parece a la tarea anterior (estamos moviendo tierra en lugar de fertilizante), así que no es demasiado difícil adivinar que el slope trick es aplicable.

Solución lenta

Sea $dp[i][j]$ el costo mínimo para mover tierra alrededor de los primeros $i$ canteiros de modo que los primeros $i-1$ canteiros tengan todos la cantidad correcta de tierra mientras que el $i$-ésimo canteiro tiene $j$ unidades extra de tierra (o le faltan $-j$ unidades de tierra si $j$ es negativo). La respuesta será $dp[N][0]$.

Solución completa

Esta DP es cóncava hacia arriba para cualquier $i$ fijo. Para obtener $dp[i+1]$ a partir de $dp[i]$ debemos poder soportar las siguientes operaciones.

• Desplazar la curva de DP $A_i$ unidades a la derecha.
• Desplazar la curva de DP $B_i$ unidades a la izquierda.
• Sumar $Z\cdot |j|$ a $DP[j]$ para todo $j$.
• Fijar $DP[j] = \min(DP[j],DP[j-1]+X)$ y $DP[j] = \min(DP[j],DP[j+1]+Y)$ para todo $j$.

Como antes, ayuda mirar las diferencias $dif[j]=DP[j+1]-DP[j]$ en su lugar. Mantendremos deques separados para $dif$ según si $j < 0$ o $j\ge 0$. Los llamaremos deque izquierdo y derecho, respectivamente.

• Las primeras dos operaciones corresponden a extraer repetidamente el último elemento del deque izquierdo y agregarlo al frente del deque derecho (o viceversa, según la dirección del desplazamiento).
• La tercera operación corresponde a restar $Z$ a todos los elementos del deque izquierdo y sumar $Z$ a todos los elementos del deque derecho.
• La última operación corresponde a fijar $dif[j]=\max(dif[j],-Y)$ para todo $j < 0$ y $dif[j] = \min(dif[j],X)$ para todo $j\ge 0$.

Podemos implementar la última operación actualizando todas las diferencias en los deques de forma “perezosa”. Esta solución corre en $\mathcal{O}(\sum A_i+\sum B_i)$.

#include <bits/stdc++.h>
 
using namespace std;
 
int N, X, Y, Z;
int difl, difr;  // "lazy" update
deque<int> L, R;
long long ans;
 
void rig() {  // shift right A, so origin moves left
	if (L.size() == 0) L.push_back(-Y - difl);
	int t = L.back() + difl;
	L.pop_back();
	t = max(t, -Y);
	ans -= t;
	R.push_front(t - difr);
}
 
void lef() {  // shift left B, so origin moves right
	if (R.size() == 0) R.push_front(X - difr);
	int t = R.front() + difr;
	R.pop_front();
	t = min(t, X);
	ans += t;
	L.push_back(t - difl);
}
 
int main() {
	freopen("landscape.in", "r", stdin);
	freopen("landscape.out", "w", stdout);
	cin >> N >> X >> Y >> Z;
	for (int i = 0; i < N; ++i) {
		int A, B;
		cin >> A >> B;
		for (int j = 0; j < A; ++j)
			rig();  // or we can just do |A-B| shifts in one direction
		for (int j = 0; j < B; ++j) lef();
		difl -= Z,
		    difr += Z;  // adjust slopes differently for left and right of j=0
	}
	cout << ans << "\n";
}

Extensión

Podemos resolver este problema cuando $\sum A_i+\sum B_i$ no es tan chico manteniendo un mapa de $j$ a $dif[j+1]-dif[j]$ para todo $j$ tal que esta última cantidad es distinta de cero. Entonces la operación “sumar $Z\cdot |j|$ a $DP[j]$ para todo $j$” corresponde a una actualización puntual en el mapa (advance() en el código de abajo).

Código de Alex Wei.

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const ll INF = 1LL << 60;
 
ifstream fin("landscape.in");
ofstream fout("landscape.out");
 
const int MAXN = 100005;
ll N, X, Y, Z, A, B;
ll ls, rs, lv, zp;
map<ll, ll> M;
 
void fix_left(ll s) {
	if (ls >= s) return;
	auto it = M.begin();
	while (ls + it->second <= s) {
		ls += it->second;
		lv += ls * (next(it)->first - it->first);
		M.erase(it++);
	}
	it->second -= s - ls;
	ls = s;
}
 
void fix_right(ll s) {
	if (rs <= s) return;
	auto it = --M.end();
	while (rs - it->second >= s) {
		rs -= it->second;
		M.erase(it--);
	}
	it->second += s - rs;
	rs = s;
}
 
void advance() {
	ll lo = M.begin()->first;
	if (zp < lo) lv += ls * (zp - lo);
	else lv += Z * (zp - lo);
	ls -= Z, rs += Z;
	M[zp] += 2 * Z;
}
 
int main() {
	fin >> N >> X >> Y >> Z;
	ls = -INF, rs = INF;
	M[0] = 2 * INF;
	for (int i = 0; i < N; i++) {
		fin >> A >> B;
		zp += B - A;
		fix_left(-Y);
		fix_right(X);
		advance();
	}
	ll res = lv, s = ls;
	for (auto it = M.begin(); it->first < zp; it++) {
		s += it->second;
		res += s * (next(it)->first - it->first);
	}
	fout << res << '\n';
}

Problemas

Aunque no hemos dado ningún ejemplo de esto, algunos de los problemas de abajo requerirán fusionar dos contenedores de pendientes (usualmente colas de prioridad).