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 “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 “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””