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