Truco de la envolvente convexa (CHT) y Árbol de Li Chao

Considérese el siguiente problema. Hay $n$ ciudades. Se quiere viajar en auto de la ciudad $1$ a la ciudad $n$ . Para ello hay que comprar algo de gasolina. Se sabe que un litro de gasolina cuesta $cost_k$ en la $k$ -ésima ciudad. Inicialmente el tanque está vacío y se gasta un litro de gasolina por kilómetro. Las ciudades están ubicadas sobre la misma recta en orden creciente, y la $k$ -ésima ciudad tiene coordenada $x_k$ . Además hay que pagar $toll_k$ para entrar a la $k$ -ésima ciudad. La tarea es hacer el viaje con el menor costo posible. Es evidente que la solución se puede calcular mediante programación dinámica:

$dp_i = toll_i+\min\limits_{j<i}(cost_j \cdot (x_i - x_j)+dp_j)$

El enfoque ingenuo da complejidad $O(n^2)$ , que se puede mejorar a $O(n \log n)$ o $O(n \log [C \varepsilon^{-1}])$ , donde $C$ es el mayor $|x_i|$ posible y $\varepsilon$ es la precisión con la que se considera $x_i$ ( $\varepsilon = 1$ para enteros, que suele ser el caso). Para ello hay que observar que el problema se reduce a añadir funciones lineales $k \cdot x + b$ al conjunto y encontrar el valor mínimo de las funciones en algún punto particular $x$ . Hay dos enfoques principales que se pueden usar aquí.

Truco de la envolvente convexa

La idea de este enfoque es mantener una envolvente convexa inferior de funciones lineales. En realidad resulta un poco más cómodo considerarlas no como funciones lineales, sino como puntos $(k;b)$ en el plano, de modo que habrá que encontrar el punto que tiene el menor producto punto con un punto dado $(x;1)$ ; es decir, para ese punto $kx+b$ se minimiza, que es lo mismo que el problema inicial. Tal mínimo estará necesariamente sobre la envolvente convexa inferior de estos puntos, como se ve abajo:

Hay que mantener los puntos de la envolvente convexa y los vectores normales de las aristas de la envolvente. Cuando se tiene una consulta $(x;1)$ hay que encontrar el vector normal más cercano a ella en términos de los ángulos entre ellos; entonces la función lineal óptima corresponderá a uno de sus extremos. Para verlo, obsérvese que los puntos que tienen un producto punto constante con $(x;1)$ yacen sobre una recta ortogonal a $(x;1)$ , de modo que la función lineal óptima será aquella en la que la tangente a la envolvente convexa colineal con la normal a $(x;1)$ toca la envolvente. Ese punto es aquel tal que las normales de las aristas que quedan a su izquierda y a su derecha apuntan hacia lados distintos de $(x;1)$ .

Este enfoque es útil cuando las consultas de añadir funciones lineales son monótonas en términos de $k$ , o si trabajamos offline, es decir, podemos primero añadir todas las funciones lineales y responder las consultas después. Así que no podemos resolver los problemas de ciudades/gasolina de esta manera. Eso exigiría manejar consultas online. Sin embargo, cuando hay que tratar con consultas online, las cosas se ponen difíciles y hay que usar algún tipo de estructura de datos de conjunto para implementar una envolvente convexa adecuada. El enfoque online, no obstante, no se considerará en este artículo por su dificultad y porque el segundo enfoque (que es el Árbol de Li Chao) permite resolver el problema de forma mucho más simple. Vale la pena mencionar que aún se puede usar este enfoque online sin complicaciones mediante descomposición por raíz cuadrada. Es decir, reconstruir la envolvente convexa desde cero cada $\sqrt n$ rectas nuevas.

Para implementar este enfoque hay que empezar con algunas funciones geométricas de utilidad; aquí sugerimos usar el tipo de números complejos de C++.


typedef int ftype;
typedef complex<ftype> point;
#define x real
#define y imag
 
ftype dot(point a, point b) {
	return (conj(a) * b).x();
}
 
ftype cross(point a, point b) {
	return (conj(a) * b).y();
}

Aquí asumiremos que cuando se añaden funciones lineales, su $k$ solo crece y queremos encontrar valores mínimos. Mantendremos los puntos en el vector $hull$ y los vectores normales en el vector $vecs$ . Cuando añadimos un punto nuevo, hay que mirar el ángulo formado entre la última arista de la envolvente convexa y el vector desde el último punto de la envolvente convexa hasta el punto nuevo. Este ángulo tiene que estar dirigido en sentido antihorario, es decir, el producto punto del último vector normal de la envolvente (dirigido hacia el interior de la envolvente) y el vector desde el último punto hasta el nuevo tiene que ser no negativo. Mientras esto no se cumpla, debemos borrar el último punto de la envolvente convexa junto con la arista correspondiente.


vector<point> hull, vecs;
 
void add_line(ftype k, ftype b) {
    point nw = {k, b};
    while(!vecs.empty() && dot(vecs.back(), nw - hull.back()) < 0) {
        hull.pop_back();
        vecs.pop_back();
    }
    if(!hull.empty()) {
        vecs.push_back(1i * (nw - hull.back()));
    }
    hull.push_back(nw);
}

Ahora, para obtener el valor mínimo en algún punto, encontraremos el primer vector normal de la envolvente convexa que está dirigido en sentido antihorario desde $(x;1)$ . El extremo izquierdo de esa arista será la respuesta. Para comprobar si el vector $a$ no está dirigido en sentido antihorario respecto del vector $b$ , debemos comprobar si su producto cruz $[a,b]$ es positivo.


int get(ftype x) {
    point query = {x, 1};
    auto it = lower_bound(vecs.begin(), vecs.end(), query, [](point a, point b) {
        return cross(a, b) > 0;
    });
    return dot(query, hull[it - vecs.begin()]);
}

Árbol de Li Chao

Supongamos que se da un conjunto de funciones tales que cada par se intersecta a lo sumo una vez. Mantendremos en cada vértice de un Árbol de Segmentos alguna función de modo que, si vamos de la raíz a la hoja, esté garantizado que una de las funciones que encontramos en el camino será la que da el valor mínimo en esa hoja. Veamos cómo construirlo.

Supongamos que estamos en algún vértice correspondiente al semisegmento $[l,r)$ y que allí se guarda la función $f_{old}$ y añadimos la función $f_{new}$ . Entonces el punto de intersección estará o bien en $[l;m)$ o bien en $[m;r)$ , donde $m=\left\lfloor\tfrac{l+r}{2}\right\rfloor$ . Podemos determinar eso de forma eficiente comparando los valores de las funciones en los puntos $l$ y $m$ . Si la función dominante cambia, entonces está en $[l;m)$ ; en caso contrario está en $[m;r)$ . Ahora, para la mitad del segmento sin intersección tomaremos la función inferior y la escribiremos en el vértice actual. Se puede ver que siempre será la que es inferior en el punto $m$ . Después vamos recursivamente a la otra mitad del segmento con la función que era la superior. Como se ve, esto mantendrá la corrección en la primera mitad del segmento y en la otra la corrección se mantendrá durante la llamada recursiva. Así podemos añadir funciones y consultar el valor mínimo en el punto en $O(\log [C\varepsilon^{-1}])$ .

Aquí está la ilustración de lo que ocurre en el vértice cuando añadimos una función nueva:

Pasemos ahora a la implementación. Una vez más usaremos números complejos para guardar las funciones lineales.


typedef long long ftype;
typedef complex<ftype> point;
#define x real
#define y imag
 
ftype dot(point a, point b) {
    return (conj(a) * b).x();
}
 
ftype f(point a,  ftype x) {
    return dot(a, {x, 1});
}

Guardaremos las funciones en el arreglo $line$ y usaremos indexación binaria del Árbol de Segmentos. Si se quiere usar sobre números grandes o dobles, hay que usar un Árbol de Segmentos dinámico. El Árbol de Segmentos debe inicializarse con valores por defecto, p. ej. con rectas $0x + \infty$ .


const int maxn = 2e5;
 
point line[4 * maxn];
 
void add_line(point nw, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    bool lef = f(nw, l) < f(line[v], l);
    bool mid = f(nw, m) < f(line[v], m);
    if(mid) {
        swap(line[v], nw);
    }
    if(r - l == 1) {
        return;
    } else if(lef != mid) {
        add_line(nw, 2 * v, l, m);
    } else {
        add_line(nw, 2 * v + 1, m, r);
    }
}

Ahora, para obtener el mínimo en algún punto $x$ simplemente elegimos el valor mínimo a lo largo del camino hasta el punto.


ftype get(int x, int v = 1, int l = 0, int r = maxn) {
    int m = (l + r) / 2;
    if(r - l == 1) {
        return f(line[v], x);
    } else if(x < m) {
        return min(f(line[v], x), get(x, 2 * v, l, m));
    } else {
        return min(f(line[v], x), get(x, 2 * v + 1, m, r));
    }
}

Problemas

Codebreaker - TROUBLES (aplicación simple del truco de la envolvente convexa después de un par de observaciones)
CS Academy - Squared Ends
Codeforces - Escape Through Leaf
CodeChef - Polynomials
Codeforces - Kalila and Dimna in the Logging Industry
Codeforces - Product Sum
Codeforces - Bear and Bowling 4
APIO 2010 - Commando