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.