SPOJ - 3407. Candy (SAMER08C)

El problema analizado hoy fue utilizado en el Regional Suramericano del 2008, donde fui el administrador del servidor y vi toda la acción desde adentro. Este problema puede ser resuelto utilizando Programación Dinámica, la cual es simple si el análisis se hace correctamente.

El problema analizado hoy fue utilizado en el Regional Suramericano del 2008, donde fui el administrador del servidor y vi toda la acción desde adentro. Hasta donde puedo recordar, sólo un equipo de Venezuela pudo resolver este problema durante la competencia, pero en SPOJ ha sido resuelto por más de 150 personas.

Enunciado del Problema

Este problema fue utilizado en el Regional Suramericano, pero Diego Satoba lo subió a SPOJ aqui. Sin embargo, no se si los casos de prueba utilizados son los mismos que fueron utilizados durante la competencia oficial.

Análisis del Problema

Este problema pide calcular la mayor cantidad de caramelos que se pueden tomar de la tabla, con la condición de que al tomar caramelos de una caja todas las cajas en las dos filas adyacentes y las dos cajas a los lados son vaciadas. Inicialmente el problema se ve complejo debido a que parece que el orden en que los caramelos son tomados importa; esto implica que se debe optimizar el orden en el que se toman los caramelos aparte de optimizar cuáles se deben tomar.

Las primeras dos propiedades a observar sobre la tabla son:

• Si al tomar una caja B1 se vacía una caja B2, entonces tomar la caja B2 ocasiona que se vacía la caja B1.
• Si al tomar una caja B1 no se vacía una caja B2, entonces tomar la caja B2 no ocasiona que se vacía la caja B1.

Este par de propiedas (y el hecho de que el operador de adición sobre los enteros es conmutativo) implica que el orden en que se tomen los caramelos no importa. Esto simplifica la solución, ya que se puede asumir que los caramelos se toman en un orden específico a nuestra conveniencia.

Otro aspecto complejo en el problema es que la tabla no se mantiene constante mientras se toman los caramelos, debido a que algunas cajas son vaciadas cuando algunos caramelos son tomados de otras cajas. Para simplificar esto es suficiente ver que vaciar una caja es equivalente a prevenir que se tomen caramelos de ésta. De esta forma, no es necesario modificar la tabla durante la ejecución del algoritmo.

Resolviendo un problema más simple

Ahora que el problema ha sido simplificado, es hora de ver como se puede obtener el máximo número de caramelos de la tabla. Primero, es mejor resolver un problema más simple para luego expandir la solución: dado un arreglo de caramelos, calcular el máximo número de ellos que se pueden tomar, si al tomar caramelos de una caja vacía las dos cajas adyacentes. Esto es equivalente a optimizar una fila en el problema original.

Para obtener el mayor número de caramelos posibles de una fila, se puede utilizar el hecho de que el orden en que se toman no importa para asumir que estos se toman de izquierda a derecha. Ahora que un orden ha sido establecido, la solución se puede formular utilizando Programación Dinámica (DP por sus siglas en inglés). Sea n el número de celdas en la fila, sea F_i el máximo número de caramelos que se pueden tomar si sólo las cajas i a la n-1 están disponibles, y sea C_i el número de caramelos en la caja i. La función F_i se puede plantear recursivamente de la siguiente manera:

F_i = \left\{
\begin{array}{ll}
  0 & \textrm{si $i \ge n$}\\
  \max(C_i + F_{i+2}, F_{i+1}) & \textrm{si $i < n$}
\end{array}\right

La definición recursiva de F_i funciona de la siguiente manera:

• El primer caso (i ≥ n) es el caso base, el cual ocurre cuando se desea obtener el máximo sobre una fila vacía. Como no hay caramelos para tomar, el valor de retorno debe ser 0.


• El segundo caso (i < n) es el único caso recursivo, el cual ocurre cuando aún quedan caramelos por tomar. En este punto existen dos opciones: tomar los caramelos y saltar la siguiente caja, o no tomar los caramelos y continuar con la siguiente caja. Entre esas dos opciones, se desea la que permita obtener la mayor cantidad posible de caramelos.

Implementar esta función de forma recursiva requiere tiempo de ejecución O(2^n), pero éste se puede reducir a O(n) utilizando DP (ver Implementación de la Solución para más detalles).

Extendiendo para el problema original

Una vez el problema ha sido resuelto para una fila, es hora de extender la solución para que funcione sobre toda la tabla. Si se observa de forma detenida el comportamiento de las filas en el problema, se puede ver que tomar un caramelo de una fila vacía completamente ambas filas adyacentes, y después de eso no hay otra forma de que se vacía esta fila. Con base en esto, se puede plantear una solución extendiendo F_i sobre una tabla, añadiendo una bandera para indicar si al menos un caramelo se tomo de la fila actual.

Desafortunadamente, esta solución es difícil de programar, ya que almacentar toda la tabla en un arreglo bidimensional excederá el límite de memoria (10^10 enteros requieren aproximadamente 9.3GB de memoria). Para almacenar toda la matriz al mismo tiempo, esta se debe almacenar en un arreglo unidimensional y su accesso se debe hacer de forma manual, en lugar de ser manejado por el compilador.

Para sobrepasar esta dificultad, es importante observar una vez se ha tomado un caramelo de una fila, la solución óptima implica tomar tantos caramelos como sea posible de esa fila. Esta propiedad permite la creación de una solución más simple: primero, se calcula el máximo número de caramelos que se pueden tomar de cada fila, y entonces (utilizando el mismo algoritmo) se calcula el conjunto óptimo de filas a tomar.

Utilizando esta reducción, la implementación de la solución debería ser corta y simple.

Implementación de la Solución

Como se mencionó en la sección anterior, la solución para optimizar filas se utilizará para optimizar toda la tabla, así que el primer paso lógico sería implementar la solución propuesta utilizando DP. En este problema, se utilizará un DP bottom-up, debido a que la versión top-down podría ocasionar un desbordamiento de pila. Primero, se debe declarar un arreglo para almacenar los valores calculados, añadiendo dos¹ posiciones adicionales para los casos de borde.

const int MAX_N = 100000;
int dp[MAX_N + 2];

Después de delcarar el arreglo, se debe implementar la función para optimizar un fila. Esta función debe recibir un apuntador a la fila y un entero con el tamaño de la misma, y debe operar de la siguiente manera:

• Inicializar los dos casos base con el valor de retorno 0.


• Procesar los estados comenzando desde los más pequeños hacia los más grandes, i.e.: desde n-1 hacia 0.


• Por cada estado, calcular el valor de F_i utilizando el caso recursivo. Los valores de F_{i+1} y F_{i+2} pueden ser tomandos directamente del arreglo, ya que los índices superiores ya han sido calculados.


• Después de procesar todos los casos, retornar el resultado de optimizar sobre toda la fila, i.e.: F_0.

int f(const int* c, int n) {
  dp[n] = dp[n + 1] = 0;
  for (int i = n - 1; i >= 0; --i)
    dp[i] = max(c[i] + dp[i + 2], dp[i + 1]);
  return dp[0];
}

Ahora se debe implementar la función principal, la cual consiste en un ciclo que lee y resuelve cada caso de prueba. Para resolver un caso, se declara un arreglo para almacenar el resultado de optimizar cada fila, que se puede llenar leyendo y optimizando fila por fila. Finalmente, se debe optimizar el arreglo con los óptimos de todas las filas utilizando la misma función, la cual retornará el valor óptimo para toda la matriz.

int main() {
  // zyx3d me dió la idea de utilizar (m | n | ...) != 0 para verificar el final.
  for (int m, n; scanf("%d %d", &m, &n) == 2 && (m | n) != 0;) {
    // Leer y optimizar cada fila, almacenando las respuestas en otra fila.
    static int rowOptimals[MAX_N];  // Resultados parciales de cada fila.
    for (int i = 0; i < m; ++i) {
      // Leer una fila, obtener el valor óptimo y almacenarlo.
      static int row[MAX_N];  // Arreglo con la fila actual.
      for (int j = 0; j < n; ++j) scanf("%d", &row[j]);
      rowOptimals[i] = f(row, n);
    }
    // Al final, optimizar las filas utilizando el mismo algoritmo.
    printf("%d\n", f(rowOptimals, m));
  }
  return 0;
}

Conclusión

En este artículo se presentó la solución para el problema SPOJ CANDY, utilizando una solución que lee y procesa una fila a la vez, y luego reutiliza el mismo algoritmo para resolver el problema para toda la matriz. Es importante resaltar que se implementó una solución simple e inteligente observando que el comportamiento de las filas en la matriz es el mismo comportamiento de las celdas en cada fila.

---

1. Si sólo se declara una posición extra, el arreglo será accesado por fuera cuando F_i necesite F_{i+2}, con i=n+1.