Memoización

A rato de no escribir en el PuroAC hoy explicaré una técnica muy usada en programación, pero sobre todo en la programación competitiva. A raíz de que recientemente me ha sido útil y con el fin de compartir los conocimientos (además de que en mi otro blog donde lo explicaba murió el post).

La memoización (Memoization en inglés) o memorización se diferencia de 'memorización' puesto que el término ya era usado en matemáticas, es una técnica que ayuda a la aceleración de cómputo en una función recursiva en el momento en que se tarde bastante y se hagan las mismas llamadas a la función que ya fueron hechas anteriormente. 

¿Ejemplo?

Todos conocemos la función de Fibonacci... ¿no?
Sino, la explico rápido. La función de Fibonacci empieza con los casos triviales o base

$Fibo(0) = 1$ y $Fibo(1) = 1$

y de ahí se deriva la serie siendo $Fibo(2) = Fibo(1) + Fibo(0)$

o sea que nuestra función de Fibonacci esta dada por

$Fibo(n) = Fibo(n-1) + Fibo(n-2)$ siendo $n>=2$

Veamos el árbol que se forma para su cálculo...

En el caso de implementar esta función de manera recursiva, otro ejemplo para la llamada de la función podría ser con $n = 5$
Cuando se llega en el árbol a los casos base (señalados en la imagen) evidentemente las llamadas a la función se detienen. Pero también podemos notar que existen varios casos en donde se llama recursivamente a números que ya fueron calculados, por ejemplo el 3.
Entonces para subsecuentes llamadas la cantidad de operaciones a calcular se volverían exponenciales y la complejidad aproximada sería $O(2^n)$ lo cuál para un $n = 40$ ya es mucho que calcular.


La optimización.

Por fortuna nos podemos ayudar de la memoización para mejorar el rendimiento de nuestra función.
Básicamente la idea es tener un arreglo del tamaño de la $n$ que queramos calcular y llenarlo de valores "bandera" (por ejemplo $-1$) y mientras se van calculando todas las $Fibo(n)$ en cada una de las llamadas recursivas esos valores obtenidos meterlos en el arreglo correspondiente a la $n$ actual.

Aquí el código de la  función en Python sin optimización:
def fiboLento(n):
 if n == 0 or n==1:
  return 1
 return fiboLento(n-1) + fiboLento(n-2)

Así pues con la optimización:
memo = [-1 for i in xrange(100000)]

def fibo(n):
 if n == 0 or n==1:
  return 1
 if memo[n]!= -1:
  return memo[n]
 memo[n] = fibo(n-1) + fibo(n-2)
 return memo[n]
Justamente en esta línea de código es donde preguntamos si el valor de Fibonacci para nuestra actual n ya fue calculado.
   
if memo[n]!= -1:
 return memo[n]
¿Cómo lo sabemos? Pues fácil sí nuestro arreglo en la posición $n$ ya no tiene $-1$ como valor es que ya fue calculado antes es ahí donde solo debemos devolver el valor para esa $n$ y así no rehaga el cálculo para todos sus hijos en caso de que los tenga.

Conclusión.


Sí, generalmente memoizar es tan fácil como solo ir coleccionando los cálculos que hagamos y preguntar si se tiene hasta ese momento (en el estado actual de la llamada recursiva) calculado el valor si sí, no se calcula y se devuelve el valor, pero hay que tener cuidado de que nuestro árbol se pueda podar y asegurarnos que las ramas que vayamos a podar sí se calculen en algún otro punto del árbol. 

Ahora el árbol nos quedaría más o menos así, ya que todas las llamadas a las n que ya fueron calculadas solo devuelve su mismo valor, lo cual reduce la complejidad aproximadamente a $O(n)$. Considerablemente se ha reducido la complejidad del cálculo.
Si bien pudimos hacer un ciclo for para calcular Fibonacci de n, use está función porque es fácil de entender y fácil para ejemplificar el uso de la Memoización pero existe una cantidad muy vasta de problemas donde podemos aplicarla.

Si tienes dudas puedes escribirme a @ferprogramming en twitter. Saludos.

Chef and Rainbow Array - 2 (RAINBOWB - CodeChef)

Link al problema: RAINBOWB

Dificultad: Medio

Problema: Dado un número $N$, $1 ≤ N ≤ 10^6$, encontrar todas las maneras posibles de formar un “arreglo arcoiris” de tamaño $N$. Un arrelgo arcoíris contiene todos los números del 1 al 7 ordenados de manera ascendente hasta la mitad del arreglo, mientras que para la otra mitad contiene los la misma cantidad pero ordenados de manera descendente. Este es un ejemplo de un arreglo de ese tipo con $N = 15$: $\{1,\ 2,\ 3,\ 4,\ 5,\ 6,\ 7,\ 7,\ 7,\ 6,\ 5,\ 4,\ 3,\ 2,\ 1\}$.

Solución: (Existe solución en $O(1)$ para este problema, sin embargo aquí se expone una solución empleando la programación dinámica)

Primero que nada debemos identificar que podemos trabajar con una sola mitad del arreglo, puesto que la otra es igual. Después debemos identificar que para cada $N$ que nos den existen $R$ números extras (repetidos) que podemos colocar, (en el ejemplo presentado más arriba $R=2$ por eso hay dos $7$ más). Podemos obtener $R/2$ de la siguente manera: aumentando $N$ en uno, dividiéndolo entre dos y a eso restarle $7$, que es la cantidad de elementos distintos en un arreglo arcoíris.

La función de programación dinámica dependerá de dos parámetros, $r$ la cantidad de números repetidos que podemos poner todavía y $n$, el número que estamos poniendo en nuestro arreglo arcoíris.

Sabemos que $1≤n≤7$ , por tanto si en algún momento toma un valor distinto, hemos puesto $7$ números distintos en el arreglo, debemos entonces revisar $r$, si $r=0$ hemos usado todos nuestros números extras y por tanto esa es una manera de formar un arreglo, por el contrario si $r≠0$ llegamos a la mitad de nuestro arreglo sin usar todos nuestros números extras, por tanto esa no es una posibilidad.

Si se cumple que $1≤n≤7$ , de nuevo tenemos que fijarnos en el valor de $r$ para tomar la decisión de repetir un número o no.

$$ f(n,r) = \left\{ \begin{array}{ll} 1 & \mbox{if } n = 8\ and\ r = 0 \\ 0 & \mbox{if } n = 8\ and\ r \neq 0 \\ f(n,r-1) + f(n+1,r) & \mbox{if } r \neq 0 \\ f(n+1,r) & \mbox{if } r = 0 \\ \end{array} \right. $$

Por último, resta llamar a $f(1,R/2)$ para obtener el resultado. No olvides ir aplicando $%$ para mantener tu resultado en un rango correcto.

Pra obtener el preciado AC, tuve que implementar la DP de manera iterativa, ya que recursiva daba RTE

Código:

#include <cstdio>
#define L 7
#define MOD 1000000007
int N;
int m[10][1000010];
int dp(int i, int res){
    for(int ii = 8; ii >= 1; ii--) {
        for(int r = 0; r <= res; r++) {
            if(ii == 8) { 
                if(r) 
                    m[ii][r] = 0; 
                else 
                    m[ii][r] = 1; 
                continue; 
            }
            if(res){
                m[ii][r] = (m[ii][r-1] % MOD 
                                + m[ii+1][r] % MOD) % MOD;
            } else {
                m[ii][r] = m[ii+1][r] % MOD;
            }
        }
    }
    return m[i][res];
}
int main(){
    scanf("%d", &N);
    N++; N /= 2;
    if(N - L < 0) printf("0\n");
    else {
        printf("%d\n", dp(1,N - L) % MOD);
    }   
    return 0;
}

2958 - Almost Complete Binary Tree (COJ)


Link del problema: 2958 - Almost Complete Binary Tree

Dificultad: Medio

Información:
Un Árbol Binario Completo es un árbol binario en donde en cada nivel, excepto quizá en el último está completamente lleno, es decir, todos los nodos tienen dos hijos excepto en las hojas y además éstas hojas están lo más a la izquierda posible. Por ejemplo:


Sabiendo esto, si no está ni lleno ni con las hojas lo más a la izquierda posible, le podemos llamar un Árbol Binario Casi Completo. Como en el siguiente ejemplo:

Problema:
Dada una $1<=N<=3000$ como la cantidad de nodos totales de nuestro árbol, digamos ¿cuantos Árboles Binarios Casi Completos se pueden formar? Se piden $1<= T <=100$ casos de prueba.
Primero debemos preguntarnos por donde atacar este problema...
Veámos un ejemplo
Supongamos que tenemos una N = 4 o sea un árbol de 4 nodos y las diferentes combinaciones con 4 nodos pueden ser las siguientes:
Árbol 1:



Árbol 2:


Árbol 3:

Árbol 4:


Entonces tenemos todas las maneras de poder formar árboles con 4 Nodos pero si logramos observar en el Árbol 1 se cumple la condición de que sea un Árbol Binario Completo (lo cual no deseamos) puesto que tenemos las hojas lo más a la izquierda posible entonces ese árbol no se considera como solución y para N = 4 la respuesta de todos los Árboles Binarios Casi Completos es 3 (las tres últimas imágenes).

Si bien este problema podría verse con una solución con dp (Dynamic Programming) la solución que pude ver de inicio fue con combinatoria, no fue hasta hoy que en el Club de Algoritmia de mi escuela pude corroborar con el gran Edgar (Garo) que se podía resolver de ambas formas, por esta ocasión lo explicare con combinatoria.

Solución:
La idea es llegar al nivel en el árbol al número de nodos donde nos excedamos de nuestro número N para así poder contar sobre los nodos de ese nivel, de cuantas formas podemos acomodar los nodos que nos falte poner, vamos a ejemplificar con la misma N = 4.
Tomando el primer nivel donde nos excedamos de nuestra N = 4 el árbol quedaría así:
Figura 1

Un nivel anterior a este podemos ver que se pueden poner 3 nodos de la siguiente manera:
Figura 2

Pero nos faltaría 1 nodo para que se cumpliera nuestra N = 4 entonces debemos de ver de cuantas formas posibles se puede acomodar con 4 posiciones las cuales se mostraron en la Fig. 1
 Si regresamos a las figuras del inicio de los 4 árboles podemos observar las diferentes formas de poner el nodo que nos falta pero tendríamos que descartar la forma de poner un nodo lo más a la izquierda posible entonces nuestra fórmula se reduciría a obtener las combinaciones de los nodos que nos faltan por poner encima de todas las que podemos poner, menos uno. 
Así sería la respuesta nCr - 1 (n combina r menos uno) siendo n las formas de ponerlo, r los que nos faltan poner y el "-1" la que está lo más a la izquierda. 
Entonces para calcular las combinaciones tendríamos la fórmula
    n!
--------
r! (n-r)!
Pero calcular los factoriales tendría varios inconvenientes el desborde de las variables y que no suele ser tan eficiente ya que la complejidad sería O(n + r + n-r) o O(n) y además como tenemos varios casos por cada caso tendríamos que hacer este proceso.
Una de las formas óptimas sería hacer un precálculo de todas las combinaciones con el Triangulo de Pascal para el calculo de los coeficientes polinomiales y bastaría con tener los números para hacer la combinación antes dichos y buscar esas posiciones en la matriz donde calculamos el triangulo de pascal.
  0  1 2 3 4 5
  ---------------
0|1
1|1 1
2|1 2 1
3|1 3 3 1
4|1 4 6 4 1
5|1 5 10 10 5 1

Siendo que tendríamos que obtener 4C1 iríamos a la fila 4 columna 1, la cuál tiene un valor de 4 y como tenemos que quitarle 1 por la que está más a la izquierda nuestra respuesta sería 3.
Bien implementado nos tendría que dar siempre la respuesta.

Aquí insertaré el código de como programé mi triangulo de pascal:

int k=1;
 for(int i=0;i<3001 1="" for="" i-1="" i="" if="" int="" j-1="" j="" k="" mat="" mod="" pre="">
A eso solo tendrían que conseguir los elementos a combinar que es el último nivel del árbol y la resta de cuantos nodos son o sea N menos cuantos nodos hay un nivel anterior, y mandaríamos llamar a la respuesta en:
printf("%lld\n",mat[(p-1)%mod][(res2)%mod]-1);
Cabe decir que el cálculo del triangulo de pascal es una especie de tabla dinámica de dp.
Por esta ocasión fue todo y si necesitan un tema o problema no duden en sugerirlo.
Complejidad: La complejidad se reduciría a calcular el nivel del árbol el cual es O(log n) donde sobrepasa a nuestra N y el calculo de la matriz de pascal que aproximadamente es O(3000^2) pues a lo más nos piden 3000 nodos.

Abba (OmegaUp)


Link al problemaAbba

Dificultad: Medio

Problema: Dada una cadena $S$, $1 ≤ |S| ≤ 1000000$, y una operación $reemplaza(a, b)$ que reemplaza todas las ocurrencias del caracter $a$ por $b$ en $S$. Encontrar el mínimo número de aplicaciones de ella para que $S$ se convierta en un palíndromo.

Solución: A primera instancia parece un problema relativamente sencillo y conocido (la distancia de edición), sin embargo a pesar de que ese algoritmo nos da una solución, no es la óptima siempre puesto que no toma en cuenta la operación $reemplaza$ definida previamente. Para resolver este problema es necesario representarlo de una manera totalmente distinta: usando un grafo en el que cada caracter es un nodo y la aplicación de la operación $reemplaza$ entre ellos forma una arista.

Tomemos la cadena trestristestigres para desarrollar un ejemplo. Para resolverlo, debemos ver que cada letra del lado izquierdo se debe cambiar por una del lado derecho o viceversa para que se forme un palíndromo. Comenzaremos con la t más a la izquierda y la s más a la derecha, mira la tabla:
Cadena Grafo resultante
     _               _
     trestristestigres
    
     __             __
     trestristestigres
    
 ___           ___
     trestristestigres
    
 ____         ____
     trestristestigres
    
 _____       _____
     trestristestigres
    
 ______     ______
     trestristestigres
    
 _______   _______
     trestristestigres
    
 ________ ________
     trestristestigres
    
Debemos notar que a pesar de que en este caso una única componente incluye todos los nodos, podría suceder que no fuera así, y que los nodos estuvieran repartidos en distintas componentes.

Ahora, gracias a la ayuda del grafo podemos ver más sencillamente las transiciones que debemos hacer para convertir nuestra cadena en palíndromo, sin embargo también podemos observar que hay bucles inútiles, que si bien nos llevarían a una solución esta no sería la óptima. Usando $reemplaza(i, t)$, $reemplaza(e, r)$, $reemplaza(r, t)$, $reemplaza(g, s)$ y $reemplaza(s, t)$ la cadena original trestristestigres se convierte en ttttttttttttttttt que es un palíndromo. Tenemos que eliminar los bucles, haciendo uso de algún algoritmo (por ejemplo el de Kruskal) para convertir nuestro grafo en un árbol, por ejemplo este:

Por último nos podemos dar cuenta que en realidad no es necesario hacer la transformación de grafo a un árbol, solo llevar un conteo de los nodos en cada componente, puesto que sabemos que para que un grafo de $N$ nodos sea un árbol debe tener exactamente $N-1$ aristas.

Complejidad: $O(N)$, $N$ es la longitud de la cadena $S$ (formar el grafo es $N/2$, buscar las componentes conexas es $N$).

ACM contest and Blackout

Link del problema: 1010 - ACM contest and Blackout

Dificultad: Medio

Problema: El problema se resume a dar los dos árboles de expansión mínima o los árboles con el menor peso dada una entrada de N $ 3<= N <= 100 $ nodos (escuelas) y M aristas (conexiones).

Ejemplo: Para cada M línea sea darán 3 números Ai, Bi y Ci. Donde Ai y Bi serán las escuelas conectadas y Ci su precio para que estén conectadas.

4 5
4 1 4
4 2 7
1 3 1
1 2 5
3 2 6
Aquí el grafo original:


Las respuestas serían 10 y 11 ya que los arboles menos costosos se pueden formar así:




Ahora, ¿cómo conseguir esto?
Solución (algoritmo de Kruskal): 
Para los que no conozcan el algoritmo o no sepa como trabaja acá hay una buena explicación e incluso una implementación descargable muy entendible pues el mismo algoritmo usa la estructura de datos Union-Find.
Si bien obtener el MST (Minimum Spanning Tree) es fácil con Kruskal ¿como haríamos para asegurar el segundo árbol más barato? La idea básicamente es guardar las aristas con las que formamos nuestro primer MST y buscar formar árboles exceptuando cada una de las aristas una por una, es decir, quitamos una de las aristas y formamos un nuevo árbol, después la siguiente arista que guardamos y formamos otro árbol, siempre quedándonos con la MENOR.
Con una de las dificultades que me enfrenté es que al hacer kruskal omitiendo arista por arista no me aseguraba que se formara un árbol es ahí donde debemos comprobar que se forme un árbol efectivamente. ¿Cómo? en nuestro Union - Find podemos saberlo checando que solo haya una raíz, pues si solo hay una quiere decir que solo hay una componente conexa (que todos los nodos están conectados y forman el árbol).
Al hacer esto omitir arista por arista, checar que solo haya una componente conexa y quedarnos con la menor, nos dará el siguiente MST o árbol menos costoso.


En el siguiente fragmento de código lo que hago es conseguir omitiendo arista por arista tener el siguiente árbol de expansión mínima, checar que solo haya una componente conexa en el arreglo de padres y quedarme con la mínima:



Y bueno eso fue todo por esta ocasión, ya saben si gustan sugerir algún tema pueden hacerlo abiertamente y espero les haya gustado comenten si hay dudas y escriban. 
Adrián Fernández @ferprogramming

Chef and Frogs (FROGV - CodeChef)

Link al problemaChef and Frogs

Dificultad: Fácil

Problema:
Dadas $N$, ($1 ≤ N ≤ 10000$) ubicaciones enteras $A_i$ ($0 ≤ A_i ≤ 10^9$) y un entero $K$ ($0 ≤ K ≤ 10^9$) para cada rana, determinar si la rana $A$ ubicada en la posición $i$ puede comunicarse con la rana $B$ en posición $j$. Las ranas en posicion $i$ y $j$ se pueden comunicar siempre que entre ellas la distancia sea  $ ≤ K$ o entre ellas existan otras ranas que cumplan con la anterior condición. Las ranas son muy amigas y entre ellas se pasan el mensaje.

Solución:
Nos damos cuenta que cuando a una rana le llegue un mensaje esta se lo podría pasar a cualquiera otra que estuviera a menos de una distancia $K$ de su posición, por tanto partiendo de ese punto formaremos grupos de ranas que estarán comunicadas entre si, para lo cual usaremos union-find.

De entrada lo que debemos de hacer es ordenar las posiciones de cada rana, manteniendo el índice original en el cual estaban, posteriormente recorremos nuestro arreglo ya ordenado para unir a las ranas que se pueden comunicar.

Complejidad: $O(N log N)$ debido a la ordenación de las ubicaciones.

Código (C++):
Para facilitarnos las cosas emplearemos un arreglo la clase pair, otro arreglo de enteros llamado roots (necesario para la estructura union-find y las funciones join y root habituales) y unas definiciones para darle un poco de claridad al código:
#define place second
#define distance first
typedef std::pair<int,int> frog;
Una vez leídas las posiciones de las ranas, las ordenamos con respecto a la distancia en la que están, y recorremos el arreglo para unir a las que se puedan comunicar:
for(int i = 1; i <= N; i++){
 roots[i] = i;
 scanf("%d", &frogs[i].distance);
 frogs[i].place = i;
}
std::sort(frogs+1, frogs+N+1);
for(int i = 1; i < N; i++){
 if(frogs[i + 1].distance - frogs[i].distance <= K){
  join(frogs[i + 1].place, frogs[i].place);
 }
}
Una vez terminada las uniones basta con leer las consultas y determinar si la rana $A$ se puede comunicar con la rana $B$:
root(a) == root(b) ? printf("Yes\n") : printf("No\n");

Elevator Code (OmegaUp)


Link al problemaE - Elevator Code

Dificultad: Fácil

Problema:
Dada una cadena $E$, ($|E| ≤ 500$) compuesta por los símbolos #, + y - (La cadena no contendrá más de 7 # juntos) y una cadena de dígitos S, ($|S| =$ número de '#' en $E$). Acomodar cada uno de lo dígitos en $S$ en cada posición # en $E$ para que la operación que representa nos de como resultado el valor máximo.

Para mejor claridad veamos el caso de prueba:
##+##
1234
La mejor forma de acomodarlos para obtener el máximo es $32+41$ lo que nos da $73$ como resultado.

Solución:
Para encontrar el valor máximo de una suma tenemos que maximizar el valor de sus operandos mientras que para las restas tenemos que minimizarlo. Una forma de hacerlo es separar la cadena $E$ en grupos de #, de tal manera que llevemos la cuenta de qué tan grande es el número (cantidad de dígitos) y podamos identificar entre los que son positivos o negativos. Sabiendo esto repartiremos los números en $E$ haciendo que los de mayor valor queden en los grupos positivos con mayor cantidad de dígitos y los de menor valor queden en los negativos con mayor cantidad de dígitos.

Los dígitos se deben repartir en un orden peculiar para que el resultado nos de la solución deseada, y es que primero se deben repartir la cantidad más grande (en el caso del ejemplo anterior son las decenas, números 4 y 3) y luego las unidades. Una vez que se hizo esto se deben repartir a los grupos negativos los dígitos con menor valor siguiendo lo anteriormente dicho.

Después bastara con sumar/restar los valores resultantes de la operación anterior para obtener el resultado.

Complejidad: $O(N log N)$ debido a la ordenación de los dígitos en $E$.

Código (C++):
Para facilitarnos las cosas, definiremos una estructura que contenga la información que necesitamos acerca de los grupos de #.
struct Group{
 int o; // Original index
 int v; // Value of the group  
 int d; // Digit amount
 int s; // Positive or negative: 1 or -1
 int value(){ // Return the final value
  return s * v;
 }
};
Definimos además un arreglo nums de tamaño k donde se almacenarán los dígitos de la cadena $E$ ordenados de manera descendente, un arreglo G de tamaño p de la estructura Grupo donde almacenaremos nuestros grupos ordenado del número positivo con mayor cantidad de dígitos al número negativo con menor cantidad de dígitos.
En el siguiente fragmento de código se reparten los dígitos a los grupos positivos:
  int n = -1;
  int neg;
  int ii = 0;
  int ix = 0;
  n = G[0].d;
  while(n > 0 && G[0].s > 0){
   for(ix = 0; G[ix].d == n && ix <= p; ix++){
    if(G[ix].s < 0) { break; }
    G[ix].d--;
    G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
    ii++;
   }
   n = G[0].d;
  }
En este se reparten a ls números negativos, no sin antes invertir el orden de los números, dejando el arreglo nums ordenado de manera ascendente:
   reverse(nums+ii, nums+k);
   neg = ix;
   n = G[ix].d;
   while(n){
    for(; G[ix].d == n && ix <= p; ix++){
     G[ix].d--;
     G[ix].v = (nums[ii] * pow(10,n-1)) + G[ix].v;
     ii++;
    }
    n = G[neg].d;
   }

Para finalizar, basta con sumar los valores de nuestro todas nuestras estructuras Grupo para obtener el resultado:
  int res = 0;
  for(i = 0; i <= p; i++){
   res += G[i].value();
  }
  printf("%d\n", res);