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 “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 “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 “DP Genérica”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 13
Autor: Freddy Román Cepeda
Fuente: Project Euler

Podemos tratar este problema de varias maneras distintas, 3 de las cuales discutiré en esta solución.

Análisis 1

Primero, una idea que hubiera obtenido 50 puntos.

Podemos observar que el problema es equivalente a encontrar de cuántas maneras se le puede asignar un número n_i del conjunto \{0,1,2\} a cada potencia de 2 tal que \sum_{i=0}^{\infty} n_i 2^i = x. Esto también es equivalente a encontrar cuántos números a y b hay tales que a + b = x y no haya ningún bit encendido en b que no esté encendido en a.

Consideremos la expansión binaria de a = \sum_{i=0}^{\infty} a_i 2^i y b = \sum_{i=0}^{\infty} b_i 2^i , donde cada a_i y b_i es 1 o 0. Al sumar a + b = \sum_{i=0}^{\infty} (a_i + b_i) 2^i tenemos que 0 \le n_i = a_i + b_i \le 2, como se necesita. Para contar solamente una vez cada configuración distinta de la secuencia n, añadimos la restricción de que cualquier b_i puede ser 1 sólo si a_i también lo es.

Subtarea 1

Para esta subtarea es suficiente probar todas las a y b posibles, revisando con un loop para cada bit si la condición sobre b se cumple. Este algoritmo corre en tiempo O(N^2 \log N).

Subtarea 2

Para esta subtarea podemos hacer una observación sencilla: a cada a sólo le puede corresponder una b, igual a x - a, lo que reduce la complejidad en tiempo del algoritmo a O(N \log N).

Subtarea 3

Podemos comprobar si b cumple la condición en tiempo constante utilizando operaciones de bits. Si ~a & b es igual a 0, b no tiene ningún bit encendido que a no tenga encendido. Ahora tenemos un algoritmo lineal. Desafortunadamente, ya no podemos mejorar nuestra solución fácilmente continuando con esta idea.

El siguiente código implementa esta solución:

Análisis 2

Podemos hacer programación dinámica de forma top-down. En ésta, contamos la cantidad de maneras de escribir x como pide el problema incluyendo o no cada una de las potencias distintas.

Consideremos la función f(n,p), que cuenta de cuántas maneras podemos escribir n utilizando potencias de 2 menores o iguales a p no más de 2 veces cada una. Es evidente que la respuesta se encontraría evaluando f(x,63).

Sabemos que f(n,p) = 0 si n es negativo o si p es negativo. Del mismo modo, f(n,p) = 1 si n = 0. De lo contrario, es igual a la suma de f(n,p-1), f(n-2^p,p-1) y f(n-2^{p+1},p-1), que corresponden a poner 0, 1, o 2 veces la potencia 2^p.

Subtarea 1

Aplicando directamente el análisis anterior, la subtarea 1 queda resuelta.

Subtarea 2

Varios de estos estados se repiten, así que convendría memorizarlos. Utilizando un contenedor como std::map, la solución se vuelve lo suficientemente rápida para resolver esta subtarea.

Subtarea 3

Podemos determinar en algunos casos rápidamente si la función se evaluará a 0. Sabemos que \sum_{i=0}^{k} 2^i = 2^{k+1} - 1. Entonces, el número más grande que podemos escribir sólo usando potencias de 2 menores o iguales a p a lo más dos veces es 2\sum_{i=0}^{p} 2^p = 2 (2^{p+1} - 1) = 2^{p+2} - 2. Por lo tanto, f(n,p) = 0 si n > 2^{p+2} - 2.

Esa optimización por sí misma (sin memorización), resuelve la subtarea 3.

Subtarea 4

Combinando las ideas de las dos subtareas anteriores, el algoritmo es lo suficientemente rápido para resolver todos los casos. Específicamente, la cantidad de estados que no podemos determinar como no viables instantáneamente es proporcional a \log x, y cada estado lo podemos evaluar en tiempo O(\log \log x) por nuestro std::map, dándonos una complejidad total de O(\log x \log \log x). Esta cota puede quedar más clara después de describir la tercera solución.

El siguiente código implementa esta solución:

Análisis 3

Esta solución es equivalente a la anterior, pero no precisa de un std::map.

Consideremos la función n(k), que definimos como el número que obtenemos tomando los bits 0..k de x. En otras palabras, si x = \sum_{i=0}^{\infty} x_i 2^i donde x_i es el i-ésimo bit de x, n(k) = \sum_{i=0}^k x_i 2^i. Ahora, definimos la función g(i,r), que cuenta de cuántas maneras se puede escribir el número n(i) + r2^i, utilizando potencias de 2 menores o iguales a i a lo más 2 veces. La respuesta, por lo tanto, se obtendría evaluando g(63,0).

Ahora, sabemos que g(i,r) = 1 si i < 0 y r = 0, porque podemos escribir sólo de una manera 0. Recordando que x_i es el i-ésimo bit de x, podemos decir que g(i,r) cuenta la cantidad de formas que se puede escribir el número (r+x_i)2^i + n(i-1). De ahora en adelante, por conveniencia, t = r + x_i.

Usando esto, podemos definir g(i,r) recursivamente:

g(i,r) = \begin{cases}  1 & \text{si } i < 0 \text{ y } r = 0 \\  \sum_{k=0}^{min(t,2)}g(i-1,2(t-k)) & \text{de lo contrario}  \end{cases}

En otras palabras, si tenemos que poner t veces la potencia i, podemos elegir ponerla hasta min(t,2) veces, y contar las maneras de escribir el resto usando potencias de 2 menores a p. Pero como dejamos t-k veces la potencia i sin poner, es igual a poner 2(t-k) veces la potencia i-1.

La siguiente observación es que si t es mayor a 3, g(i,r) = 0 porque 2\sum_{k=0}^{i} 2^k < 4 \times 2^{i}. Entonces, sólo nos interesan los casos en los que 0 \le t \le 3. En total, sólo hay 4 valores posibles para t en los que g(i,r) no es 0: 0, 1, 2, y 3. Enumerémoslos:

g(i,r) = \begin{cases}  g(i-1,0) & \text{si } t = 0 \\  g(i-1,2) + g(i-1,0) & \text{si } t = 1 \\  g(i-1,4) + g(i-1,2) + g(i-1,0) & \text{si } t = 2 \\  g(i-1,6) + g(i-1,4) + g(i-1,2) & \text{si } t = 3   \end{cases}

Pero g(i,r) = 0 si t > 3, y como t \ge r, nos quedamos con:

g(i,r) = \begin{cases}  g(i-1,0) & \text{si } t = 0 \\  g(i-1,2) + g(i-1,0) & \text{si } t = 1 \\  g(i-1,2) + g(i-1,0) & \text{si } t = 2 \\  g(i-1,2) & \text{si } t = 3   \end{cases}

Tomando en cuenta que r sólo puede ser 0 o 2, y x_i sólo 0 o 1:

(g(i,0),g(i,2)) = \begin{cases}  (g(i-1,0),g(i-1,2)+g(i-1,0)) & \text{si } x_i = 0 \\  (g(i-1,2)+g(i-1,0),g(i-1,2)) & \text{si } x_i = 1   \end{cases}

El siguiente código implementa esta solución, que corre en tiempo O(\log n) y espacio constante:

Como podemos observar, esta solución considera los mismos estados que la anterior, sólo que aquí evitamos computarlos, mientras que la otra los descarta inmediatamente.

Consideraciones

Varios competidores no consideraron que x no cabe en un entero signado de 64 bits. Si bien la respuesta cabe en uno, en los límites del problema se especifica que x < 2^{64}.

Análisis adicional:

Diego Roque escribió una solución distinta, la cual detallaré a continuación.

Consideremos la función f(x) como la define el problema: la cantidad de maneras de escribir x como una suma de potencias no negativas de 2 sin usar cada una más de 2 veces.

Enfoquémonos en la paridad de x (es decir, el último bit de x). Si x es impar, necesariamente tenemos que poner una vez la potencia 2^0, porque las otras dos opciones: ponerla 0 veces o ponerla 2 veces cambiarían la paridad de x. Por lo tanto, f(x) = f(\frac{x-1}{2}) si x es impar. En cambio, si es par, podemos elegir poner la potencia 2^0 0 o 2 veces, lo que nos deja con f(x) = f(\frac{x}{2}) + f(\frac{x}{2}-1). Sólo falta definir los casos base: f(0) = f(1) = 1.

Aquí está su código que implementa esta solución, que corre en tiempo O(\log^2 x \log \log^2 x):

Solución a “La Venganza de Silvio”

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

Este problema es bastante sencillo de entender, la dificultad radica en que exponenciar un número de la manera obvia no es lo suficientemente rápido para obtener todos los puntos disponibles.

Subtarea 1

Para obtener el primer grupo de puntos, sólo basta calcular N^M multiplicando a N por sí mismo M veces, teniendo cuidado de que no haya overflow.

Subtarea 2

Para la segunda subtarea, se necesita algo más rápido, para lo que se puede usar exponenciación binaria.

Sabemos que x^0 = 1, que (x^n)^2 = x^{2n}, y que x * x^{n-1} = x^n para toda x y n, por lo que podemos escribir la siguiente relación:

\text{potencia}(N,M) = \begin{cases} 1 & \text{si } M = 0 \\ (potencia(N,M/2))^2 & \text{si } M \text{ es par} \\ N * (potencia(N,(M-1)/2))^2 & \text{de lo contrario} \end{cases}

Aplicando esta definición directamente, la segunda subtarea queda resuelta. Esto es porque el algoritmo descrito anteriormente tiene complejidad O(log M), ya que en cada paso M se reduce a la mitad.

Subtarea 3

El algoritmo anterior es lo suficientemente rápido para resolver esta subtarea, pero el rango de los enteros de la máquina no es lo suficientemente grande para guardar a M. Para ello requerimos una observación adicional. Dividir entre 2 en base 2 ignorando el residuo es lo mismo que recorrer todos los dígitos una vez a la derecha descartando el bit menos significativo, y, además, se puede saber si un número es par o no con sólo ver el bit menos significativo del mismo.

Podemos aprovechar esta observación guardando M como una cadena de bits y modficando un poco la función descrita anteriormente. Si A es el arreglo donde guardamos los bits de M, está 0-indexado, tiene k bits, y los bits están ordenados del más significativo al menos (como viene en la entrada del problema), la respuesta se encuentra evaluando potencia2(N,k-1), donde potencia2 es:

\text{potencia2}(N,i) = \begin{cases} 1 & \text{si } i < 0 \\ (potencia2(N,i-1))^2 & \text{si } A[i] = 0 \\ N * (potencia2(N,i-1))^2 & \text{de lo contrario} \end{cases}

Subtarea 4

El problema con el algoritmo anterior es que ocupa demasiada memoria para los casos que contiene esta subtarea. Para corregirlo, podemos analizar la función anterior.

Por conveniencia, definamos f(i) como el número que se obtiene tomando los elementos [0..i] del arreglo A, y f(-1) = 0. Recordando que multiplicar por 2 en base 2 es lo mismo que recorrer todos los dígitos a la izquierda, f(i) = 2f(i-1) + A[i].

Ahora, es simple notar que potencia2(N,i) = N^{f(i)}, que podemos reescribir como potencia2(N,i) = N^{2f(i-1) + A[i]} = (N^{f(i-1)})^2 N^{A[i]}.

Por lo tanto, podemos escribir un ciclo en vez de utilizar recursión.

Este algoritmo ocupa espacio constante, por lo que resuelve la subtarea 4.

Aquí está la implementación del algoritmo anterior:

Consideraciones

Hay que tener cuidado de que no haya overflow. Cuando un entero de k bits se eleva al cuadrado, puede ahora tener a lo más 2k bits. Como m puede tener hasta 31 bits, es necesario usar enteros de 64 bits durante todos los cálculos.

También, varios competidores no consideraron el caso en el que se pide calcular N^0 \pmod 1.