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

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 1
Autor: Ethan Jimenez

Empecemos analizando el caso en que solo jugamos con un montón de fichas, dada la restricción de tomar únicamente una sola ficha el juego se vuelve predecible ya que no hay más opción que tomar una ficha de ese montón. Si el montón tiene una sola ficha el jugador con el primer turno pierde, si hay dos fichas el jugador con el primer turno gana, si hay tres fichas el jugador con el primer turno pierde, y así alternadamente, podemos entonces deducir que si hay un número impar de fichas en el montón, el jugador con el primer turno perderá, por el otro lado, si el montón tiene un número par de fichas ganará la partida.

La pregunta clave para este problema es, ¿realmente hay diferencia entre tomar una ficha de un montón y tomar una ficha de otro montón? Aumentemos la cantidad de montones en el juego, digamos que ahora tenemos dos montones de fichas, ambos montones tienen una sola ficha, el jugador con el primer turno ganará, detente por un momento a experimentar qué sucede si aumentamos la cantidad de fichas en un montón, en el otro y en ambos montones, teniendo en mente la pregunta anterior.

Después de probar con diferentes configuraciones de juego podemos decir que la respuesta a la pregunta es no, tomar primero una ficha de un montón no es diferente a haberla tomado de cualquier otro montón, con lo que podemos concluir que, si tenemos dos montones, el primero con a1 fichas y el segundo con a2 fichas, este juego es equivalente a tener un solo montón con a1+a2 fichas, una vez establecido podemos volver a nuestro análisis inicial y calcular quién ganará.

De manera análoga deducimos que si tenemos N montones de fichas y elegimos K de ellos, podemos reducir la configuración herpes transmission de esta partida a un juego con solo un montón de k1+k2+…+kN fichas, donde ki es el número de fichas en el montón elegido i. Una vez que sabemos lo anterior debemos darnos cuenta que para ganar tenemos que elegir K de los N montones cuya suma total sea un número impar.

Para asegurarnos que un conjunto de montones tiene un número impar de fichas debemos considerar lo siguiente, un número impar más un par da un número impar, un número impar sumado a un impar da un número par y un número par más un par da otro número par. Dado lo anterior podemos definir una regla para tener una suma total impar, debe existir una cantidad impar de montones con un número de fichas impar, si le agregamos cualquier cantidad montones con número de fichas par no se modifica la condición de tener un total impar.

En conclusión, es posible ganar el juego cuando existe más de un montón con número impar de fichas, si hay una cantidad impar de montones impares ya se cumple la condición deseada, pero si hay una cantidad par de montones impares debemos quitar uno para cumplirla, para obtener el juego con la mayor cantidad de fichas el montón que quitemos debe ser el que tenga menos fichas, nota que, como mencioné antes, agregar montones pares no afecta la condición de victoria, por lo que para aumentar la cantidad de fichas en el juego se deben agregar todos ellos.