Editorial for Eren en Marley

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: aniervs

Solución:

Digamos que una ruta desde el nodo $1$ ~1~ al nodo $n$ ~n~ consiste de $k$ ~k~ aristas, y tiene longitud $S$ ~S~. Su costo es exactamente $\dfrac{S}{v} + k\cdot c$ ~\dfrac{S}{v} + k\cdot c~

Consideremos dos rutas diferentes, de $k$ ~k~ aristas, con longitudes $S$ ~S~ y $S'$ ~S'~ respectivamente. Como $v > 0$ ~v > 0~, tenemos:

$\displaystyle k \cdot c + \frac{S}{v} \le k \cdot c + \frac{S'}{v} \iff S \le S'$

Esto quiere decir, que para un $k$ ~k~ fijo, basta con minimizar la longitud de la ruta de longitud $k$ ~k~ desde 1 hasta $n$ ~n~. Llamemos $S_k$ ~S_k~ a la menor longitud de una ruta de $k$ ~k~ aristas.

¿Cómo computar $S_k$ ~S_k~? Podemos usar programación dinámica.

$dp(k, u)$ ~dp(k, u)~: menor distancia desde $1$ ~1~ hasta $u$ ~u~ usando exactamente $k$ ~k~ aristas.

$\displaystyle \begin{cases} dp(0, 1) = 0\\ dp(k, u) = \min\{dp(k-1, v) + length(v, u)\}\text{ para todos los } v \text{ conectados a } u \end{cases}$

Luego $S_k = dp(k, n)$ ~S_k = dp(k, n)~.

Ahora, consideremos dos $k_1, k_2$ ~k_1, k_2~, con $k_1 \ne k_2$ ~k_1 \ne k_2~.

$\displaystyle \dfrac{S_{k_1}}{v} + k_1\cdot c \le \dfrac{S_{k_2}}{v} + k_2\cdot c \iff S_{k_1} + k_1 \cdot (cv) \le S_{k_2}+k_2\cdot(cv)$

Entonces podemos considerar para $k$ ~k~ fijo, el costo de la ruta óptima de $k$ ~k~ aristas como una función lineal $f_k(x) = k\cdot x + S_k$ ~f_k(x) = k\cdot x + S_k~.

De estas líneas $f_1, f_2, \dots, f_n$ ~f_1, f_2, \dots, f_n~, solo queremos las que podrían ser óptimas para algún $x \ge 0$ ~x \ge 0~; es decir los valores de $k$ ~k~, tal que existe algún $x\ge 0$ ~x\ge 0~, para el cual se cumple que $f_k(x) \le f_{k'}(x)$ ~f_k(x) \le f_{k'}(x)~ para todo $k' \ne k$ ~k' \ne k~.

Estas son las líneas pertenecientes al Lower Hull (parte inferior del Convex Hull) del conjunto de líneas. Bueno, debemos quitar de este Hull, las líneas que solo son óptimas para $x < 0$ ~x < 0~; pero esto es un pequeño detalle que puede ser manejado luego de computar el Lower Hull; mientras las dos líneas más a la izquierda en el Lower Hull se corten en un punto con $x < 0$ ~x < 0~, borramos la línea más a la izquierda.

Una vez que tenemos las líneas óptimas, lo que en realidad tenemos son los $k, S_k$ ~k, S_k~ que son óptimos para algún par $c, v$ ~c, v~. Solo tenemos que reportar los nodos que son parte de alguna ruta de $k$ ~k~ aristas, con longitud $S_k$ ~S_k~. Para hacer eso, haremos un DFS desde $n$ ~n~ hasta llegar a $1$ ~1~, y llevaremos también $k$ ~k~. Es decir, llevaremos en el DFS el nodo en el que estamos y la cantidad de aristas (y queremos visitar los nodos que pertenecen a alguna ruta óptima con dicha cantidad de aristas desde $1$ ~1~ hasta el nodo actual). Durante el DFS, si el estado actual es $(u, k)$ ~(u, k)~, entonces consideramos los vecinos $v_i$ ~v_i~ de $u$ ~u~, y si $dp(v_i, k-1) + length(v_i, u)$ ~dp(v_i, k-1) + length(v_i, u)~, nos movemos al estado $(v_i, k-1)$ ~(v_i, k-1)~. Los nodos visitados durane el DFS son la solución.

Complejidad: Si $n$ ~n~ es la cantidad de nodos del grafo, y $m$ ~m~ es la cantidad de aristas, entonces una ruta consiste de a lo más $n-1$ ~n-1~ aristas. La Dp entonces toma tiempo $\mathcal{O(n\cdot (n + m))}$ ~\mathcal{O(n\cdot (n + m))}~. El Convex Hull se puede hacer en tiempo $\mathcal{O(n)}$ ~\mathcal{O(n)}~ ya que las líneas $k \cdot x + S_k$ ~k \cdot x + S_k~ ya están ordenadas por pendientes. El DFS toma el mismo tiempo que la DP. La complejidad temporal final sería $\mathcal{O(n^2 + m)}$ ~\mathcal{O(n^2 + m)}~. La complejidad en memoria sería $\mathcal{O(n^2 + m)}$ ~\mathcal{O(n^2 + m)}~.

Tags:

Grafos
Programación Dinámica
Convex Hull

Comments

There are no comments at the moment.