Resolución del problema Lightning Conductor usando tablas dispersas y optimización de decisiones
El problema Lightning Conducter (POI2011) requiere calcular para cada posición i el valor máximo de la expresión:
[\max\left{a_j+\left\lceil\sqrt{|i-j|}\right\rciel\right}-a_i ]
Una solución directa con complejidad (O(n\sqrt{n})) utiliza una tabla de máximos (ST table) para rangos. Dado que (\sqrt{|i-j|}) tiene aproximadaemnte (\sqrt{n}) valore ...
Publicado el 9-16 07:21
Análisis de intervalos consecutivos mediante estructuras de datos avanzadas
Transformación del problema
El problema se puede reformular como:
Determinar la centidad de subintervalos donde se cumple que Max - Min = r - l
Solución por fuerza bruta
Aprvoechando la propiedad anterior, podemos iterar todos los posibles intervalos y verificar si cumplen con la condición.
#include <iostream>
#include <cstdio>
#inc ...
Publicado el 8-8 13:26