Truco de la envolvente convexa

Queremos resolver problemas de la siguiente forma:

Considerar un conjunto de funciones $\{f_i(x)\}$ sobre algún rango $[l,r]$ tal que para cualesquiera dos funciones $f_i$ y $f_j$ existe algún $m$ tal que

• Para todo $x \in [l,m]$, $f_i(x)\le f_j(x)$
• Para todo $x \in [m,r]$, $f_i(x)\ge f_j(x)$

Responder consultas de la forma “cuál es el máximo/mínimo $f_i(x)$ para algún $x\in [l,r]$ dado”, suponiendo que tenemos una forma de hallar $m$ de manera eficiente.

Un conjunto de condiciones suficiente (pero no necesario):

• Todas las funciones son continuas a lo largo del rango $[l,r]$.
• Ningún par de funciones se intersecta en más de un punto.

El caso más común es cuando cada $f_i(x)$ es de la forma $a_ix+b_i$. Dadas dos rectas $f_i(x)=a_ix+b_i$ y $f_j(x)=a_jx+b_j$ tales que $a_i<a_j$, su punto de intersección $m=\frac{b_i-b_j}{a_j-a_i}$ se puede hallar en tiempo $\mathcal{O}(1)$. Entonces es claro que

• Para todo $x\le m$, $f_i(x)\ge f_j(x)$.
• Para todo $x\ge m$, $f_i(x)\le f_j(x)$.

El caso lineal se conoce como el truco de la envolvente convexa (convex hull trick, CHT) porque $\max_i(f_i(x))$ como función de $x$ es cóncava hacia arriba (de forma análoga, $\min_i(f_i(x))$ como función de $x$ es cóncava hacia abajo). Ver las imágenes del tutorial de CF de abajo si esto no queda claro.

Algunas formas no lineales posibles de $f_i(x)$:

• $f_i(x)=x^2+a_ix+b_i$
  • Se reduce al caso lineal, ya que podemos ignorar el término $x^2$ al comparar dos funciones.
• $f_i(x) = \sqrt{x - a_i} + b_i$
  • Si esta función está definida para todo $x\in [l,r]$.
  • Observar que cuando $a_i<a_j$, $\sqrt{x-a_i}-\sqrt{x-a_j}$ es estrictamente decreciente sobre el rango $x\in [a_j,\infty)$.

En este módulo nos concentramos en el caso especial de CHT en el que las “pendientes” de las funciones son monótonas. Este caso específico se puede resolver en $\mathcal{O}(N)$ usando un std::deque en C++. Para el CHT más general en $\mathcal{O}(N \log N)$ (que involucra un std::multiset), ver el módulo LineContainer.

Tutorial

Solución - The Fair Nut and Rectangles

No voy a analizar este problema en gran detalle porque el blog de Codeforces de los recursos ya lo hace, pero esencialmente ordenamos los rectángulos por coordenada $x$ y obtenemos la siguiente recurrencia de DP:

Observar cómo la parte $-p_j \cdot q_i + dp[j]$ de la recurrencia describe una recta $y = mx + c$.

Como ordenamos los rectángulos y ningún par de rectángulos está anidado, las pendientes de las rectas que insertamos son estrictamente crecientes. Las posiciones de consulta también son estrictamente crecientes.

Esto significa que podemos resolver este problema usando CHT en tiempo $\mathcal{O}(N)$. Acá está mi implementación:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
 
struct Rect {
	ll x, y, a;
	bool operator<(Rect B) { return x < B.x; }
};
 
Rect a[1000001];
ll dp[1000001];
 
double slope(int i, int j) { return (double)(dp[i] - dp[j]) / (a[i].x - a[j].x); }
 
int main() {
	iostream::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].y >> a[i].a; }
	sort(a + 1, a + n + 1);
 
	deque<ll> q;
	q.push_back(0);
	for (int i = 1; i <= n; i++) {
		while (q.size() > 1 && slope(q[0], q[1]) >= a[i].y) q.pop_front();
 
		ll j = q.front();
		dp[i] = max(dp[i - 1], a[i].x * a[i].y - a[i].a + dp[j] - a[j].x * a[i].y);
 
		while (q.size() > 1 && slope(q[q.size() - 2], q.back()) <= slope(q.back(), i))
			q.pop_back();
		q.push_back(i);
	}
 
	cout << dp[n];
	return 0;
}

Problemas