Solución a “Cueva”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 4
Autor: Ethan Jiménez Vargas

Después de comprender el problema podemos deducir dos cosas:

  • Los N puntos de la cueva modelan un árbol, esto debido a la propiedad de que existirán N-1 aristas y siempre hay un camino entre cualquier par de nodos.
  • Podemos traducir la tarea principal del problema a lo siguiente “Para cada una de las Q preguntas, ¿el nodo A es un ancestro del nodo B?”, de modo que necesitamos encontrar una manera óptima de saberlo.

Subtarea 1. Para obtener los primeros 25 puntos del problema solo necesitamos implementar el método de fuerza bruta que nos permita conocer si A es ancestro de B, esto puede conseguirse con una búsqueda en profundidad (DFS) que desde el nodo A encuentre la manera de llegar al nodo 1, restringiendo que no sea posible pasar por el nodo B, si existe un camino del nodo A al nodo raíz la respuesta es 1, en caso contrario la respuesta es 0. Hay que cuidar los casos especiales cuando el nodo B es el nodo raíz o cuando el nodo A es el mismo nodo B, en ambos casos la respuesta es 0.

Complejidad de la solución: O(NQ)

Subtarea 2. Es notable que esta vez el número de preguntas es mucho mayor, por ello la solución anterior tardaría demasiado. Cambiemos nuestra estrategia, esta vez realicemos una búsqueda en profundidad desde el nodo 1 hasta los demás N nodos, llevando una lista L de los nodos que forman parte del camino desde el nodo 1 hasta el nodo K, incluyendo los nodos 1 y K, esto puede lograrse mediante recursividad.

La tabla ancestro[K][M] nos permitirá saber si el nodo M es un ancestro del nodo K, dándonos cuenta que todos los ancestros de K se encuentran en la lista L cuando la búsqueda en profundidad llega al nodo K, podemos llenar la tabla ancestro[K][M] durante la búsqueda en profundidad. Con la tabla anterior es fácil responder las preguntas, pues la respuesta depende de ancestro[B][A].

Complejidad de la solución: O(N2+Q)

Subtarea 3. Para obtener los puntos de esta subtarea podemos utilizar cualquier algoritmo para resolver el clásico problema del ancestro común de dos nodos en un árbol, puesto que la respuesta es 1 si el ancestro común entre los nodos A y B es el nodo A. Este problema ya ha sido estudiado ampliamente y tiene diversas formas de ser resuelto con complejidad O(NlogN), en el foro de tutoriales de TopCoder podemos encontrar un buen artículo con algunos de los algoritmos que pueden ser utilizados:

TopCoder Lowest Common Ancestor

El algoritmo que utiliza programación dinámica es el más recomendado, puesto que se puede responder a las Q preguntas en un tiempo constante.

Complejidad de la solución: O(NlogN+Q)

Subtarea 4. Para empezar, notemos que la solución anterior no funciona para este conjunto de puntos porque utiliza demasiada memoria, el simple hecho de almacenar los nodos y las aristas ocupa bastante espacio en memoria (aproximadamente 100Mb) y una solución para la subtarea 3 requeriría al menos 50Mb más, por lo tanto no es posible completar la subtarea 4 con una solución como la anterior, para obtener los 100 puntos en este problema necesitamos una idea mucho más creativa.

Renombremos todos los nodos del árbol enumerandolos del 1 al N siguiendo el orden establecido por el recorrido en postorden del árbol comenzando por el nodo 1, después, para cada nodo, con su respectivo número Y, hay que obtener el menor número presente en el subárbol con raíz en el nodo Y, denotemos este número menor como X, con los números X y Y definimos entonces un intervalo cerrado [X,Y] que nos representa que en el subárbol con raíz en el nodo Y se contienen todos los nodos cuyo número se encuentra en el intervalo [X,Y]. Podemos interpretar esta información de una manera más conveniente, un nodo con número Y es ancestro de un nodo con número K si X ≤ K ≤ Y, lo cual nos permitirá responder las preguntas planteadas.

Es recomendable que el olímpico experimente y se convenza que la propiedad del intervalo [X,Y] es siempre correcta debido a que el recorrido en postorden establecerá que el nodo con el número X, que establece la cota inferior del intervalo, siempre será una hoja del subárbol y el nodo con valor Y, que establece la cota superior del intervalo, siempre será la raíz del subárbol, cualquier otro valor fuera del intervalo estará excluido del subárbol con raíz en el nodo Y.

Complejidad de la solución: O(N+Q)

Solución a “Chilly Rapero”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12
Autor: Ethan Jiménez Vargas

La clave para resolver este problema es interpretar las palabras como nodos y los cambios entre palabras como aristas, de manera que podamos verlo todo como un grafo no dirigido. Asignamos a cada palabra un nodo y creamos las aristas entre nodos verificando alguna de las condiciones que se proponen en el enunciado del problema: si una palabra A es un prefijo o sufijo de la palabra B o la palabra A difiere con la palabra B por un solo caracter, establecemos una arista entre los nodos A y B.

Crear las aristas entre los nodos tiene una complejidad de O(LN2) y la manera más simple de almacenar dichas aristas es mediante una matriz de adyacencia. Ya que tenemos el grafo planteado, buscaremos la manera más rápida de cambiar de palabra entre cualquier par de palabras, esto puede conseguirse usando el algoritmo de Floyd-Warshall con una complejidad de O(N3) que es suficiente para el problema.

Finalmente, para obtener la respuesta sumamos el mínimo número de cambios requeridos entre todos los pares de palabras consecutivas en el rap, este número de cambios fue obtenido mediante el algoritmo de Floyd-Warshall. El número total de cambios lo multiplicamos por 0.2 y será la respuesta para el problema.

Complejidad de la solución: O(LN2+N3)

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 A denotaremos por s(A) a la suma de los elementos de A. Entonces podemos replantear el problema como: Dada una secuencia S debemos de econtrar una subsecuencia A de S tal que s(A) - (s(S) - s(A)) sea la minima posible.

Ahora, como s(A) - (s(S) - s(A)) = 2 \times s(A) - s(S), entonces tenemos que minimizar 2 \times s(A) - s(S) que es lo mismo que minimizar s(A) - s(S)/2. O sea, debemos de encontrar una subsecuencia A cuya suma esté lo más cercana a la mitad de la suma de S, en particular podemos restringir nuestra búsqueda a las subsecuencias cuya suma sea menor o igual a 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 S y considera todas las posibles diferentes sumas de subsecuencias cuyos elementos tienen índices menores o iguales al actual y cuya suma no excede s(S)/2. Se tendrán entonces 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 O (n \times s(S)).

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