Solución a “Los Callejones de Guanajuato”

Problema: Los Callejones de Guanajuato.

En este problema se nos está pidiendo que, dado un grafo conexo no dirigido, encontrar un camino tal que pasemos por todas las aristas.

Esta es una aplicación directa de un problema conocido de grafos, aunque no es tan común como otros problemas, estoy hablando de los ciclos Eulerianos.

Continue reading

Solución a “Splatoon”

Problema: Splatoon.

Este problema pide llevar a un inkling desde el inicio de una calle hasta el final siguiendo sus reglas de movimiento.

Ignoremos por un momento el hecho de que los inklings pueden pintar el piso y con ello alterar la calle en donde se realiza la carrera. Si los inklings no tuvieran esta habilidad, se puede hacer un algoritmo de fuerza bruta intentando todas las operaciones posibles, es decir, hacer una búsqueda en amplitud para encontrar el camino más corto, en donde el estado está representado únicamente por la posición en donde se encuentre el inkling.

Recuerda que en las búsquedas es importante marcar visitados para que la complejidad del algoritmo no se vuelva exponencial.

Para cada posición, se tienen dos posibles operaciones, saltar, o caminar, ambas toman 1 segundo y la distancia a la que se llega depende directamente del color sobre el que se está parado. El movimiento de saltar es muy fácil pues solo hay una casilla donde se puede caer, pero el movimiento de avanzar difiere cada vez pues depende directamente del color de las siguientes casillas.

Es posible hacer un ciclo para ver hasta donde puedes llegar avanzando desde la casilla en donde estás, y agregar a la búsqueda el lugar más lejano a donde puedas llegar. Sin embargo, si únicamente registramos la última casilla a donde se puede llegar, casos como el siguiente se nos escaparán:

En la solución superior, primero se avanza todo lo que se puede en la pintura naranja hasta llegar a la casilla azul, de ahi ya sea saltando o avanzando únicamente se puede llegar a la casilla blanca, y de ahí, no importa lo que hagas, te tomará dos segundos llegar al final.

En cambio, en la solución inferior, se avanza solo 3 casillas en la pintura naranja, lo cual es 1 casilla menos del máximo, de ahí se hace un salto el cual nos deja de nuevo en pintura naranja, desde donde podemos llegar caminando hasta el final en un total de tan solo 3 segundos, 1 segundo menos que la solución anterior.

Por lo tanto, no es suficiente visitar la distancia máxima, también hace falta visitar la distancia máxima – 1. Si intentamos hacer cosas similares con otro color de pintura, o más deteniéndonos todavía más atrás del máximo, no hay realmente ninguna ventaja, por lo que el caso presentado anteriormente es el único caso especial.

Una búsqueda en amplitud bien hecha que considere este caso sacará 30 puntos, una que no considere este caso sacará únicamente 5 puntos. Da perfectamente en tiempo y memoria porque a lo más tendremos un total de 1000 estados.
Sin embargo, la parte interesante de este problema es que los inklings son capaces de alterar el estado de la calle usando la pintura que traen en su tanque para poder recorrer más rápido la calle, utilizando hasta D disparos de tinta.

En este caso, necesitamos agregar una segunda dimensión al estado de nuestra búsqueda, ahora no sólamente es suficiente con guardar el lugar en donde estamos, sino que es necesario guardar también cuanta tinta queda en el tanque. En este caso, agregamos una operación más, la cual es pintar, la cual cuesta 0 segundos, nos avanza 0 casillas y nos quita una unidad D de pintura.

Si hacemos esto, nuestro espacio de búsqueda crece del N que era en la solución de 30 puntos, a N x D, lo cual es 1000 x 1000 y aún da en tiempo y memoria.

No obstante, la operación de pintar altera el mapa, por lo que si no guardamos también en el estado que las casillas siguientes ahora son de otro color, pintar no servirá de nada. Podríamos agregar una dimensión más a la búsqueda para considerar este caso, pero esto solo le agregaría complejidad innecesaria a la búsqueda.

La clave está en que pintar toma 0 segundos, por lo que podemos convertir la operación de pintar en una operación compuesta, que sea pintar y avanzar.

Pintar y avanzar toma 1 segundo, y nos permite avanzar 4 casillas hacia adelante siempre, por lo que hacer una operación de pintar y avanzar nos lleva del estado (i, d) al estado (i + 4, d – 1) con un costo de 1 segundo.

El detalle con esta solución, es que estamos ignorando de nuevo el caso especial explicado en la solución de 30 puntos, por lo que si se nos olvida que es posible ahorrarnos un segundo en ciertas ocasiones, sacaremos entre 35 y 90 puntos dependiendo de la implementación.

Para sacar los 100 puntos, es necesario agregar una operación más, la cual es pintar, avanzar y saltar, la cual nos lleva del estado (i, d),  al estado (i + 6, d – 1) con un costo de 2 segundos. Y como esta operación toma 2 segundos en vez de tan solo 1, no es suficiente con utilizar una cola común y corriente para hacer la búsqueda en amplitud, sino que es necesario utilizar una estructura de datos más avanzada, como una cola de prioridad o un montículo que nos ayude a ordenar los estados y elegir siempre con el tiempo más pequeño.

 

Solución a “Los Chocolates del Agente Nieves”

Problema: Los Chocolates del Agente Nieves

En este problema tenemos un tubo de chocolates los cuales se van a vender uno cada día, pudiendo vender únicamente los que están en ese momento en los extremos. El precio por vender un chocolate es igual al precio base de chocolate multiplicado por el número de días que se han vendido chocolates (empezando en 1).

El objetivo es encontrar la mayor ganancia posible al vender todos los chocolates.

 

Si lo quisiéramos resolver como una búsqueda, ¿qué tendríamos que considerar? En una búsqueda, nos importa obtener dos cosas, el espacio de búsqueda (es decir, cómo estará representado nuestro estado y qué valores puede tener), y las operaciones en nuestra búsqueda.

En cuanto a nuestros estados en la búsqueda, nos importa saber qué chocolates aún tenemos disponibles y cuántos días han pasado. Podríamos empezar teniendo N valores booleanos por cada chocolate y un número para saber cuántos días han pasado, por ejemplo, si tenemos 3 chocolates y aún no vendemos nada, tendríamos el estado (1, 1, 1, 1), si ya vendimos el primer chocolate, tendríamos (0, 1, 1, 2), si vendimos el tercer chocolate tendríamos (1, 1, 0, 2) y si vendemos los chocolates 1 y 2, tendríamos (0, 0, 1, 3). Sin embargo, esta representación es un poco inútil, ya que en el peor de los casos, tendríamos 1000 chocolates, lo cual hace un estado de 1000 posibles valores.

Podemos mejorar esto solo guardando únicamente los índices a los extremos del tubo, ya que ya sabemos que aún tenemos todos los chocolates entre estos dos valores. Eso transforma los estados anteriores a los siguientes estados respectivamente: (1, 3, 1), (2, 3, 2), (1, 2, 2). y (3, 3, 3). Esto vuelve al estado muchísimo más manejable, pues cada valor puede valer únicamente entre 1 y 1000.

Ya que tenemos nuestro estado, definimos las operaciones que hay que hacer para ir entre estado y estado, y estas operaciones son únicamente 2, vender el chocolate de la izquierda, o vender el chocolate de la derecha, si estamos en el estado (1, 3, 1) y vendemos el de la izquierda, nos lleva al estado (2, 3, 2), y si vendemos el de la derecha, nos lleva al estado (1, 2, 2). Podemos continuar estas instrucciones recursivamente sobre los estados que resulta y generar un árbol de búsqueda:

Una vez teniendo el árbol de búsqueda, podemos proceder a darle valor a cada uno de los nodos. Del nodo inicial (1, 3, 1), si decides vender el chocolate de la izquierda, obtendrás una ganancia igual a lo que te de el nodo (2, 3, 2) más el precio del chocolate 1 multiplicado por el número de días, que en este caso es 1, y si decides vender el chocolate de la derecha, la ganancia será lo que de el nodo (1, 2, 2) más el precio del chocolate 3 (múltiplicado por 1). De las dos opciones, tomaremos el máximo.

Llenemos ahora el resto del árbol de búsqueda con estos datos:

De aquí podemos ver dos cosas, la primera es que los nodos de hasta abajo, que son nuestros nodos hoja, tienen el mismo valor en el chocolate izquierdo como en el derecho, por lo que el valor máximo que podemos obtener de ellos es el precio de ese único chocolate por el número de días que llevamos. Y la segunda cosa es que tenemos nodos repetidos, por lo que cuando hagamos nuestra búsqueda, necesitamos guardar cálculos que ya hayamos hecho para no calcular un mismo estado más de una vez.

Nuestro árbol de búsqueda ya está terminado, así que es hora de convertirlo a una función matemática. Nuestra función recibe como entrada un estado, en este caso el chocolate más a la izquierda que nos queda, el más a la derecha y el nivel en el que estamos, y dado lo que aprendimos de nuestro árbol de búsqueda, regresará el siguiente valor:

Con esto, y considerando que debemos evitar repetir valores duplicados, es más que suficiente para resolver el problema con el método que más te guste, ya sea dinámica o memorización, aunque hay un pequeño problema para guardar los valores visitados.

Vamos a necesitar un arreglo de 1000 x 1000 x 1000 si es que queremos guardar un arreglo que se identifique de esta forma:

arreglo[izquierda][derecha][nivel]

Y esto es mucho más de lo que cabe en memoria, por lo que tenemos que encontrar una forma de reducir la memoria que necesitamos.

Lo que nos tenemos que dar cuenta es que la variable nivel es innecesaria, pues puede calcularse utilizando el número de chocolates que nos quedan en el tubo y el número de chocolates que teníamos originalmente:

nivel = total – chocolates_en_el_tubo + 1

Y para calcular el número de chocolates que nos quedan en el tubo solo se necesitan el índice del chocolate más a la izquierda, y más a la derecha, que ya tenemos en nuestro estado.

chocolates_en_el_tubo = derecha – izquierda + 1

Despejando:

nivel = total – derecha + izquierda – 1 + 1

nivel = total – derecha + izquierda

De esta forma, podemos eliminar el nivel de todos nuestros estados y cambiar el valor de nivel de todas las fórmulas por el valor de arriba. Esto simplifica nuestro arreglo de visitados de 1000 x 1000 x 1000 a un arreglo de tan solo 1000 x 1000, lo cuál es suficiente en tiempo y memoria.

 

Solución a “Contraseña Binaria”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 7
Autor: Orlando Isay Mendoza Garcia
Fuente: Christian Adan Hernández Sánchez

Podemos ayudarnos de la imagen para comprender mejor esta explicación:

En ella aparecen de forma descendente a la izquierda los números pares comenzando desde el dos, y su representación binaria a la derecha. En la parte superior aparece el valor de cada cifra en decimal.

Tomando en cuenta el límite del problema, sabemos que si sumamos B(i) para cada par menor o igual a N, en el peor de los casos tendríamos que realizar 500,000,000,000,000 veces la función. Aún si lograramos calcularla en una operación nuestro programa excedería el tiempo límite.

En cambio, haciendo cálculos notamos que:
2^{50} \approx 1,000,000,000,000,000. Lo cual significa que a lo más habrán 50 columnas en la tabla (ya que en la forma binaria cada cifra representa una potencia de 2).

Dado que sabemos que en una suma el orden de las cantidades a sumar no importa, podemos determinar que es lo mismo sumar los valores de forma horizontal, tanto como de forma vertical. Sumando los valores de las columnas solo tomaría 50 operaciones. La columna 1 podemos ignorarla ya que al ser pares los números de la lista ninguno contendrá un 1 en la última cifra.

Observando la siguiente imagen, vemos que la columna C se forman grupos de tamaño C (por ejemplo, en la columna 4 se forman grupos de cuatro elementos),que contienen una la mitad de 1s y la otra de 0s. También podemos ver que en la columna 2 no hay 0s antes del primer grupo, en columna 4 hay un 0, en la que sigue hay 2, luego 4,etc (área en color gris). Podemos notar que ese espacio aumenta en base a potencias del dos.

Teniendo el número N habrán N / 2 números en la lista. Para calcular la cantidad de grupos completos que se forman en cada columna dividimos N menos el espacio lleno de ceros en esa columna, entre el número de la columna en el que estemos; a su vez, esta cantidad la multiplicamos por, el número de la columna entre dos. Sin embargo, puede que nos falten de contabilizar los 1s que pudieran estar en un grupo que no se completo. Esto se arregla sumando a lo anterior, el mínimo entre el resto de la división anterior y, el número de la columna entre dos.

Código:

Solución a “Poema Equino”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 5
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves, Freddy Román Cepeda

Los límites de este problema permitían hacer una búsqueda sobre todos los estados posibles de los caballos sobre el teclado, ya que si el estado es (\text{poema},\text{fila caballo}_1,\text{columna caballo}_1,\text{fila caballo}_2,\text{columna caballo}_2), solamente hay 100 \times (4 \times 10)^2 = 160,000 estados distintos.

Además, como el problema no pide la cantidad mínima de movimientos no hace falta hacer una BFS (búsqueda en amplitud), sino que una DFS (búsqueda en profundidad) utilizando el mismo stack del lenguaje es suficiente. Para simplificar la implementación, se podían utilizar varias observaciones. Particularmente, no importa qué caballo es el 1 o el 2, por lo que en vez de escribir código para mover a ambos basta con añadir una transición que cambie los roles de los caballos en cada estado. Esto además de simplificar la implementación sirve como una poda ya que ¡reduce la cantidad de estados a la mitad! (¿por qué?). También, se puede aprovechar que los operadores booleanos en C/C++ evalúan a 1 cuando son verdaderos y a 0 cuando son falsos, lo cual es bastante útil para indexar arreglos.

Varios competidores fallaron en su primer intento por no revisar que los caballos no podían ocupar la misma tecla al mismo tiempo. ¡Cuidado!

La siguiente solución implementa las simplificaciones descritas anteriormente.

Solución a “Carretera”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Examen 1
Autor: Freddy Román Cepeda
Fuente: Edgar Augusto Santiago Nieves, Freddy Román Cepeda

Para obtener los puntos de la primer subtarea bastaba notar que las condiciones especificadas significan que hay dos bloques de coches yendo en diferentes sentidos que inicialmente no se intersectan y eventualmente lo harán, por lo que la respuesta simplemente es el máximo de los anchos de estos bloques.

Este código obtiene los primeros 30 puntos:

Para el resto de los puntos: Sea f(t) el ancho necesario para la fotografía en el segundo t. La observación crucial es que f es una función unimodal: es decir, existe un punto t_0 tal que f es decreciente a la izquierda de t_0 y es creciente a la derecha.

Computar f(t) para t fijo es trivial: basta con obtener el coche más a la izquierda y más a la derecha en el segundo t, lo cual toma tiempo O(N). Como f es unimodal, podemos utilizar búsqueda ternaria o búsqueda binaria para encontrar el mínimo de la función en tiempo O(\lg T), donde T es el tamaño del rango a evaluar. Con eso obtenemos un algoritmo con complejidad O(N \lg T), suficiente para obtener todos los puntos del problema.

El siguiente código implementa la solución anterior con búsqueda binaria.

Solución a “Químicos”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 6
Autor:  Luis Héctor Chávez (lhchavez)
Fuente: Ethan Jiménez Vargas

Éste es un problema que tiene una solución elegante y determinística pero requiere algoritmos avanzados bastante complicados. Lo bueno es que es posible aproximar a la solución utilizando fuerza bruta mediante backtracking.

El problema nos pide encontrar una manera de asignar sustancias a los tubos y después mezclarlas con las dos operaciones disponibles (suma y diferencia absoluta) para terminar con un acomodo homogéneo de sustancias: la diferencia entre el tubo con más cantidad y con menos cantidad de sustancia debe ser lo más pequeña posible. Una manera de hacerlo es proponer un intervalo [a,b] y ver si es posible asignar sustancias y aparear los tubos de manera que la cantidad de sustancia resultante de la mezcla en todos los tubos esté contenido dentro del intervalo. Para acelerar el proceso, puedes elegir los intervalos haciendo una búsqueda binaria de acuerdo a su ancho b-a, porque a fin de cuentas lo que nos pide el problema es precisamente el ancho mínimo. Para cada intervalo propuesto [a,b], podemos hacer un grafo con 2N nodos (uno para cada tubo), agregando un arco entre dos nodos A y B si A+B\in[a,b] ó |A-B|\in[a,b]. Después, buscamos un apareamiento máximo) en el grafo: buscamos el conjunto de arcos con cardinalidad máxima tal que cada nodo tenga a lo más un arco incidente. Esto se puede encontrar con el algoritmo de Edmonds (también conocido como el Blossom algorithm por la forma de los ciclos de longitud impar) en tiempo O(|2N|^4), lo cual encontraría todas las soluciones en solo un par de segundos.

Lamentablemente la implementación del algoritmo de Edmonds es bastante complicada. Como este es un problema de solo-salida y todo se vale, en vez de hacer el intento por implementarlo, utilicé la librería Boost de C++ que ya tiene muchísimos algoritmos de grafos ya implementados.

Ahora, si no se te ocurre usar el algoritmo de Edmonds o no tienes acceso a Boost, aún así puedes obtener una cantidad decente de puntos usando una heurística: podemos intentar hacer un apareamiento máximo usando fuerza bruta, rindiéndonos si el problema suena muy complicado y asumimos que no existe un apareamiento. Una fuerza bruta naïve con un contador que se decrementa cada vez que se llama la función de búsqueda es más que suficiente. Haciendo un par de modificaciones al algoritmo anterior nos da una solución que nos da el 80% de los casos bien:

Claro que si te quieres ver greedy, puedes subirle al número de intentos, pero posiblemente no haya suficiente tiempo en el concurso para que termine. Si llegas a utilizar estas técnicas “impuras”, asegúrate primero de obtener cualquier solución que te de puntos antes de subirle para encontrar mejores respuestas.

Solución a “Crucero”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 4
Autor: Saúl Germán Gutiérrez Calderón
Fuente: USACO Enero 2009 Gold

Como se puede notar, al trazar la ruta óptima del crucero se está desperdiciando mucho espacio, y daría lo mismo si expandiésemos la isla para que no se desperdiciara espacio entre la ruta y la orilla de ésta.


Si supiéramos cual es la ruta óptima del crucero para expandir la isla bastaría con hacer un Flood Fill para rellenar los espacios con agua que quedan dentro de la ruta.

Resulta que el flood fill e puede hacer aun sin conocer cuál sería la ruta óptima. Si nos ponemos a hacer todos los tipos de celdas adyacentes a la celda actual en un flood fill, nos toparemos con que solo hay 2 que permiten que la isla crezca y 1 que evita que se expanda. El resto de las celdas adyacentes no nos dice nada acerca de si tenemos que poner algo ahí o no (de momento).

Si se pone un pedazo de isla nuevo en el centro de las figura de abajo, entonces la cosa peligrosa tendría que ser rodeada de alguna manera para poder pasar, lo cual nos llevaría a tomar una ruta mas larga. Por ello, no es una buena idea poner un pedazo de isla ahí.

Si es como la de la figura de abajo,

ambos caminos tienen la misma longitud. Por ello, se puede poner un pedazo de isla ahí y esto nos simplifica el problema.

La ruta óptima no puede pasar por el cuadro del centro ya que esto sería un desperdicio de tiempo, por lo cual podemos expandir la tierra ahí.

Entonces, sólo hay que hacer todas las expansiones de tierra hasta que ya no se pueda más y después de esto se puede hacer una mano derecha para buscar la orilla de la isla que al mismo tiempo será la ruta óptima.

Solución a “Mocha Hojas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Freddy Román Cepeda
Fuente: Alberto José Ramírez Valadez

Para simplificar el análisis, podemos notar que la respuesta que nos piden es igual al total de los pesos de las hojas del árbol menos el total de los pesos de las hojas del árbol ya balanceado. De ahora en adelante, trataremos el problema como si tuviéramos que conseguir este segundo valor, en vez del número de operaciones. Entonces queremos maximizar el peso total del árbol balanceado, para minimizar la cantidad de operaciones.

Consideremos el caso de un árbol con un solo nivel. Ya que sólo podemos restarle a los pesos de las hojas, evidentemente el peso máximo del árbol se alcanza cuando se emparejan todas las hojas al peso de la hoja con peso mínimo.

Ahora, consideremos un árbol con dos niveles. Si la raíz tiene k hijos, para cada hijo i sea h_i el subárbol de i, b_i el número de hojas de h_i, y c_i el peso del árbol obtenido de realizar el procedimiento del párrafo anterior a h_i. Si todas las c_i son iguales, entonces nuestro árbol está balanceado. De lo contrario, debemos restar aún más para poder balancearlo. Sin embargo, también necesitamos que cada h_i continúe estando balanceado. La única manera que le podemos restar peso a h_i sería restarle la misma cantidad de peso a cada una de sus hojas. Entonces, a cada h_i sólo podemos restarle peso en múltiplos de b_i. Como queremos maximizar el peso del árbol resultante, necesitamos encontrar el número más grande x tal que a todos los c_i les podamos restar un múltiplo de su respectivo b_i para obtener x. Notemos también que c_i es un múltiplo de b_i porque los nodos internos del árbol no tienen peso. Si m es el mínimo común múltiplo de todos los b_i, entonces x también es un múltiplo de m. Entonces, el máximo x posible es igual al múltiplo de m más grande que sea menor o igual a todos los c_i. Por lo tanto, el valor máximo obtenible del árbol completo es igual a kx. Por último, si tuviéramos que restarle más peso a este árbol pero mantenerlo balanceado, es evidente que lo menos que podemos restar para mantenerlo balanceado es km, y si seguimos restando km continuará balanceado.

De esta observación podemos obtener la solución para cualquier árbol. Reusando la notación del párrafo anterior, k es la cantidad de hijos de la raíz, h_i el subárbol del iésimo hijo, y c_i el peso del árbol obtenido de realizar recursivamente el procedimiento de éste párrafo a h_i (o el del anterior si h_i tiene 2 niveles). Ahora b_i es igual a lo mínimo que le podemos restar a h_i y que continúe balanceado. El análisis del párrafo anterior también es correcto para la nueva definición de b_i y c_i.

El código siguiente implementa esta solución:

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.