Entrenamiento 2018: Tanda 4

¡Cuarta tanda temática!

1 me gusta

Si hacen Indiana, están invitados a contar su solución en Desafío Ryckeboer #4 :wink:

Si hacen ambulancia, están invitados a contar su solución en Desafío Ryckeboer #6 :wink:

Si bien si mandan el código solo está todo bien, aprovecho para aclarar que escribir las ideas detalladamente y explicarlas a otra persona es un ejercicio muy enriquecedor (de hecho, es una forma conocida de debuguear), y es parte de la idea de los Desafíos que se proponen (obviamente, la otra parte es pensar problemas copados).

Maxinum

Vengo a poner una forma posible de resolver “maxinum” con Programación Dinámica.

Muchas veces es más fácil pensar un problema en términos de subproblemas con la misma estructura, pero de menor tamaño. Una bastante común es imaginarse que uno tiene una función que resuelve el problema para los primeros i elementos.

f(i) = \text{''La solución al problema mirando solo los primeros } i \text{ elementos''}

Volviendo ahora sí al problema de Maxinum, supongamos que tenemos dicha f, o sea una función que dado i nos devuelve un par:

f(i) = (\text{MáximaSumaProductos}_i,\text{SumaNoUtilizados}_i)

Que nos devuelve la máxima suma de productos que uno puede generar con los primeros i elementos (y la suma de los no utilizados).

Entonces para calcular f(i) uno puede hacerlo recursivamente según qué decisión se tomen con los últimos elementos y “patear el resto de la solución a la función recursiva”:

Caso 1 : No se utiliza el i-ésimo en ningún producto

\begin{matrix} \underset{f(i-1)}{\underbrace{a_1 \dots a_{i-1}}} & | & \color{red}{a_i} \\ \end{matrix}

Caso 2 : Se utiliza al i-ésimo y no se utiliza al (i-1)-ésimo

\begin{matrix} \underset{f(i-3)}{\underbrace{a_1 \dots a_{i-3}}} & | & \color{lime}{a_{i-2}} & \color{red}{a_{i-1}} & \color{lime}{a_i} \\ \end{matrix}

Caso 3 : Se utiliza al i-ésimo y también se utiliza al (i-1)-ésimo

\begin{matrix} \underset{f(i-4)}{\underbrace{a_1 \dots a_{i-4}}} & | & \color{green}{a_{i-3}} & \color{lime}{a_{i-2}} & \color{green}{a_{i-1}} & \color{lime}{a_i} \\ \end{matrix}

Bueno, y para cada i uno quiere el mejor de estos 3 casos.

Dejo acá mi implementación de esta idea. Hay un detalle en el código que es que agrego muchos ceros al principio para que sirvan de caso base en la recursión.

Código
#include <bits/stdc++.h>

using namespace std;

#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(int)(s);i<(int)(n); i++)

int main()
{
	ifstream input ("maxinum.in");
	ofstream output ("maxinum.out");
	int n;
	while (input >> n)
	{
		vector<int> a (n+10,0);
		forn(i,n)
			input >> a[i+10];
			
		vector<pair<int,int> > maxinum (n+10,{0,0}); //  lo mejor con el prefijo de i : (producto,sumaNoUtilizados) (relleno con ceros al principio)
		forsn(i,8,n+10)
			maxinum[i] = max(make_pair(maxinum[i-1].first,  maxinum[i-1].second + a[i]), // Caso 1
				     max(make_pair(maxinum[i-3].first + a[i]*a[i-2], maxinum[i-3].second + a[i-1]), // Caso 2
					 make_pair(maxinum[i-4].first + a[i]*a[i-2] + a[i-1]*a[i-3], maxinum[i-4].second))); // Caso 3
							 
		output << maxinum[n+9].first << "\n" << maxinum[n+9].second << "\n";
				
	}
	return 0;
}

Encontrando Mutaciones (ADN)

Este problema creo que se lo puede considerar “clásico”, o al menos está MUY relacionado con el problema de Edit Distance (que es la distancia entre strings que define el enunciado, por si se quiere googlear al respecto).

Como muchas otras veces donde usamos programación dinámica, la idea es resolver el problema, suponiendo que sabemos resolver pedacitos más pequeños. En este caso, vamos a pensar el problema suponiendo que ya lo sabemos resolver para los prefijos de cada palabra (les voy a llamar s a la primera y t a la segunda).

Es decir, vamos a plantear:

\texttt{f}({\color{cyan}{i}},{\color{magenta}{j}}) = \texttt{distancia entre } \overset{\text{prefijo}}{\overbrace{ {\color{cyan}{\texttt{s}\texttt{[0..i)}}} } } \texttt{ y } \overset{\text{prefijo}}{\overbrace{ {\color{magenta}{\texttt{t}\texttt{[0..j)}}} } }
\begin{matrix} s_1& s_2 & \dots & s_{i-1} & | & {\color{cyan}{s_i} } & | & s_{i+1} & \dots & s_N \end{matrix}
\begin{matrix} t_1 & t_2 & \dots & t_{j-1} & | & {\color{magenta}{t_j} } & | & t_{j+1} & \dots & t_M \end{matrix}

Esta \texttt{f} depende solo de los estados:

  • (i-1,j) (borrar el s[i])
  • (i,j-1) (agregar t[j] después de s[i])
  • (i-1,j-1) (reemplazar s[i] por t[j])

Con esta idea, creo que debería estar más claro cómo obtener una solución que corra en \mathcal{O}(NM) (N y M como en el enunciado).


Vamos a diferenciar el tiempo de corrida del espacio usado en memoria. El enfoque usual usa \mathcal{O}(NM) de tiempo y también \mathcal{O}(NM) de memoria (porque se guarda toda la tabla)

¿Cómo podemos mejorar el \mathcal{O}(NM) en memoria? (el de tiempo no todavía)

La gracia es que si vamos llenando en orden los j, para llenar (1,j) solo necesitamos estados de la pinta (0,j) o (1,j) con j anteriores. Para llenar el (2,j) solo necesitamos los (1,j) o (2,j) con los j anteriores. Entonces si vamos llenando en orden creciente en i, para resolver todos los nodos de la pinta (i,j) solo nos hace falta la “capa” anterior (la capa de todos los (i-1,j) ).

En la “tabla” esto nos dice que al llenar la fila i, solo nos hace falta conocer los valores de la fila i-1 y la fila i que vamos llenando.

Entonces si en lugar de guardarnos tooooda la tabla, solo nos guardamos las últimas dos filas que vamos procesando, nos podemos ahorrar memoria (y usar solo \mathcal{O}(N) u \mathcal{O}(M) memoria)


¿Cómo podemos usar el K en todo esto para bajar el tiempo?¿Hace falta mirar toda la tabla?

Para pensar en términos de la tabla probablemente es más fácil mirar las transiciones al revés (me resulta más natural bajar hacia la derecha que subir a la izquierda). Los movimientos posibles son 3:

(i,j)) \rightarrow \{\overset{\text{diagonal } \searrow}{\overbrace{(i+1,j+1)}},\underset{\text{bajar } \downarrow}{\underbrace{(i+1,j)}},\underset{{\normalsize\text{derecha }} \rightarrow }{\underbrace{(i,j+1)}} \}

O sea, si estamos en la fila i y la columna j podemos movernos en esas 3 direcciones. Pero en las de bajar y moverse a la derecha, pagamos costo 1 siempre (en diagonal depende de si coinciden las letras o no). Por lo tanto en las soluciones que nos interesan, jamás se realizan más de K de estos movimientos (notar que el K es chiquito).

Entonces alcanza con ver qué pasa en los lugares que podemos alcanzar. Por ejemplo, esto sería con K = 1, con K más grandes la banda que hay que mirar se agranda:

BandaBlanco

De esta forma, solo visitamos \mathcal{O}(KN) estados.