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.