Solución alternativa a “Decepción”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 8
Autor: Freddy Román Cepeda
Fuente: Ethan Jiménez Vargas

Esta es una solución alternativa al problema. La solución pensada originalmente consiste en una búsqueda podada. Sin embargo, esta solución corre en tiempo y memoria O(N^2), mucho mejor de lo necesario para obtener todos los puntos.

Podemos dividir el problema a la mitad con una observación simple: la torre más alta debe verse desde ambos lados. Además, no dejará que el resto de las torres que ocurren después de ella se vean. Podemos aprovechar este hecho para separar el problema en dos partes: izquierda y derecha. Si f(n,m) cuenta de cuántas maneras se pueden poner n torres de tal manera de que sólo m se pueden ver de un lado, la respuesta que queremos es \sum_{i=0}^{N-1} ({N-1 \choose i} * f(i,F-1) * f(N-i-1,B-1)).

En otras palabras, esta expresión es la suma de las maneras de cumplir las condiciones originales del problema colocando la torre más alta en la posición i. Es decir, hay {N-1 \choose i} maneras de distribuir el resto de las torres a la izquierda o derecha de la torre más alta (porque la única cosa que importa es el orden relativo de las torres y todas las alturas son distintas), las cuales multiplicamos por las maneras de hacer que se cumpla la condición sobre el lado izquierdo y lo mismo con el lado derecho.

Ahora, para computar f, podemos reusar la misma observación. Cuando colocamos la torre más alta en el índice i, cualquier torre que pongamos después de i ya no se podrá ver. Del lado visible, necesitamos reordenar las torres restantes de tal manera que sólo se puedan ver m-1. Además, podemos reordenar el lado oculto de la manera que queramos. Con esto tenemos que

f(0,0) = 1
f(n,m) = \begin{cases}  0 & \text{si } m > n\\  \sum_{i=0}^{n-1}({n-1 \choose i} * f(i,m-1) * (n-i-1)!) & \text{de lo contrario}    \end{cases}

con lo que resolvemos el problema en tiempo O(N^3) y memoria O(N^2).

Esto se puede mejorar aún más observando que f(n,m) está computando los números de Stirling de primera clase, para los cuales hay una recurrencia que se puede utilizar para calcularlos en tiempo O(N^2).

Los números de Stirling de primera clase cuentan las permutaciones de n elementos con m ciclos. Considere una permutación con m ciclos de los n edificios. Cada ciclo debe tener un elemento máximo. Además podemos ordenar los ciclos entre sí por su elemento mayor. De esta manera, tenemos m edificios visibles. Ya que estamos contando todas las permutaciones con m ciclos, cada posible ordenamiento con m edificios visibles será considerada. Esto se debe a que cada ciclo tiene únicamente un ordenamiento en el cual sólo uno de sus elementos es visible: el que comienza con el edificio más grande.

Aquí está el código que implementa esta solución.

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 “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 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).