Para cada ~1 \le i \le N^2~, calculamos el número mínimo de espectadores que odiarán al espectador ~i~ para siempre (la respuesta es la suma de estos valores). Este número coincide con el costo mínimo de una ruta desde el asiento del espectador i hasta los lados del cine, considerando que pasar por un asiento vacío ha costado 0 y pasar por un asiento ocupado tiene costo 1. Sea ~H_k(i)~ el costo mínimo (como se define arriba) de una ruta desde el asiento del espectador ~i~ hasta afuera del cine despues que los primeros ~k~ espectadores han salido del cine.

Observación clave.

Los valores ~H_k(i)~ son decrecientes (para ~k~ pasando de ~0~ a ~N^2~) y al principio se tiene que

\(H_0 (1) + H_0 (2) + ··· + H_0 (N^2) ≈ \frac{N^3}{6}\).

Nuestra estrategia es mantener todos los valores ~H_k (i)~ actualizados en todo momento. Inicializando ~H_0 (1),. . . , H_0 (N^2)~ en ~O (N^2)~ es simple. Vamos a mostrar cómo actualizar ~H_{k - 1} (1),. . . , H_{k - 1} (N^2)~ para obtener ~H_k (1),... , H_k (N^2)~. Cuando el espectador ~P_k~ se va, realizamos una búsqueda en amplitud (o una búsqueda en profundidad) a partir del asiento de de ~P_k~ y actualizando los valores. Durante la búsqueda del ~k~-ésimo primero en amplitud, visitaremos solo los asientos ~i~ tales que ~H_k (i) <H_{k - 1} (i)~, por lo tanto, el número total de asientos visitados en los ~N^2~ pasos (para ~1 \le k \le N^2~) es ~O (N^3)~ (ver la observación clave). La complejidad temporal de esta solución es ~O (N^3)~ con una pequeña constante que es suficiente para ser aceptada.