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 el ancho necesario para la fotografía en el segundo
. La observación crucial es que
es una función unimodal: es decir, existe un punto
tal que
es decreciente a la izquierda de
y es creciente a la derecha.
Computar para
fijo es trivial: basta con obtener el coche más a la izquierda y más a la derecha en el segundo
, lo cual toma tiempo
. Como
es unimodal, podemos utilizar búsqueda ternaria o búsqueda binaria para encontrar el mínimo de la función en tiempo
, donde
es el tamaño del rango a evaluar. Con eso obtenemos un algoritmo con complejidad
, suficiente para obtener todos los puntos del problema.
El siguiente código implementa la solución anterior con búsqueda binaria.
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 multiplicando a
por sí mismo
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 , que
, y que
para toda
y
, por lo que podemos escribir la siguiente relación:
Aplicando esta definición directamente, la segunda subtarea queda resuelta. Esto es porque el algoritmo descrito anteriormente tiene complejidad , ya que en cada paso
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 . Para ello requerimos una observación adicional. Dividir entre
en base
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 como una cadena de bits y modficando un poco la función descrita anteriormente. Si
es el arreglo donde guardamos los bits de
, está
-indexado, tiene
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
, donde
es:
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 como el número que se obtiene tomando los elementos
del arreglo
, y
. Recordando que multiplicar por
en base
es lo mismo que recorrer todos los dígitos a la izquierda,
.
Ahora, es simple notar que , que podemos reescribir como
.
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 bits se eleva al cuadrado, puede ahora tener a lo más
bits. Como
puede tener hasta
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 .
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.