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);

Sums in a Triangle I (COJ)

Link del problema: 1079 - Sums In a Triangle I

Dificultad: Fácil


Problema: Dado un número $N$ donde $1<=N<=100$ se tienen $N$ niveles en un triangulo, así el primer nivel tiene 1 número, el segundo nivel tiene 2 números, el tercero 3, etc. El programa debe encontrar la máxima suma desde el primer nivel hasta el último pudiendo tomar una ruta tal que solo se acceda al número de abajo o al de abajo y una posición a la derecha...

Ejemplo:
Con $N = 3 $
Tenemos el siguiente triángulo:
1
1 2
2 3 1

La respuesta es 6 ya que primero solo tomamos el primer elemento pues no hay más opción ya que es el único elemento en la fila en la siguiente podemos tomar el 1 o 2

1
1 2  //La mejor opción aquí es tomar el de abajo y a la derecha que es  el mayor
2 3 1

Hasta este punto llevamos la "mejor" ruta posible habiendo tomado los elementos de mayor prioridad entonces en la siguiente iteración solo podemos tomar dos elementos:
1
2  
2 3//La mejor opción aquí es tomar el de abajo que es  el mayor
Y así por fin llegar a nuestro cometido que era tomar la ruta tal que la suma sea la mayor...


Solución: (DP)
Este problema se resuelve con Programación Dinámica (DP) ya que tenemos que tomar una decisión en cada nivel (la mejor) y así ir tomar la mejor ruta que podamos, entonces como se mencionó en nuestra otra publicación de DP tenemos que establecer los ESTADOS de la DP y las DECISIONES para lo cual nuestros estados tendremos:
 int dp(int i,int j){
 }
Necesitaremos un apuntador a la columna donde estemos (i) y uno para la fila (j) para saber en que número vamos.
Lo siguiente es establecer donde se tendrá que detener la DP así que necesitamos un caso base para la recursión. Para lo cual:

if(i==n)
   return 0;
Vemos que si nuestro apuntador llega a la última columna tendremos que detener la DP.
Por último necesitamos nuestras decisiones, aquí solo basta con devolver el MÁXIMO entre tomar el de abajo dp(i+1,j) y tomar el de abajo y una posición a la derecha dp(i+1,j+1) y sumar en cada decisión el elemento que corresponde a esa posición de la siguiente manera:
return max(dp(i+1,j)+piramide[i+1][j],dp(i+1,j+1)+piramide[i+1][j+1]);
Y así se resolvería el problema, cabe decir que mis números los guarde en un arreglo llamado pirámide para así poder usarlos después y sumarlos. Ahora un punto IMPORTANTE al final a la respuesta que devuelva esta función tenemos que sumarle el primer elemento del triángulo ya que aquí NO estamos considerándolo.
res = dp(0,0);
printf("%d\n",res + piramide[0][0]);
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

1047 - Visible Lattice Points

Link al problema1047 - Visible Lattice Points

Dificultad: Fácil

Problema:
Un punto lattice $(x, y)$ en el primer cuadrante ($x, y0$ son números enteros mayores o iguales a 0), que no sea el origen, es visible desde el origen si la línea de $(0, 0)$ a $(x, y)$ no pasa a través de cualquier otro punto lattice. Escriba un programa que, dado un valor para el tamaño $N$ ($1 ≤ N ≤ 1000$), calcula el número de puntos visibles $(x, y)$ con $0 <= x, y <= N$.

Solución:
Para resolver este problema trazaremos las rectas (imaginariamente) desde todos los puntos que pueden existir en la cuadrícula hacia el origen. Dichas rectas, además de pasar siempre por el origen, la coordenada $(x_2 = 0, y_2 = 0)$, también deberán pasar por el punto $(x_1 = x, y_2 = y)$ donde $0 ≤ x, y ≤ N$. Recordemos la ecuación de la recta: $(x_2 - x_1) / (y_2 - y_1) + b$, por tanto para nuestras rectas la ecuación se reducirá a $x / y$.
Podemos ver que algo sucede con los puntos que no son visibles, y es que la recta que los une puede ser expresada por un múltiplo de la recta de uno que si es visible. El caso más sencillo: tomando el punto visible $(1, 1)$ y el punto no visible $(3, 3)$, tenemos que las coordenadas del punto no visible es tan solo $(3 * 1) / (3 * 1)$, la forma para identificar esto es obtener el MCD de $x$ y $y$, mientras que para el punto visible $MCD(x, y) = 1$, para el no visible $MCD(x, y) > 1$.

Ahora solo hay que obtener todos los puntos dentro de nuestra cuadrícula cuyo MCD sea igual a 1 para cada consulta que nos hagan. Esto es sencillo pero es un gasto inecesario de recursos, por lo que lo mejor es realizar un precálculo partiendo de que para $N = 0$ la respuesta es $0$ y para $N = 1$ la respuesta es $3$. Otro punto a considerar es que podemos solo calcular la mitad de los puntos ya que los puntos son simétricos.

Complejidad: $O(N)$ donde $N$ es el tamaño máximo de nuestra cuadrícula

Código (C++):
Definiremos un arreglo a donde a[i] será la cantidad de puntos visibles para el número i-ésimo dado.

Precálculo:
a[0] = 0;
a[1] = 3;
for(int x = 2; x <= 1000; x++){
 int sum = 0;
 for(int y = 1; y < x; y++){
  if(mcd(x,y) == 1) sum++;
 }
 a[x] = a[x-1] + 2 * sum;
}

2533 - Connecting Cities (COJ)

Link al problema2533 - Connecting Cities

Dificultad: Medio

Problema:
Dado un conjunto de $N$ ($1 ≤ N ≤ 2000$) ciudades y $M$ ($0 ≤ M ≤ 50000$) carreteras cada una con un costo $P_i$ ($0 ≤ P_i ≤10^7$) de construcción distinto y un costo $C$ ($0 ≤ C ≤10^7$) por construir un aeropuerto, determinar el menor costo para conectar las $N$ ciudades. En este problema el aeropuerto cumple una función peculiar, ya que una carretera que va de una ciudad A a una ciudad B funciona como una arista bidireccional en un grafo; mientras que colocar un aeropuerto en una ciudad A forma una arista bidireccional con cualquiera otra ciudad que tenga un aeropuerto.

Solución:
Del problema mismo sabemos que para que dos ciudades se consideren conectadas debe existir una o varias aristas entre ellas. También sabemos que para obtener el costo mínimo la forma final de las conexiones debe ser un árbol (para evitar ciclos y por tanto aristas innecesarias), ya que en un árbol solo ocuparíamos $N - 1$ aristas. De inmediato el problema nos suena como a un simple árbol de mínima expansión... pero, ¿qué sucede con los aeropuertos?

El problema nos indica que pueden existir desde $0$ hasta $50000$ carreteras, por lo cual nosotros podemos esperar que existan ciudades a las cuales no es posible llegar por ninguna carretera y por lo tanto tratar de considerarlos en un árbol de mínima expansión es imposible (llamaremos componente conexa a un conjunto de $n$ ciudades unidas con $n - 1$ carreteras), es ahí donde los aeropuertos tienen una de sus funciones principales. Otra función de los aeropuertos se da cuando construir una carretera entre A y B es más costoso que construir un áeropuerto en A y B.

Recapitulando: sabemos que pueden existir varias componentes conexas, sabemos que construyendo un aeropuerto en cada una de ellas garantizaría que estén conectadas, sabemos que a veces el costo de construir una carretera entre dos ciudades es mayor al de poner aeropuertos en ellas y por último sabemos que queremos obtener el menor costo para conectarlas todas.

Para resolverlo, partiremos de que cada una de las $N$ ciudades tiene un áeropuerto y por tanto están todas conectadas lo cual tendrá un costo $C_0$, posteriormente iremos uniendo (como si estuvieramos formando un árbol de mínima expansión) a cada unión quitaremos un aeropuerto, ya que no es necesario una vez que exista una carretera entre dos ciudades, porque estas estarían conectadas de todos modos, al hacer esto obtendremos un costo $C_i$ ($1 ≤ i ≤ Z$, $Z$ es el número de uniones que es posible realizar), lo que nos queda por hacer extraer el valor mínimo de todos los $C_i$ para obtener la respuesta.

Lo único que resta por considerar es que de este modo de resolver el problema puede suceder que al final nos quede una sola componente conexa y por tanto un solo aeropuerto, lo cual representa un gasto innecesario y por tanto no debe ser parte de nuestra solución.

Complejidad: $O(M)$ donde $M$ es el número de carreteras

Código (C++):
Definiremos una función join(a, b) que intenta unir a con b y devuelve true si la unión fue posible. En un vector denominado roads tendremos las carreteras (con su origen 'o' y destino 'd') ordenadas de menor a mayor costo 'c'.

long long int ans = N * C;
long long int roadCost = 0;
int airports = N;
for(int i = 0; i < roads.size(); i++){
 if(join(roads[i].o, roads[i].d)){
  roadCost += roads[i].c;
  airports--;
  ans = min(ans, roadCost + airports * C);
 }
}
if(airports == 1)
 ans = min(ans, roadCost);
pritnf("%lld\n", ans);

Parsing Binary Strings (COJ)

Link del problema: 2858 - Parsing Binary Strings

Dificultad: Fácil.


Problema: Dada una cadena S que solo tiene números binarios y letras minúsculas de la 'a' a la 'z' imprimir todos los caracteres excepto las cadenas de números binarios, a estas cadenas convertirlas a su representación decimal e imprimirlas junto a la cadena. A lo más serán 10,000 caracteres para lo cual es necesario sacar modulo 1000000007 (10^9 + 7) ya que el número puede ser muy grande.

Ejemplo:
Input:
saludosamis11amigosqueestana1010kilometrosdedistancia
Output:
saludosamis3amigosqueestana10kilometrosdedistancia

Complejidad: O(N) donde $1<=N<=10000$ es el número de caracteres dentro de la cadena.

Solución:

Este problema es muy simple ya que basta con ir recorriendo caracter a caracter y checar que si no es 1 ó 0 solo lo imprimamos el caracter pero ¡¿que pasa cuando es Binary String!?
Lo primero que se nos ocurriría es tratar la Binary String con corrimientos pero dado que el número puede ser muy grande esto no funcionaría así que con una simple operación de multiplicar por 2 cada que haya 0 o 1 será suficiente. 

Primero hacemos un define de nuestro modulo para no tener que estar poniendo tanto 0 xD:
#define modulirri 1000000007

Así pues tendríamos dos decisiones:
numerote = 0;
if(S[i]=='1'){
    numerote *= 2;
    numerote += 1;
    numerote %= modulirri;
}
Nótese que primero debemos multiplicar por dos nuestro número ya que si tenemos el caso que la cadena sea de tamaño N = 1 entonces nos daría la respuesta 2 porque primero sumamos uno y luego multiplicamos por dos pero basta con primero multiplicar y después sumarle el 1. La otra decisión:
else if(S[i]=='0'){
   numerote *= 2;
   numerote %= modulirri;
}
Y no olviden ir multiplicando por dos para aumentar el número ;).

Y bueno eso fue todo por esta ocasión si pueden y quieren compartir háganlo, mi equipo y yo estamos a la disposición de sugerencias de problemas de programación competitiva, saludos!!!
Por Adrián Fernández @ferprogramming

DP (Programación Dinámica)


Tema:

La programación dinámica es un tema muy usual en las competencias de programación y a la vez una técnica que requiere de cierta práctica para empezar a dominarse. Bien empleada la programación dinámica puede ser muy útil para resolver problemas que requieran minimizar el tiempo de ejecución de su algoritmo y a la vez requieran checar muchas soluciones para encontrar la óptima.

Las "DP's" dividen un problema en sub-problemas es decir resuelven un "gran" problema partiendolo en problemas pequeños para así llegar a la solución. Suele relacionarse con la definición de recursividad pero no debe confundirse ya que a veces la programación dinámica requiere de la misma recursividad para emplearse.
Hay dos estilos (tipos tal vez) de programación dinámica la Top-Bottom y la Bottom-Top que son dos diferentes enfoques de ver las soluciones con DP's y la forma en como las programamos también. Para este problema usaremos Top-Bottom (Recursiva).
Lo primero que hay que hacer para resolver un problema bajo DP es ver y analizar que posibles "estados" que tendrá nuestra función dp();
Para ello usaré como ejemplo un problema de COJ llamado 

Link del problema: Coin Change
Dificultad: Fácil

Problema:

Este problema consiste a grandes rasgos en decir de cuantas maneras podemos representar un numero $N$ con $0<= N <= 10,000$, con 5 tipos de monedas de cambio (50,25,10,5 y 1) por ejemplo el caso de prueba que viene en la página
Con dinero = 11 ¿De cuántas formas se puede expresar?


Solución:
1° 1+1+1+1+1+1+1+1+1+1+1 = 11 
2° 5+5+1 = 11 
3° 1+1+1+1+1+1 + 5 = 11
4° 10 + 1 = 11
Para este caso es evidente que la solución es 4 porque solo existen 4 maneras diferentes de representar nuestro número N.

Paso 1 (Identificar los estados de nuestra dp() ): 

-¿De que estados o variables depende?
Para este problema necesitamos tanto la cantidad de 'dinero' que llevamos hasta el momento y además que 'monedas' utilizamos.

int dp(int dinero,int i);

además de devolver el valor que procese nuestra dp() como int

Paso 2 (Decisiones: "Tomar o no tomarlo")

Esta parte de la dp() es muy importante ya que de aquí deriva el buen funcionamiento de la misma

-¿Qué decisiones podemos establecerle a este problema?

Supongamos que tenemos un arreglo cambios de la siguiente manera:
int cambios[] = {50,25,10,5,1};
Además supongamos que tenemos nuestro total de dinero y cada que tomemos o no un cambio[] se lo restaremos al total de dinero entonces sabremos cuando frenar la dp(); y saber que ya hemos procesado todo así:

if(dinero==0)
   return 1;

Como caso base de la DP quiere decir que ya le restamos todo a nuestro dinero entonces para ese entonces ya abremos tomado todas las decisiones 
if(dinero!=0 && i==5)
   return 0;
Es otra decisión pues quiere decir que terminamos de recorrer nuestro arreglo de monedas pero que no llegamos a nuestro dinero==0 o sea que no quedó justa la resta de los dineros.

Ahora las decisiones tienen que ver con que el número del arreglo no sea mayor a nuestro dinero, SI ES MAYOR NO LO TOMAMOS y avanzamos al siguiente elemento SI ES MENOR O IGUAL lo tomamos y se lo restamos a nuestro dinero OJO (mandamos ambas probabilidades tomarlo y no tomarlo) para que se realice el árbol y tome todas las posibilidades...
if(cambios[i]>dinero)
     return dp(dinero,i+1);

  if (cambios[i] <= dinero) 
     return dp(dinero - cambios[i],i) + dp(dinero,i+1);

Esto tiene una complejidad O($2^N$) así que haría falta memorizarlo para hacerlo pueden checar el siguiente enlace donde explico en mi blog como memorizar (memoizar) una función recursiva y eso nos reducirá la complejidad de la siguiente DP a O($n^2$) y aquí ya la función dp() memorizada:

 int dp(int dinero,int i){

   if(memo[dinero][i]!=-1)
      return memo[dinero][i];
   if(dinero==0)
      return 1;
   if(dinero==0 && i==5)
      return 1;

   if(i==5)
      return 0;

   if(cambios[i]>dinero)
      return memo[dinero][i] = dp(dinero,i+1);

   if (cambios[i] <= dinero) 
      return memo[dinero][i] = dp(dinero - cambios[i],i) + dp(dinero,i+1);
}
Esta es una DP sencilla pero en sí mejorar y perfeccionar esta técnica requiere mucha práctica aunque seguro hay un AC con este código, así que eso es todo por esta sesión. 

Por: Adrián Fernández @ferprogramming

Madrigueras (OmegaUp)

Link al problemaMadrigueras

Dificultad: Medio

Problema:
El principal problema radica en encontrar una manera correcta de representar la información que se nos da, la manera más sencilla es representar cada camino hecho por una suricata como una arista unidireccional. Por lo tanto tenemos $N$ ($1 ≤ N ≤ 10^5$) nodos y $M$ aristas entre ellos.

Como ejemplo de lo anterior, veamos cómo representaríamos el caso de prueba de diversas maneras:
Entrada: Representación: Explicación:
5 4
1 2
3 2
4 5
4 5
Las aristas rojas nos indican que la suricata 3 creó un camino hacia el cuarto 2, mientras que la suricata 2 creó un camino hacia el cuarto 1.
Las aristas azules nos indican que la suricata 3 creó un camino hacia el cuarto 2, mientras que la suricata 1 también creó un camino hacia el cuarto 2 y así sucesivamente.

En la imagen anterior también se puede observar algo peculiar, y es que para cada componente conexa solo existen dos posibilidades válidas para colocar las aristas (de acuerdo al problema): Cada componente con $V$ nodos debe tener a lo más $V$ aristas, ya que de tener más implicaría que una suricata construyó más de un camino, lo cual no es posible.

Para responder al problema necesitamos conocer de cuantas maneras se pueden colocar las aristas, dadas las condiciones establecidas anteriormente. Para una componente conexa de $N$ nodos con $N - 1$ aristas (un árbol), podemos elegir cualquiera de los $N$ nodos como la raíz, dejandonos con un total de $N$ maneras de formarlo. Mientras que para una componente con $N$ aristas (un grafo cíclico) solamente tenemos $2$ maneras.

Solución:
Dado que el problema implica componentes conexas, emplearemos la estructura disjoint-set para llevar un registro de ellas. También sabemos que necesitamos conocer la cantidad de nodos y aristas dentro de una misma componente, para lo cual podemos emplear alguna clase de búsqueda en grafos, sin embargo, también podemos modificar las operaciones del disjoint-set para llevar el conteo de los nodos y aristas; la modificación propuesta radica en que a cada llamada a la función unir siempre sumémos una arista a nuestra componente, sin importar si dicha unión representaría un ciclo.

Por último, la respuesta esperada se obtiene de multiplicar las formas de ordenar las aristas para cada componente y aplicarles la operación módulo, ya que el resultado puede ser bastante grande.

Complejidad: $O(M)$, donde $M$ es el número de aristas especificadas en el problema

Código (C++) y pseudocódigo:
Implementación de disjoint-set (C++):
Definiremos un arreglo V, donde V[i] es la cantidad de vértices que tiene la componente i-ésima. Definiremos un arreglo E, donde E[i] es la cantidad de aristas que tiene la componente i-ésima. Definiremos un arreglo G, donde G[i] es el identificador de la componente i-ésima.
// Join function
void join(int i, int j){
 int pi = root(i);
 int pj = root(j);
 E[pi] += 1; // Siempre sumar una arista a nuestra componente
 if(pi != pj){
  G[pj] = G[pi];
  V[pi] += V[pj];
  E[pi] += E[pj];
 }
}

// Root function
int root(int n){
 if(G[n] != n) 
  G[n] = root(G[n]);
 return G[n];
}

Solución al problema (pseudocódigo):
Sea K un arreglo con todos los identificadores de cada componente conexa:
var res := 1
foreach i in K
 if E[i] = V[i]
  res := res * 2
 elsif E[i] = V[i] - 1
  res := res * N
 else
  res := 0
end foreach
print res mod 1000000007

Cookie Clicker Alpha (Code Jam 2014)

Link al problemaProblem B. Cookie Clicker Alpha

Dificultad: Fácil

Problema:
El problema es una simulación basada en un juego, para este caso particular se tiene que el jugador comienza con $0$ galletas y gana $2$ por segundo, una vez que después de cierto tiempo junta $C$ ($1 ≤ C ≤ 10^4$) galletas, puede comprar una fábrica que le otorgará que aumentará en $F$ ($1 ≤ F ≤ 100$) la cantidad de galletas producidas por segundo.

El juego termina una vez que el jugador tiene $X$ ($1 ≤ X ≤ 10^5$) galletas que no ha gastado en fábricas. Ahora es nuestro turno de responder cuál es el menor tiempo en el que podemos terminar el juego.

Solución:
La solución podemos obtenerla analizando el caso de prueba, que tiene como valores de entrada: $C=500.0$, $F=4.0$ y $X=2000.0$. Ejecutando la simulación para que realice la simulación de comprar (en este caso) hasta 10 fábricas aumentando con ello la cantidad de galletas producidas por segundo y obteniendo menor de los tiempos en el que se completará la tarea de juntar $X$ cantidad por cada nueva fábrica comprada. En la siguiente tabla se observan los resultados de la simulación y en la gráfica se observa mejor lo que sucede:
De la gráfica se observa que solo existe mínimo absoluto, ya que a partir de cierta cantidad de fábricas comprada a pesar de que es más rápido obtener las cantidad, el tiempo gastado en comprar fábricas hace que ya no sea una opción viable.

Por tanto es solo necesario verificar el punto en el que nuestro tiempo para llegar al objetivo comience a crecer.

Complejidad: $???$
Código (C++):
#include <cstdio>
#include <algorithm>
using namespace std;
float C, F, X, s, g;
int main(){
 int T;
 scanf("%d",&T);
 for(int ix = 1; ix <= T; ix++){
  double gs = 2;
  double t = 0;
  double tg = 0;
  double nuevo = 0;
  double previo = 0;
  bool primerCaso =  true;
  scanf("%f%f%f", &C, &F, &X);
  while(true)
  {
   nuevo = tg;
   tg = (X / gs) + t;
   previo = tg;
   if(nuevo < previo && !primerCaso) break;
   t += C / gs;
   gs += F;
   primerCaso = false;
  }
  printf("Case #%d: %.7f\n",ix,nuevo);
 }
 return 0;
}

Chef and Digits (ADIGIT - CodeChef)

Link al problemaADIGIT (Practice)
Link al editorial en CodeChefADIGIT - Editorial

Dificultad: Fácil

Problema:
Dados $N$ ($N ≤ 10^5$) dígitos y $M$ ($M ≤ 10^5$) consultas que consisten en un entero $x$ ($1 ≤ x ≤ N$), que llamaremos step (paso), imprimir el resultado de $B1 - B2$, donde:
  • $B1$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b > 0$
  • $B2$ := Sumatoria de todos los $b = a_x - a_y$ tal que $x > y$ y $b < 0$

Solución:
Veamos el siguiente caso, con entrada a = 0123152397

Calculando los valores para todos los pasos tenemos lo siguiente:

En la tabla anterior he marcado dos casillas, para observar a detalle lo que sucede:
  • Para el paso 4 tenemos: $B1 = (3 -0) + (3 - 1) + (3 - 2) = 6$ y $B2 = 0$ lo cual nos da el valor de $6$
  • Para el paso 8 tenemos: $B1 = (3 - 0) + (3 - 1)+  (3 - 2) + (3 - 1) + (3 - 2) = 9$ y $B2 = (3 - 5) = - 2$, por lo tanto tenemos $B1 - B2 = 11$
Observando las ecuaciones anteriores, podemos notar que el paso 11 se compone del paso 3 en las sumas $(3 - 0) + (3 - 1)+ (3 - 2)$ más otras 3 sumas, así que ¿qué pasaría si los almacenamos para no volver a calcularlo todo? Basándonos en eso, almacenamos los resultados en otro arrelgo.

Ahora, ¿cómo es que sabemos que tenemos un valor ya calculado?, esto es sencillo de encontrar y ocurre cuando los números $a_x$ y $a_y$ son iguales. Si los calculamos de manera secuencial, es decir de 1 hasta N, estaremos garantizando que para cada paso los pasos previos ya estarían precalculados, como solo hay 10 dígitos distintos, en el peor de los casos terminaremos sumando 10 veces. Al terminar el precálculo, para cada consulta que nos hagan la respuesta será obtenida en tiempo constante

Complejidad: $O(10 * N) + O(M)$

Código (C++):
Definiremos un arreglo A, donde A[i] es es valor de paso i-ésimo del problema y s, un arreglo de char, donde s[j] es la posición del dígito j-esimo.
void precalc(){
 int t = 0;
 for(int step = 0; step < n; step++){
  int ans = 0;
  for(int i = step-1; i >= 0; i--){
   t = (s[step] - '0') - (s[i] - '0');
   if(t == 0){
    ans += A[i];
    A[step] = ans;
    break;
   }
   ans += abs(t);
   A[step] = ans;
  }
 }
}
Haciendo que para responder a las consultas q, solo será necesario imprimir el valor almacenado en A[q-1]
int main(){
 scanf("%d%d",&n,&m);
 scanf("%s",s);
 precalc();
 while(m--){
  scanf("%d",&q);
  printf("%d\n", A[q-1]);
 }
 return 0;
}