Solución a “Cambio”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 7
Autor: Enrique Lira Vargas

Lo importante de este problema es notar como se puede usar un backtracking para contar cosas. En este caso lo que se debía contar era la cantidad de formas de llegar a una cantidad sumando una o más veces una serie de cantidades dadas.

Solución de 30, 50 puntos

Generar todas las combinaciones que sumen la cantidad C pedida. Para hacer esto se puede hacer con una búsqueda en profundidad de manera ordenada de la misma forma que se calculan permutaciones pero cuidando que la suma no sobrepase el valor C deseado. Esto se puede considerar una búsqueda podada.

Solución de 100 puntos

Consideremos la solución anterior y tratemos de calcularlo de abajo hacia arriba, habría que crear una función que nos dijera para una cantidad dada y un set de monedas que se pueden usar (para no repetir) nos diga cuantas formas distintas hay de completar dicha cantidad. Si se logra construir dicha función la solución al problema es simple puesto que se reduce a llamar dicha función con la cantidad que nos piden y el set completo de monedas. Lo interesante radica en cómo se compone dicha función, suponiendo que la función funciona hay que tratar de construirla, primero hay que considerar los casos especiales, si la cantidad es cero significa que no hay que hacer nada y entonces hay una forma de lograrlo (es una combinación válida), si la cantidad es mayor a cero hay que sumar las combinaciones de tomar una moneda de la primera denominación disponible con las de dejar de tomar monedas de dicha denominación.

  • Para calcular las combinaciones de tomar una moneda de dicha denominación se puede usar la función a partir de la cantidad restante (la cantidad buscada menos la denominación de la moneda) y el mismo set de monedas.

  • Para calcular las combinaciones de dejar de tomar monedas de cierta denominación de igual forma se puede usar la función con la misma cantidad pero con un set de monedas que no incluya la denominación que decidimos dejar de tomar.

Si se toma la moneda sin considerar si la denominación es más grande que la cantidad entonces existe el caso donde la cantidad es negativa y en ese caso la respuesta debiera ser cero puesto que es una combinación no válida.

De igual forma si el set de denominaciones disponibles está vacío significa que ya no hay más denominaciones para probar y por lo tanto no hay ninguna forma de lograrlo.

Como podemos notar dicha función es recursiva y se llama a si misma hasta que la cantidad se vuelve cero, negativa y/o el set de denominaciones queda vació, y si lo analizamos un poco podemos darnos cuenta de que funciona.
La forma simple de saber que set de monedas es usable es guardar el índice de la primera moneda usable y eliminarlas en orden.
Hay que notar que hasta el momento no hemos mejorado en nada la solución anterior, y la complejidad de esto es similar a la de nuestra idea anterior.

Lo que hay que notar es que la cantidad no tendrá más de 10,000 valores distintos y que nunca habrá más de 100 sets distintos, por lo tanto dicha función solo se puede mandar a llamar 1,000,000 de veces con parámetros distintos. Sin embargo sabemos que la cantidad de combinaciones puede llegar a ser mucho mayor. Entonces ¿Qué sucede?, pues es sencillo darse cuenta que dicha función se mandará a llamar más de una vez con los mismos parámetros y en todos esos casos siempre deberá entregar la misma solución, es por esto que podemos guardar las respuestas para cada uno de los casos en un array y así nunca tener que calcularlos más de una vez, esto hace que nuestro programa pueda correr en tiempo.

El asunto de los módulos creo que es algo que debiesen saber sin embargo les digo que el modulo se puede aplicar al sumar el tomar y el no tomar, puesto que (A + B) modulo X es igual a (A modulo X + B modulo X ) modulo X.

Solución a “Minecraft”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 5
Autor: Enrique Lira Vargas

Este problema no requiere ninguna observación específica y realmente lo único que hay que hacer es una búsqueda.

Para los primeros 50 puntos

Este primer sub set de casos se puede resolver implementando una búsqueda en amplitud que nos dé el camino más corto entre dos puntos en un mapa con paredes.

Para los 75 puntos

Para este punto se me ocurrió una solución factible para aquellos que no saben construir una cola de prioridad, correr una búsqueda en amplitud con dos colas cuidando elegir siempre la siguiente posición con una menor cantidad de movimientos de las dos colas.

Para los 100 puntos

Esta solución era para aquellos que supieran hacer una búsqueda utilizando una cola de prioridad. La idea es que al sacar un elemento de la cola siempre nos dé aquel al que se puede llegar con la menor cantidad de movimientos. Este procedimiento es idéntico a una búsqueda en amplitud solo que se utiliza una cola de prioridad. En la solución hago uso de un montículo como cola de prioridad.

Solución a “K-Arbol”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 5
Autor: Saul de Nova Caballero

En pocas palabras el problema es, dado un árbol que se puede colorear, encuentra la menor solución satisfaciendo las restricciones dadas sobre los colores. Este problema es un caso particular de Graph Coloring(en español coloración de grafos), en donde el grafo es un árbol.

Subcaso 1(10 puntos)

Para el primer subcaso era posible hacer una búsqueda en profunidad sobre todos los nodos, encontrando la menor solución. Para guardar el árbol, era posible utilizar una matriz que guardara todos los colores posibles y entonces ver si era posible una solución con el menor color posible. La solución de este caso era trivial si se usaba una búsqueda exhaustiva.

Subcaso 2(20 puntos)

Para el segundo subcaso era necesario una mejor estrategia. Para este caso, era necesaria la observación de que todos los colores de los nodos solo dependen de su padre y de sus hijos. Otra observación importante era que para los nodos del árbol, excepto las hojas, había que procesar a sus hijos menores.Procesar implica checar que colores puede tener un nodo. Por lo que para lograr los puntos en este subcaso era necesario procesar los nodos hijos, luego sus padres y asi sucesivamente. Es decir para procesar, un nodo primero hay que procesar a todos sus hijos.

La forma de procesar a un nodo es la siguiente. Por cada nodo se compara con su padre y al momento de comparar, lo que se busca es que por cada color del nodo, el padre no tenga un color que lo elimine como opción. Es decir tengo el siguiente caso

Nodo -> Rojo, Verde, Azul

Padre -> Rojo, Verde

Por cada color del nodo, el padre puede elegir un color distinto. Por ejemplo, si el Nodo es Rojo, el padre puede ser Verde. Si el nodo es Verde, el padre puede ser Rojo y si el nodo es Azul, puedes elegir el Rojo o el Verde. Sin embargo, para el siguiente caso

Nodo -> Rojo, Verde, Azul

Padre -> Rojo

El padre del nodo solo puede ser Rojo, por lo que para que las condiciones del problema se cumplan, el Nodo no puede ser Rojo. En este caso actualizamos la tabla de valores posibles del Nodo. Y queda como

Nodo -> Verde, Azul

Padre -> Rojo

Lo anterior se hace para cada par de nodos desde los nodos hoja hasta la raíz. Procesandolos de menor a mayor da la mejor solución

Subcaso 3(20 puntos)

Para obtener los puntos del subcaso 3 era posible simplemente ver por cada nodo procesarlo comenzando en la raíz, ya que en este caso el grafo en basicamente una gran línea. Utilizando la técnica descrita en el subcaso 2 por cada nodo se obtenía una solución a este subcaso

Subcaso 4(50 puntos)

Para los puntos del cuarto caso era necesario “linearizar” el grafo, esto simplemente significa que los nodos mas arriba van a tener menor prioridad que los nodos de abajo, es decir el nodo raíz tendría valor 0 mientras que sus hijos tendrían valores más altos. Por ejemplo para un caso asi:

0 -> 1 -> 4

-> 2

-> 3

El nodo 0 es la raíz del árbol, el nodo 1 y 3 son hijos de 0 y los nodos 2 y 4 son hijos de 1, el arbol se linearizaría de la siguiente manera:

0 -> 1, 1 -> 2, 3 -> 3, 4 -> 4, 2 -> 5

Ahora lo que es necesario hacer es por cada nodo de mayor prioridad a los de menor prioridad es necesario hacer la técnica explicada en el subcaso 2.Tomando en cuenta otra observación. Que solo es necesario procesar los nodos que solo tengan un color. Es decir si el nodo 0 tiene posibilidad de ser Rojo, Azul o Verde, no es necesario procesarlo. Sin embargo si un nodo solo puede ser azul, hay que eliminar esa posiblidad tanto de su padre como de sus hijos.

Imagen obtenida de http://aima.cs.berkeley.edu/newchap05.pdf
  1 // karbol100.cpp
  2 // By Saul de Nova Caballero
  3 
  4 //Librerias de la standard template library de c++(stl)
  5 #include <algorithm>
  6 #include <cassert>
  7 #include <cstdio>
  8 #include <cstdlib>
  9 #include <cstring>
 10 #include <iostream>
 11 #include <list>
 12 #include <utility>
 13 
 14 using namespace std;
 15 
 16 //Iterador sobre estructuras de datos. En este caso listas de la stl
 17 #define TR(container, it) \
 18     for(typeof(container.begin()) it = container.begin() ; it != container.end() ; ++it)
 19 
 20 //Definicion de un par de la stl
 21 typedef pair<int, int> pii;
 22 
 23 //Constantes del programa
 24 const int MAXN = 10002;
 25 const int MAXM = 502;
 26 const int MAXMEM = 2*MAXN;
 27 
 28 //Clase para definir los hijos del arbol
 29 //Es una lista con todos los hijos de cada nodo
 30 class Graph {
 31     public :
 32     void addNode(int node, int value) {
 33         nodes[node].push_back(value);
 34     }
 35     list<int> nodes[MAXN];
 36 };
 37 
 38 //Clase para cola de las busquedas en amplitud
 39 //Es de tipo generica
 40 template<class T>
 41 class Queue {
 42     public :
 43     Queue() { init(); }
 44     void init() { p1 = 0; p2 = 1; }
 45     void push(T val) { memory[++p1] = val; }
 46     T front() { return memory[p2]; }
 47     void pop() { p2++; }
 48     bool empty() { return (p1 < p2); }
 49 
 50     private :
 51     int p1, p2;
 52     T memory[MAXMEM];
 53 };
 54 
 55 //Definicion de todas las variables del programa
 56 int N, M, C, //Variables dadas
 57     allowedColorsSize[MAXN], //La cantidad de colores posibles por nodo
 58     parents[MAXN], //El padre de cada nodo
 59     colorAssigned[MAXN]; //El color que le asigne al final al nodo
 60 bool allowedColors[MAXN][MAXM]; //Una matriz con todos los colores posibles por cada nodo
 61 list<int> nodesOrder; //Una lista ordenada de mayor a menor por la profundidad de cada nodo
 62 Graph tree; //Mi arbol
 63 Queue<pii> searchDepth; //Una cola para la busqueda
 64 
 65 //Regresa el color valido por cada nodo permitiendo que un nodo no sea de un color
 66 int validColor(int node, int constraint = -1) {
 67     for(int i = 0; i < M; ++i) {
 68         if(allowedColors[node][i] && constraint != i) {
 69             return i;
 70         }
 71     }
 72     return -1;
 73 }
 74 
 75 //Funcion para la lectura de todas las variables y la inicializacion de las estructuras
 76 //Los asserts son para probar que el codigo es correcto
 77 /*Guarda en allowedColors los posibles colores por nodo en una matriz*/
 78 void read() {
 79     int node, prohibited;
 80     scanf("%d%d", &N, &M);
 81     assert(1 <= N && N <= MAXN-2);
 82     allowedColorsSize[0] = M;
 83     memset(allowedColors, true, sizeof(allowedColors));
 84     for(int k = 1; k < N; ++k) {
 85         scanf("%d", &node);
 86         assert(0 <= node && node < N);
 87         parents[k] = node;
 88         tree.addNode(node, k);
 89         allowedColorsSize[k] = M;
 90     }
 91     scanf("%d", &C);
 92     for(int k = 0; k < C; ++k) {
 93         scanf("%d%d", &node, &prohibited);
 94         assert(0 <= node && node < N && 0 <= prohibited && prohibited < M);
 95         if(allowedColors[node][prohibited]) { //Checa que los nodos no se repitan ya que se pueden repetir
 96             allowedColors[node][prohibited] = false;
 97             allowedColorsSize[node] --;
 98         }
 99     }
100 }
101 
102 /*Una busqueda en amplitud para "linearizar el árbol"*/
103 void orderNodes() {
104     searchDepth.push(make_pair(0, 0));
105     while(!searchDepth.empty()) {
106         pii value = searchDepth.front(); searchDepth.pop();
107         nodesOrder.push_front(value.first);
108         TR(tree.nodes[value.first], it) {
109             searchDepth.push(make_pair(*it, value.second + 1));
110         }
111     }
112 }
113 
114 /*Checa por cada nodo de mayor a menor en la linearizacion, los colores posibles por nodo que solo tiene un color posible*/
115 void enforceArc() {
116     TR(nodesOrder, it) {
117         int currNode = *it;
118         int parent = parents[*it];
119         if(currNode != 0) {
120             if(allowedColorsSize[currNode] == 1 || allowedColorsSize[parent] == 1) {
121                 if(allowedColorsSize[parent] == 1) {
122                     swap(currNode, parent);
123                 }
124                 int color = validColor(currNode);
125                 //printf("%d %d %d\n", currNode, parent, color);
126                 if(allowedColors[parent][color]) {
127                     allowedColors[parent][color] = false;
128                     allowedColorsSize[parent] --;
129                 }
130             }
131         }
132         //Si no hay colores posibles, no se puede resolver el mapa
133         if(allowedColorsSize[currNode] <= 0) {
134             printf("-1\n");
135             exit(0);
136         }
137     }
138     //Checa de nuevo si alguno de los colores no puede ser
139     for(int k = 0; k < N; ++k) {
140         if(allowedColorsSize[k] == 0) {
141             printf("-1\n");
142             exit(0);
143         }
144     }
145 }
146 
147 //Hace un ciclo checando el menor color posible por nodo e imprime los colores menores
148 void findSolution() {
149     colorAssigned[0] = -1;
150     list<int>::iterator it = nodesOrder.end();
151     do {
152         it --;
153         assert(0 <= *it && *it < N);
154         int color = validColor(*it);
155         if(colorAssigned[parents[*it]] == color) {
156             color = validColor(*it, color);
157         }
158         assert(0 <= color && color < M);
159         colorAssigned[*it] = color;
160     } while(it != nodesOrder.begin()) ;
161 
162    for(int k = 0; k < N; ++k) {
163        printf("%d\n", colorAssigned[k]);
164    }
165 }
166 
167 int main() {
168     read();
169     orderNodes();
170     enforceArc();
171     findSolution();
172     return 0;
173 }

Solución a “Metro”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12
Autor: Alain Acevedo Mejía

El problema en cuestión se reduce a encontrar un árbol de expansión mínima. La solución es una aplicación directa de alguno de los algoritmos existentes para ello (bien implementada), por lo que hablaré brevemente sobre una de las posibilidades y daré referencias donde puedan encontrar información más detallada.

Para encontrar el costo mínimo de unir todas las estaciones debemos encontrar el árbol de expansión mínima de la gráfica en cuestión (es decir, una subgráfica conexa que una todos los vértices de la gráfica original y cuyo peso (la suma de los costos de todas sus aristas) sea el mínimo posible (siempre es un árbol)). Para ello una opción es usar el algoritmo de Kruskal: Ordenamos las aristas por su peso y vamos agregando cada arista de peso mínimo que no cree un ciclo en la gráfica. Hacemos esto hasta haber conectado todos los vértices de nuestra gráfica. Por la cantidad de aristas que tenemos requerimos ordenar eficientemente y verificar si las aristas forman un ciclo o no eficientemente en cada paso, de lo contrario el programa no correrá en tiempo.

Para verificar si se forma o no un ciclo agregando una determinada arista empleamos el algoritmo conocido como Union Find, que se explica ampliamente en las secciones 16.7, 16.8 y 16.9 del libro Problemas y Algoritmos de Luis E. Vargas Azcona. Es importante mencionar que para obtener los 100 puntos en el problema es necesario implementar las optimizaciones que se mencionan (y aunque no fuera así no está de más que las conozcan).

Además del libro de Luis E. Vargas, que recomiendo ampliamente, sugiero la página de Pier Guillen http://pier.guillen.com.mx/ , que en ->Algorithms ->10. Gráficas ->10.6 Árboles Mínimos Generadores desarrolla el tema en cuestión. Y claro, no está de más que consulten el tema en el libro Introduction to Algorithms de Thomas H. Cormen, que en la tercera edición trabaja el tema en el capítulo VI. Graph Algorithms ->23 Minimum Spanning Trees.

El siguiente código resuelve el problema:

Solución a “Pulseras”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10
Autor: Alain Acevedo Mejía

Considero este problema como un buen ejemplo para quienes desean comenzar a trabajar con problemas de programación dinámica. Se nos pide calcular la cantidad de pulseras diferentes que se pueden construir bajo ciertas condiciones. Podemos comenzar preguntándonos, ¿qué sucede si la primera cuenta es negra? La siguiente podrá ser sólo blanca. Y si comenzamos con una blanca, la siguiente puede ser negra o blanca. Podemos entonces en una matriz de 2xn colocar en cada columna cuántas secuencias distintas hay que en la posición i-ésima terminen en negro y cuántas en blanco de tal modo que no haya dos cuentas negras consecutivas. Simplemente, para obtener los números de la siguiente posición, observamos que el número de las que terminan en blanco es la suma de ambos números de la posición anterior y de las que terminan en negro es el número de secuencias que terminan en blanco de la posición anterior.

Resta solo un detalle más a considerar. Requerimos que la secuencia no inicie y termine en negro, pues los extremos quedarán adyacentes al cerrar la pulsera. Una forma de resolver esto es la siguiente: Contamos, con el método descrito, cuántas secuencias distintas hay que inicien con blanco y que no tengan dos cuentas negras consecutivas. El número que nos pide el problema será entonces la cantidad de pulseras que empiezan con blanco y cumplen con que no haya dos negras consecutivas (independientemente de con qué color terminen) más el número de pulseras que inicien con negro y terminen con blanco (y claro, cumplan con que no haya dos negras consecutivas). ¿Cuántas hay de estas últimas? La misma cantidad que de pulseras que inician con blanco y terminan con negro, pues su simétrica inicia con negro, termina con blanco y claramente sigue cumpliendo el que no posea dos cuentas negras consecutivas. Así que es posible resolver el problema con un código muy breve, como se muestra abajo.

Solo resta mencionar que hay que tener cuidado de aplicar el módulo correctamente. Se pueden evitar errores definiendo el valor del mismo para no tener que escribir el número varias veces.

El siguiente código resuelve el problema:

Solución a “Los Bloques de Link”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 8
Autor: Alain Acevedo Mejía

Es claro que no es posible probar todas las sucesiones posibles de movimientos de los bloques para encontrar la solución (a excepción de casos muy simples). El número de tales sucesiones puede ser infinito en caso de que se puedan formar ciclos de movimientos (lo cual sucede en muchos de lo casos de prueba), y aún en casos donde el número sea finito puede suceder que no se tenga tiempo para probarlos todos.

Una primera observación crucial es que, en el estado del mapa, solo nos interesa saber donde están los bloques de hielo en cada paso, es decir, su ubicación es lo que determina lo que nos interesa del estado. No nos interesan los pasos previos que los llevaron a su posición, solo que sea el número mínimo posible. Tenemos un problema que puede ser resuelto realizando una búsqueda en amplitud.

¿Cuántos estados es posible alcanzar? El mapa es a lo más de 40×40 espacios y las orillas siempre están bloqueadas, así que realmente tenemos 38×38=1444 espacios a los que quizá es posible llevar a los bloques. Tenemos dos bloques de hielo, así que hay (1444×1443)/2=1,041,846 formas de colocarlos en el mapa (hemos considerado aquí ya el hecho de que son indistinguibles). Para fines de la búsqueda el número que hemos calculado es en realidad una cota superior muy mala (mala en el sentido de que la cota superior mínima es muy inferior, es decir, calculamos “de más”), pues por la forma en que se mueven los bloques es claro que aún en el peor de los casos posibles la cantidad de estados a los que se puede acceder es mucho menor (¿cuál es el peor de los casos?). Es posible entonces emplear una búsqueda en amplitud común para resolver el problema, el espacio de búsqueda no es muy grande y es claro que podemos recorrerlo por completo.

Para representar los estados requerimos tener la posición de ambos bloques, y nada más. Podemos emplear una arreglo de bool’s (boolean’s en pascal) de cuatro dimensiones para marcar los estados a los que se ha accedido. Para la cola, en el código que se anexa más abajo, empleamos un arreglo de dos dimensiones (una matriz) donde además de guardar la posición de los bloques de los estados guardamos la cantidad de movimientos realizados para llegar a cada estado. Para ver a que estados podemos llegar desde un estado dado basta con ver en que direcciones es posible mover los bloques y a qué posición llegarán.

Para optimizar la búsqueda podemos hacer dos observaciones. La primera es que con nuestra representación de los estados podríamos llegar dos veces al mismo estado, ya que los dos bloques de hielo son para nuestros fines iguales. En el código de abajo es por ello que al llegar a un estado nuevo se marcan dos valores en el arreglo de bools como verdaderos, pues ambos representan en realidad el mismo estado.

Otra observación es que para averiguar eficientemente a que estados se puede llegar desde un estado dado podemos precalcular, antes de realizar la búsqueda, para cada espacio vacío o con bloque de hielo, cuál es la posición del espacio bloqueado (con numeral # o con el botón A) más cercano en cada dirección. Así solo habrá que comparar esa posición con la del otro bloque de hielo para ver a dónde llegará el bloque tras su movimiento. Esto puede mejorar el tiempo de ejecución para un caso dado, aunque no siempre es así. En este problema para obtener los 100 puntos no hacen falta optimizaciones de este tipo, aunque es bueno tener este tipo de ideas en mente para problemas más complejos.

El siguiente código resuelve el problema:

Solución a “Problema”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10
Autor: Hugo Dueñas

Primero, dado una secuencia $latex A$ denotaremos por $latex s(A)$ a la suma de los elementos de A. Entonces podemos replantear el problema como: Dada una secuencia $latex S$ debemos de econtrar una subsecuencia $latex A$ de $latex S$ tal que $latex s(A) – (s(S) – s(A))$ sea la minima posible.

Ahora, como $latex s(A) – (s(S) – s(A)) = 2 \times s(A) – s(S)$, entonces tenemos que minimizar $latex 2 \times s(A) – s(S)$ que es lo mismo que minimizar $latex s(A) – s(S)/2$. O sea, debemos de encontrar una subsecuencia $latex A$ cuya suma esté lo más cercana a la mitad de la suma de $latex S$, en particular podemos restringir nuestra búsqueda a las subsecuencias cuya suma sea menor o igual a $latex s(S)/2$.

Se plantea para este problema una solución de tipo Programación Dinámcia que corre sobre los elementos de la secuencia $latex S$ y considera todas las posibles diferentes sumas de subsecuencias cuyos elementos tienen índices menores o iguales al actual y cuya suma no excede $latex s(S)/2$. Se tendrán entonces $latex n \times s(S)/2$ posibles estados y cada uno podrá ser procesado en tiempo constante ya que solo hay dos trancisiones posibles para cada estado: Se toma el elemento actual dentro de la subsecuencia o no. Por lo tanto la solución tendrá una complejidad temporal de $latex O (n \times s(S))$.

A continación se lista una implementación en C++ de la solución:

Solución a “Alfiles”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 7
Autor: Hugo Dueñas

Lo primero que se debe de notar es que en cada una de las $latex 2n-1$ diagonales principales, las cuales mostradas en la imagen de abajo, habrá máximo 1 alfil. Lo mismo se cumple para las diagonales invertidas, mostradas también en una imagen abajo.

Ahora, cada diagonal principal se cruza con ciertas diagonales invertidas. Entonces se plantea una solución de tipo Backtracking que corre sobre las diagonales principales marcando diagonales invertidas a cada paso (representando que se ha colocado un alfil en el cruce de esas dos diagonales).

Una implementación directa y sin optimizaciones ni podas para los casas donde $latex n = 8$ hará uso de $latex 1\times2\times3\times4\times5\times6\times7\times8\times7\times6\times5\times4\times3\times2\times1=203212800$ operaciones, lo cual no está muy lejos de ser una solución eficiente. Entonces bastan algunas podas para obtener una solución al 100%, podemos por ejemplo podar las ramas de la recursión que consideran combinaciones con una diagonal invertida repetida.

A continación se lista una implementación en C++ de la solución:

Solución a “Mario Reloaded”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 8
Autor: Pavel Herrera Dominguez

Observaciones

Lo primero es ver como se modelan los estados del problema sin pensar en que Mario puede tomar los atajos, únicamente pensar en las llaves, claramente existen $latex n\times2^m$ estados, pues no importa el orden en que se toman las llaves solo las llaves que se tienen al llegar a cada puerta. A partir de aquí nos referiremos como estado a la puerta y las llaves que trae Mario.

La segunda observación es ver como afecta llegar a una puerta con cierto juego de llaves, osea a cada estado. Cada vez que visitamos un estado todos los estados ya visitados que tienen el mismo juego de llaves se actualiza instantáneamente. Esto se puede entender como si únicamente el juego de llaves definiera el estado, lo que nos lleva a pensar que el problema es saber que puertas pertenecen a qué juego de llaves.

De la observación anterior podemos pensar que si mantenemos una lista de puertas ya visitadas para cada juego de llaves, cuando algún estado (puerta, juego de llaves) se visita con un menor tiempo, todas las puertas alcanzadas con ese juego de llaves deben ser actualizadas y sus respectivos vecinos.

Idea

La idea es hacer una especie de búsqueda en amplitud la cual tome en cuenta las observaciones anteriores. Esto es una búsqueda que visite los estados (puerta, llave) y conserve una lista de las puertas alcanzables con cada juego de llaves.

Implementacion

Tarea

Pensar si es posible hacer la búsqueda sin usar los estados (puerta, juego de llaves).

Solución a “El collar de perlas”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 10 
Autor: 
Félix Rafael Horta Cuadrilla

En una bosque habitan dos clanes de enanos: los enanos rojos y los enanos verdes. Durante sus expediciones en las cuevas cercanas, un grupo de enanos rojos y verdes encontraron un collar formado por perlas blancas y negras que no tienen ningun valor, pero al final del collar hay un valioso diamante. Los dos clanes de enanos quieren apoderarse del diamante.

Para resolver el problema de manera pacifica deciden jugar el siguiente juego: a cada uno de los N enanos se le asigna un numero del 1 al N (un numero diferente para cada enano) y dos listas de numeros, una negra y una blanca (las listas pueden ser diferentes entre si). Cada lista contiene una cantidad diferente de numeros, cada numero i en cualquier lista representa al enano i.

Durante el juego, el collar se pasa de un enano a otro de acuerdo con las siguientes reglas: cuando un enano recibe el collar, el quita la primer perla en el collar y si la perla es blanca, entonces pasa lo que quedo del collar a cualquier enano que este en su lista blanca (al que el quiera), pero si la piedra es negra, entonces pasa lo que quedo del collar a algun enano de su lista negra. Para empezar el juego, el collar se le da a un enano aleatoriamente.

En algun momento el collar solamente va a tener el diamante, el enano que recibe el collar en este estado gana el diamante para su clan y el juego termina.

Continue reading “Solución a “El collar de perlas””