Por Freddy
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 $latex f(t)$ el ancho necesario para la fotografía en el segundo $latex t$. La observación crucial es que $latex f$ es una función unimodal: es decir, existe un punto $latex t_0$ tal que $latex f$ es decreciente a la izquierda de $latex t_0$ y es creciente a la derecha.
Computar $latex f(t)$ para $latex t$ fijo es trivial: basta con obtener el coche más a la izquierda y más a la derecha en el segundo $latex t$, lo cual toma tiempo $latex O(N)$. Como $latex f$ es unimodal, podemos utilizar búsqueda ternaria o búsqueda binaria para encontrar el mínimo de la función en tiempo $latex O(\lg T)$, donde $latex T$ es el tamaño del rango a evaluar. Con eso obtenemos un algoritmo con complejidad $latex 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.