Amassando ideas

Nota: Por defecto, los intervalos de números que aparecen en este artículo son cerrados.

Este problema apareció en uno de los concursos abiertos que organiza la Olimpíada Informática de Croacia. Escogí hacer un pequeño tutorial de este problema porque para hallar la solución se requiere hacer uso de la misma propiedad de las sumas necesaria para demostrar nuestra solución a Two Sets.

Resumen del enunciado

Dadas $N \leq 1000000$ columnas de alturas $1$, $2$, \ldots, $N$, hay que formar un histograma con ellas tal que la cantidad máxima de agua que se puede verter dentro sin que el agua rebalse del histograma (es decir, su capacidad) sea exactamente $X \leq 10^{15}$.

Por ejemplo, si $N = 3$, tenemos las columnas de altura $1$, $2$ y $3$ y el histograma “$2$ $1$ $3$” tiene una capacidad de $1$.

¿Es posible crear el histograma?

Dado un histograma, si agarramos un sub-histograma cualquiera, se crea una especie de pozo de agua entre las dos columnas más altas (si no me crees, mira la imagen de arriba). Entonces el histograma con el pozo más grande que podemos hacer tiene las columnas de alturas $N$ y $N-1$ en los bordes y el resto en medio. Su capacidad es exactamente $(N-1)-1 + (N-1)-2 + \ldots + (N-1)–(N-2) = 1 + 2 + \ldots + (N-2) = \frac{(N-2)(N-1)}{2}$. Por lo tanto, si $X$ excede dicho valor, la respuesta es $-1$ porque no podemos crear un histograma con capacidad $X$ con las $N$ columnas que tenemos.

¿Y si $X \leq \frac{(N-2)(N-1)}{2}$?

En ese caso sí podemos construir el histograma muy fácilmente. Hay que crear un pozo con las columnas de alturas $N$ y $N-1$ en los bordes, y en medio las columnas que vamos a usar para conseguir una capacidad de $X$. Las que no ocupemos pueden ir en el borde izquierdo en orden ascendente para que no creen ningún pozo.

¿Qué columnas irán dentro del pozo?

Si elegimos una columna de altura $h$, la capacidad del pozo aumentará en $(N-1)-h$. Como la altura mínima de las columnas restantes es $1$ (que aumenta la capacidad en $N-2$) y la máxima es $N-2$ (que aumenta la capacidad en $1$), y además existe exactamente una columna disponible para cada altura entre $1$ y $N-2$, tenemos que elegir un subconjunto de ${1, \ldots, N-2}$ tales que la suma de sus elementos sea igual que $X$.

El subconjunto a elegir siempre existe pues para cualquier $M \in \mathbb{N}$ y $S \leq \frac{M(M+1)}{2}$ (fracción que corresponde a la suma de todos los números naturales desde el $1$ hasta el $M$), siempre existe un subconjunto de ${1, \ldots, M}$ tal que la suma de sus elementos sea $S$. En el tutorial de Two Sets demuestro una propiedad muy parecida.

Dado lo anterior, podemos declarar una variable $S$ y asignarle el valor $0$, variable que nos servirá para saber cuánta capacidad llevamos. Iteramos con $k$ desde $N-2$ hasta $1$ (inclusive). Si $S + k \leq X$ significa que debemos añadir la columna de altura $(N-1)-k$ al pozo, y en caso contrario debemos colocarla fuera. Una vez terminadas todas las iteraciones, se imprimen en orden ascendente las columnas no ocupadas para almacenar agua (las que llamamos “del pozo”), la de altura $N-1$ (o $N$), las columnas que sí ocupamos para hacer que la capacidad del histograma sea $X$, y finalmente la columna de altura $N$ (o $N-1$).

¿Me darías más detalles?

Si ocupamos un vector de booleanos (en C++) para indicar si una columna debe ser del pozo o debe quedarse al margen, la complejidad tanto espacial como temporal de la solución es de $O(N)$, suficiente para los límites de tiempo y memoria RAM del problema.

No me gusta dar detalles sobre la implementación a pesar de tener el código de la solución que podría publicar, porque considero que el lector o lectora objetivo ya domina las bases de la programación en cierto lenguaje y debe ser capaz de diseñar una implementación de las soluciones por su cuenta.