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
Selección máxima de estudiantes con restricciones de supervisión
En este problema, se consideran n estudiantes en un aula. Cada estudiante (excluyendo al monitor principal, asignado con identificador 0) supervisa a otro estudiante específico. El objetivo es seleccionar el mayor número posible de estudiantes para una tarea, garantizando que para cada estudiante seleccionado, al menos uno de sus supervisores d ...
Publicado el 7-18 14:24