¿Cómo resolvemos el problema B, ‘Can of Worms’, del Chicago Invitational Programming Contest 2013?

¡Oye! ¡Escribí este problema! Uno de los aspectos interesantes es que hay muchas soluciones. Mi favorito tiene que ser la solución O (N) si las latas se dieron en orden ordenado por coordenada x. También hay una solución O (N log M) que es muy corta para codificar si solo conoce las pilas. (Pero esta idea de solución se ejecuta en O (N ^ 2) si las explosiones fueran asimétricas)

Escribí una explicación bastante detallada de cómo resolver el problema cuando lo envié al concurso:
Página en vanb.org

Estoy sorprendido de cuántas soluciones complejas existen para este problema y se usaron en el concurso.

En una nota al margen de Nick Wu, un registro (N) vinculado a la cantidad de barridos para resolver el problema es incorrecto. Si lees mi documento de análisis, puedes ver que el límite está en el espacio de coordenadas y no en el número de latas. (De ahí el log (M)) Si las coordenadas estuvieran en un espacio continuo o limitadas por un número muy grande, entonces la solución podría tomar hasta O (N ^ 2) tiempo. (Mi tiempo de ejecución limitado proporciona tal construcción) Los datos, lamentablemente, no intentaron maximizar el número de barridos. (No hice los datos) La solución de Nick también podría tomar N pasadas si las explosiones pudieran ser asimétricas (¡el lado izquierdo de la explosión! = El lado derecho de la explosión). Hice las explosiones simétricas por simplicidad y porque encontré que el límite en el número de pasadas requerido era interesante. Desafortunadamente, muchos equipos simplemente adivinaron que esto era cierto en lugar de probarlo. También hubo el efecto secundario de muchas presentaciones de TLE de equipos que tenían un factor de registro (N) adicional o que usaban una estructura de datos generales más alta como el árbol de intervalos.

Las soluciones modelo tenían tiempos de ejecución de O (N) (después de la clasificación) y O (N log M).

Aquí está la solución que se me ocurrió mientras competía en este concurso, que obtuvo AC.

Ordena las bombas de izquierda a derecha. Vamos a mantener árboles de rango mínimo y máximo que, dado un intervalo de la línea numérica, devuelven los puntos más a la izquierda y a la derecha que están cubiertos por una explosión si explotamos todas las bombas dentro de ese intervalo. Tenga en cuenta que tendremos que discretizar las ubicaciones de las bombas para que quepan en las restricciones de memoria.

Ahora podemos barrer repetidamente de izquierda a derecha y de derecha a izquierda a lo largo de la línea numérica, actualizando los árboles de rango hasta que ya no actualice el árbol de rango. La razón por la que podría tener que barrer de un lado a otro es que una bomba puede tocar una bomba a la derecha, que es realmente grande, que toca más bombas a la izquierda. Tenga en cuenta que este fenómeno de salto hacia adelante y hacia atrás solo puede ocurrir un número logarítmico de veces.

Por lo tanto, solo tenemos que hacer un número logarítmico de barridos. Un único barrido toma [math] O (n \ log n) [/ math], por lo que esta solución es [math] O (n \ log ^ 2 n) [/ math].