Solución a “Suma Manhattan”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 1
Autor: Freddy Román Cepeda
Fuente: Freddy Román Cepeda

Este problema requería manipular con cuidado la expresión que había que computar.
Recordemos que nos piden computar

\sum_{0 \leq i < j < N} manhattan(S_i,S_j).

Para resolver la primer subtarea bastaba con iterar sobre todas las parejas de puntos y calcular su distancia. Esto corre en tiempo cuadrático y no es suficiente para obtener todos los puntos.

La siguiente subtarea era una pista: se puede computar la distancia Manhattan de dos puntos considerando por separado sus coordenadas en x y y. Ahora nos preocuparemos por calcular la siguiente expresión:

\sum_{0 \leq i < j < N} |a_i - a_j|.

Donde a son las coordenadas en x o y. El problema está en el valor absoluto. La manera más sencilla de deshacernos de él es ordenar la secuencia a, de tal manera que a_i \leq a_j. Entonces tenemos:

\sum_{0 \leq i < j < N} |a_i - a_j| = \sum_{0 \leq i < j < N} |a_j - a_i| = \sum_{0 \leq i < j < N} a_j - a_i.

La primer igualdad es verdadera porque |x| = |-x| para cualquier x. La segunda es porque como ahora a está ordenado, como a_j \geq a_i \implies a_j - a_i \geq 0, el valor absoluto no hace nada.

Podemos entonces separar la suma en dos términos:

\sum_{0 \leq i < j < N} a_j - \sum_{0 \leq i < j < N} a_i.

Analicemos el primer término. Estamos sumando sobre todas las j tantas veces haya una i menor que ella. Eso quiere decir que cada a_j la vamos a sumar j veces (nota que a_0 la sumamos 0 veces).

El segundo término nos dice que sumaremos todas las a_i tantas veces haya una j mayor a ella. Eso quiere decir que cada a_i la vamos a sumar N-i-1 veces (nota que a_{N-1} la sumamos 0 veces).

Juntando esas ideas, entonces tenemos:

\sum_{j = 0}^{N-1} j \cdot a_j - \sum_{i = 0}^{N-1} (N - i - 1) \cdot a_i

= \sum_{i = 0}^{N-1} i \cdot a_i - \sum_{i = 0}^{N-1} (N - i - 1) \cdot a_i.

= \sum_{i = 0}^{N-1} (i - (N - i - 1)) \cdot a_i.

= \sum_{i = 0}^{N-1} (2i - N + 1) \cdot a_i.

Y con eso terminamos: ahora tenemos una expresión que podemos computar fácilmente en tiempo lineal. Hay que tener cuidado al computar esto: La primera observación es que hay que estar tomando módulo después de cada operación porque en cualquier momento puede haber un overflow. Algunos competidores obtuvieron 60 puntos en este problema por no tomar esto en cuenta. La segunda observación es que el término (2i - N + 1) \cdot a_i no necesariamente cabe en un entero signado de 32 bits — hacía falta utilizar enteros de 64 bits para realizar este cálculo.

Aquí está mi código que implementa la solución anterior.

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.

Solución a “Panoramas”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 17
Autor: Miguel Ángel Covarrubias
Fuente: Miguel Ángel Covarrubias

El problema es un Steiner tree problem (un MST pero donde sólo hay que conectar un subconjunto de nodos) pero con costo por nodo en vez de por arista. El grafo de los panoramas es un árbol más un ciclo. Para un árbol una solución es poner como raíz a s_1 y para cada s_i marcar los nodos en su camino hacia la raíz. Se puede usar DP o recursión para calcular el mínimo numero de vertices que conectan todos los nodos interesantes y pasan por la raíz para cada subárbol.

\mathrm{dp}_r=\mathrm{interesante}(r)\  \mathrm{si}\ \Sigma_h\mathrm{dp}_h=0
\mathrm{dp}_r = \Sigma_h\mathrm{dp}_h+1\  \mathrm{si}\ \Sigma_c\mathrm{dp}_h>0

h es un hijo de r. La arista extra (u,v) en el ciclo c permite usar otros caminos a lo largo de c. Tales caminos deben conectar todos los nodos en c que tengan nodos interesantes en su árbol después de quitar las aristas del ciclo E-c. Etiquetemos tales nodos con un uno y los demás nodos del c con un cero. Para E-(u,v) el ciclo sólo no cubre los últimos ceros. Para encontrar la solución sólo basta encontrar la secuencia de ceros más grande.
En el siguiente diagrama, la arista que falta es (u,v). La DP sólo no usa el último cero, pero es mejor no usar los dos ceros que están adyacentes.

  0 1
 /   \
1     0
 \   /
  1-0

Este código implementa la solución.

Solución a “Mapas de bits”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12
Autor: Jorge Alberto González Martínez
Fuente: Jorge Alberto González Martínez

En el problema se describen dos formas de representar un mapa de bits.

La forma bidimensional es simplemente utilizar una matriz para representar los bits.
La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.

La solución a este problema consistía en programar el método descrito. Este método inherentemente está basado en la técnica de divide y vencerás.

A continuación, un pseudo-código que muestra la forma de llevar a cabo la transformación de un mapa de bits bidimensional a la forma reducida:


ReduceMapa(mapaDeBits)
Si todos los elementos en mapaDeBits son iguales
    Imprime el valor y termina
Si no
    Imprime D
    ReduceMapa(mapaDeBits.superiorIzquierdo)
    ReduceMapa(mapaDeBits.superiorDerecho)
    ReduceMapa(mapaDeBits.inferiorIzquierdo)
    ReduceMapa(mapaDeBits.inferiorDerecho)

El método para hacer la transformación inversa es muy parecido, sólo que para imprimir la equivalencia hay que comenzar con un mapa de bits bidimensional que nos sirva de variable auxiliar para hacer la conversión. Esta variable auxiliar se puede declarar de manera global y, cuando el método recursivo termine, simplemente imprimir su contenido:


AmplificaMapa(mapaDeBits, sección)
Si mapaDeBits comienza con un valor
    Rellenar sección del mapa bidimensional con el valor
Si no
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorDerecha)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorDerecha)

La primera vez que se llama a la función AmplificaMapa se debe entregar la representación de la forma por descomposición del mapa de bits en la variable mapaDeBits y la sección que se entrega inicialmente es todo el mapa de bits. Esto puede ser manejado por filas y columnas.

A continuación se muestra una implementación en C++ que resuelve el problema. Nótese cómo se maneja la sección sobre la que se está trabajando con cuatro variables: tl_row, tl_col, br_row, br_col. El nombre de las variables proviene de top-left row, top-left colum, bottom-right row y bottom-right colum respectivamente. Representan los índices (fila,columa) de las esquinas superior izquierda e inferior derecha.

Solución a “Pista”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 14
Autor: Miguel Covarrubias
Fuente: Codeforces

Este problema es una ligera modificación del Let’s Play Osu! que apareció en la ronda 146 en Codeforces. La solución explicada la pueden encontrar en el editorial.

Para N \le 10 se pueden checar todas las 2^N configuraciones de pistas. Para N \le 1000 funciona una dinámica O(N^2), donde los estados son (posición, altura/profundidad que se lleva hasta el momento).

Les dejo la implementación de DiegoRoque como un muy buen ejemplo de una solución a este problema.

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)