Examen 1 – omegaUp blog

July 25, 2014July 27, 2014

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.

August 8, 2013September 14, 2013

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

July 29, 2013September 14, 2013

Solución a Las Cartas del Dr. Lira

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 1
Autor: Joemmanuel Ponce Galindo
Fuente: Topcoder

Básicamente lo que nos pide el problema es encontrar el número de cartas que son distintas entre la configuración que es dada como entrada y una configuración donde las cartas estén alternadas.

Cómo se explica en el problema, sólo hay 2 estados posibles en los que una carta puede estar: negro (B) y blanco (W). En otras palabras, la observación clave para resolver el problema es darse cuenta que sólo existen 2 configuraciones que cumplen con las reglas que necesita Dr. Lira: Una configuración donde la primer carta es W, la siguiente B, la siguiente W y así sucesivamente. La otra configuración posible es donde las cartas empiezan con B, forzando la siguiente carta a ser W y esta a su vez forzando la siguiente carta a ser B.

Contar el número de caracteres diferentes entre una cadena y otra sólo requiere de un ciclo, por lo que la complejidad es lineal con respecto al tamaño de la cadena. Lo único que tenemos que hacer es entonces comparar la cadena dada como entrada con las configuraciones BWBW.. y WBWB…, contar el número de diferencias y dar como salida el mínimo de estos números.