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 , 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 cuenta de cuántas maneras se pueden poner
torres de tal manera de que sólo
se pueden ver de un lado, la respuesta que queremos es
.
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 . Es decir, hay
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 , podemos reusar la misma observación. Cuando colocamos la torre más alta en el índice
, cualquier torre que pongamos después de
ya no se podrá ver. Del lado visible, necesitamos reordenar las torres restantes de tal manera que sólo se puedan ver
. Además, podemos reordenar el lado oculto de la manera que queramos. Con esto tenemos que
con lo que resolvemos el problema en tiempo y memoria
.
Esto se puede mejorar aún más observando que está computando los números de Stirling de primera clase, para los cuales hay una recurrencia que se puede utilizar para calcularlos en tiempo
.
Los números de Stirling de primera clase cuentan las permutaciones de elementos con
ciclos. Considere una permutación con
ciclos de los
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
edificios visibles. Ya que estamos contando todas las permutaciones con
ciclos, cada posible ordenamiento con
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.