Solución a “Jardinero”

Concurso: Preselectivo para la IOI 2015, Etapa 1, Problemset 6
Autor: Saúl Germán Gutiérrez Calderón
Fuente: Saúl Germán Gutiérrez Calderón (recopilado de los ACM-ICPC World Finals 2010, problema I)

En este problema, una búsqueda exhaustiva con podas bastaba para que corriera en tiempo.

La búsqueda podía tener como estado al renglón y a la columna en la que se estaban, más las casillas por las que ya se había pasado más el numero de la siguiente casilla a esconderse que se necesitaba.

Las podas que se utilizaron en la solución oficial fueron las siguientes (otras podas podrían también conseguir 100 puntos):

  1. Que pasara el tiempo en el que se debería llegar a un escondite.
  2. Que se pasara por un escondite cuando no se debía.
  3. Que no fuera capaz de llegar al siguiente escondite a tiempo.
  4. Que el camino que se llevaba volviera imposible una ruta válida. Si la ruta dejaba a algunas posiciones “encerradas” o dividía al mundo en dos, entonces la ruta actual no llevaba a ningún recorrido valido. Esto se podía checar haciendo una búsqueda en profundidad o en amplitud desde alguna posición no visitada (la posición (0,1) es bastante conveniente porque siempre estará libre).

Aquí está el código de la solución:

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 “Planetas”

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

La observación principal de este problema es que siempre hay N-1 lugares estables para el meteorito, y que cada uno de éstos se encuentra entre parejas consecutivas de planetas. Primero notemos que ningún lugar estable puede estar más a izquierda que todos los planetas, ya que la fuerza neta sobre éste lo haría moverse a la derecha. Por la misma razón, no pueden haber lugares estables después del último planeta hacia la derecha.

Ahora, para ver que siempre hay un lugar estable entre cualquier pareja consecutiva de planetas hay que analizar la función que describe la fuerza entre el meteorito y el planeta: \frac{1}{\left | X_i - M \right |}. Supongamos que el meteorito está entre los planetas i e i+1. Cuando M \approx X_i la fuerza que atrae al meteorito hacia el planeta i es suficientemente grande para forzar al meteorito a moverse a la izquierda sin importar la fuerza de los planetas que se encuentren a la derecha (nota que el denominador se hace muy pequeño). Lo mismo ocurre con el planeta i+1 cuando el meteorito está muy cerca de él. Pero esto quiere decir que existe un único punto p entre los dos planetas en el que la fuerza neta sobre el meteorito es 0. (Este argumento se puede formalizar utilizando cálculo.)

Además, es sencillo observar que el meteorito se movería a la izquierda si estuviera entre el planeta i y el punto p, y a la derecha si estuviera entre el punto p y el planeta i+1. Por lo tanto, podemos hacer una búsqueda binaria para encontrar el punto p para cada pareja de planetas consecutivos.

Como hay N-1 parejas y calcular la fuerza neta sobre el meteorito en algún punto arbitrario toma tiempo O(N), la complejidad total de este algoritmo es O(N^2 I) donde I es la cantidad de iteraciones que realice la búsqueda binaria. También hay que ordenar los planetas, ya que la descripción del problema no asegura que vendrán ordenados. Por lo tanto, la solución final tiene complejidad O(N \lg N + N^2 I).

El siguiente código implementa esta solución:

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 “Números Libres”

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

Para resolver este problema hacía falta tener en mente la definición de square-free. Como tanto a y b no son divisibles por el cuadrado de un primo, la única manera de que su producto deje de ser square-free sería que ambos compartieran un factor primo.

Para obtener todos los puntos de la primer subtarea bastaba con computar a \times b e iterar sobre todos los números menores a ese producto y revisar si es divisible por el cuadrado de alguno de ellos.

Para obtener los puntos de la segunda subtarea era suficiente iterar hasta \max(\sqrt{a}, \sqrt{b}), para factorizar a a y b.

Por último, para obtener el resto de los puntos bastaba notar que si a y b comparten un factor primo, entonces su máximo común divisor es distinto de 1.

El siguiente código implementa esta solución:

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: