Editorial for El Escape Vacuno

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

Si la permutación escogida es $x_1, x_2, x_3, \dots, x_n$ ~x_1, x_2, x_3, \dots, x_n~ (digamos que $x_0 = 0$ ~x_0 = 0~), entonces el costo es $\displaystyle \sum_{i = 0}^{n-1} |x_i-x_{i+1}|\cdot(n - i)$

Se puede observar que es óptimo visitar los positivos en orden creciente, y los negativos en orden decreciente. Es decir, la permutación óptima contiene como subsecuencia a los positivos en orden creciente y también contiene como subsecuencia a los negativos en orden decreciente.

Entonces, tengamos dos arreglos $A$ ~A~ y $B$ ~B~, que contengan a los positivos en orden creciente y a los negativos en orden decreciente, respectivamente; y por una cuestión de simplicidad, agreguemos el $0$ ~0~ al inicio de ambos. En el ejemplo serían $A = \{0, 3, 7\}$ ~A = \{0, 3, 7\}~ y $B = \{0, -2, -12\}$ ~B = \{0, -2, -12\}~.

Ahora podemos usar programación dinámica para construir la permutación óptima. Necesitamos saber cuál es el último elemento de $A$ ~A~ escogido, y el último elemento de $B$ ~B~ escogido; además necesitamos saber en qué posición terminamos. Por tanto, podemos usar la siguiente DP.

$dp(i, j, 0)$ ~dp(i, j, 0)~: costo mínimo de visitar los primeros $i$ ~i~ elementos de $A$ ~A~, los primeros $j$ ~j~ elementos de $B$ ~B~, y en el viaje terminamos en la posición $A_i$ ~A_i~

$dp(i, j, 1)$ ~dp(i, j, 1)~: costo mínimo de visitar los primeros $i$ ~i~ elementos de $A$ ~A~, los primeros $j$ ~j~ elementos de $B$ ~B~, y en el viaje terminamos en la posición $B_j$ ~B_j~

Las transiciones son bastante sencillas:

Del estado $(i, j, 0)$ ~(i, j, 0)~ podemos movernos al estado $(i + 1, j, 0)$ ~(i + 1, j, 0)~ con costo adicional $|A_{i+1}-A_i|\cdot (n - i - j)$ ~|A_{i+1}-A_i|\cdot (n - i - j)~, y al estado $(i, j + 1, 1)$ ~(i, j + 1, 1)~ con costo adicional $|B_{j+1}-A_i|\cdot (n - i - j)$ ~|B_{j+1}-A_i|\cdot (n - i - j)~. Del estado $(i, j, 1)$ ~(i, j, 1)~ podemos movernos al estado $(i + 1, j, 0)$ ~(i + 1, j, 0)~ con costo adicional $|A_{i+1}-B_j|\cdot (n - i - j)$ ~|A_{i+1}-B_j|\cdot (n - i - j)~, y al estado $(i, j+ 1, 1)$ ~(i, j+ 1, 1)~ con costo adicional $|B_{j + 1}-B_j|\cdot(n-i-j)$ ~|B_{j + 1}-B_j|\cdot(n-i-j)~.

Como casos base podemos poner $dp(0, 0, 0) = 0$ ~dp(0, 0, 0) = 0~.

La respuesta sería $\min(dp(|A|, |B|, 0),\ dp(|A|, |B|, 1))$ .

Complejidad: Son $|A|\cdot|B|\cdot 2$ ~|A|\cdot|B|\cdot 2~ estados, y dos posibles transiciones desde cada estado; además $|A|,|B|\le n$ ~|A|,|B|\le n~; por tanto, la complejidad temporal es $\mathcal{O}(n^2)$ ~\mathcal{O}(n^2)~, y en memoria es $\mathcal{O}(n^2)$ ~\mathcal{O}(n^2)~.

Nota: Se puede obtener memoria lineal, pero no es necesario en este problema.

Comments

There are no comments at the moment.