====== Sliding Window RMQ ====== ==== Requisitos previos ==== * [[cpp-avanzado:deque |deque]] * [[cpp-avanzado:set |set y multiset]] ==== Motivación: situación o "problema" que deseamos resolver ==== FIXME [Sacar cosas de acá, y llevarlas a su propio artículo separado de ventana deslizante, que acá queda linkeado] Una ventana deslizante (en inglés, Sliding Window) es un concepto que se utiliza mucho en el desarrollo de algoritmos. Consiste en un cierto **intervalo**, delimitado por dos índices $A$ y $B$, de forma tal que el intervalo incluye todos los $x$ tales que $A \leq x < B$, es decir, nuestro intervalo es de la forma $[A,B)$((Cerrado a izquierda, abierto a derecha: esta es la convención más recomendada para estos casos.)). Además, como sugiere su nombre, una característica esencial de las ventanas deslizantes es que sus extremos se van moviendo o "deslizando", pero **siempre en la misma dirección**. Es decir, podemos comenzar por ejemplo con $A=B=0$, e incrementar cualquiera de ellos, a elección, en cada paso, pero **nunca** decrementarlos. Estos dos índices o punteros siempre avanzan: cuando se incrementa $A$, la ventana pierde un elemento por la izquierda, y cuando se incrementa $B$, la ventana gana un elemento por la derecha. Sobre todo en inglés y en sitios de programación competitiva, a veces se le llama a las técnicas de ventanas deslizantes "two-pointers", en referencia a las variables $A$ y $B$ que se mueven y apuntan siempre a los bordes de la ventana. Es muy común trabajar con datos almacenados en un cierto arreglo, de manera tal que la ventana deslizante se refiere a un cierto subarreglo del mismo en cada momento, y querer **mantener cierta información** sobre los datos en la ventana deslizante en todo momento. Por ejemplo, una de las cosas más fáciles de mantener es la suma de sus elementos: para esto basta con tener una variable ''sumaTotal'', inicialmente en 0, y actualizarla ante cada movimiento: cuando se agrega un elemento, se suma su valor a ''sumaTotal'', y cuando se pierde un elemento, se resta su valor a ''sumaTotal'', pudiendo así mover la ventana deslizante en $O(1)$ manteniendo su suma. El problema que trataremos en esta sección es el de mantener **el mínimo**((O el máximo, que es análogo intercambiando $<$ y $>$, e INF y -INF.)) de la ventana deslizante. El enfoque de utilizar una simple variable ya no sirve, porque no podemos "restar" en este caso, así que no tenemos manera de manejar eficientemente (sin recalcular desde 0) el caso en que se **saca** un elemento. Supondremos que al comenzar tenemos $A=B=0$, y tendremos que programar 3 operaciones: void avanzarA(); void avanzarB(); int minimoEnVentana(); Por ejemplo, si tenemos el siguiente arreglo: $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline \end{array}$$ Y ejecutamos la siguiente secuencia de movimientos de la ventana: avanzarB(); avanzarA(); avanzarB(); avanzarB(); avanzarB(); avanzarB(); avanzarB(); avanzarA(); avanzarA(); avanzarB(); La ventana se movería de la siguiente manera: $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline A=B=0 & & & & & & \\ \end{array} \mbox{, ventana vacía}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline \color{red}2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline A=0 & B=1 & & & & & \\ \end{array} \mbox{, mínimo=$2$}$$ ''avanzarA();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & 4 & 3 & 10 & 0\\ \hline & A=B=1 & & & & & \\ \end{array} \mbox{, ventana vacía}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red} 2 & 1 & 4 & 3 & 10 & 0\\ \hline & A=1 & B=2 & & & & \\ \end{array} \mbox{, mínimo=$2$}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & 4 & 3 & 10 & 0\\ \hline & A=1 & & B=3 & & & \\ \end{array} \mbox{, mínimo=$\color{red}1$}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red} 4 & 3 & 10 & 0\\ \hline & A=1 & & & B=4 & & \\ \end{array} \mbox{, mínimo=$1$}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & 10 & 0\\ \hline & A=1 & & & & B=5 & \\ \end{array} \mbox{, mínimo=$1$}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & \color{red}{10} & 0\\ \hline & A=1 & & & & & B=5 \\ \end{array} \mbox{, mínimo=$1$}$$ ''avanzarA();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & \color{red} 1 & \color{red}4 & \color{red}3 & \color{red}{10} & 0\\ \hline & & A=2 & & & & B=5 \\ \end{array} \mbox{, mínimo=$1$}$$ ''avanzarA();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & \color{red}4 & \color{red}3 & \color{red}{10} & 0\\ \hline & & & A=3 & & & B=5 \\ \end{array} \mbox{, mínimo=$\color{red}3$}$$ ''avanzarB();'' $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & 2 & 1 & \color{red}4 & \color{red}3 & \color{red}{10} & \color{red}0 & \\ \hline & & & A=3 & & & & B=6 \\ \end{array} \mbox{, mínimo=$\color{red}0$}$$ Llamaremos ''v'' al arreglo de números en cuestión: ''v=[2,2,1,4,3,10,0]''. ==== Implementación directa, recalculando el mínimo cada vez ==== La forma más directa posible de implementar estas operaciones es calculando el mínimo desde cero cada vez: void avanzarA() { A++; } void avanzarB() { B++; } int minimoEnVentana() { int mini = INF; for (int i = A; i < B; i++) mini = min(mini, v[i]); return mini; } En esta implementación, los ''avanzar'' son $O(1)$, pero obtener el mínimo es caro: cada operación tiene un costo $O(N)$. ==== Implementación utilizando set (multiset si hay repetidos) ==== Utilizando la estructura [[cpp-avanzado:set|multiset]]((Se puede utilizar ''set'' directamente si el arreglo no tiene ningún repetido)), podremos mejorar muchísimo el enfoque anterior. La idea es mantener en todo momento un ''multiset'' con todos los elementos de la ventana. Podemos declararlo por ejemplo con: multiset elementosEnVentana; La idea es que en todo momento, el multiset tenga todos los elementos de la ventana actual. De esta forma, cuando se avanza $A$ será necesario **borrar** ese elemento del multiset, y cuando se avance $B$ será necesario **agregar** un nuevo elemento al multiset. Al igual que set, multiset guarda sus elementos ordenados internamente, lo que nos permite acceder al mínimo con ''*elementosEnVentana.begin()''((Y podríamos acceder al máximo con ''*elementosEnVentana.rbegin()''.)). El código quedaría entonces: void avanzarA() { // Si hacemos simplemente elementosEnVentana.erase(v[A]) se borran TODAS las apariciones // de ese valor, pero queremos borrar una sola. elementosEnVentana.erase(elementosEnVentana.find(v[A])); A++; } void avanzarB() { elementosEnVentana.insert(v[B]); B++; } int minimoEnVentana() { if (A == B) return INF; // VENTANA VACIA!!! else return *elementosEnVentana.begin(); } Las tres operaciones tienen complejidad $O(\lg N)$, pues realizan $O(1)$ operaciones del multiset que tienen todas complejidad $O(\lg N)$. Se puede realizar otra implementación de la misma complejidad asintótica, pero más eficiente en los factores constantes, utilizando [[cpp-avanzado:priority-queue|priority_queue]] de la STL en lugar de multiset. Como no se pueden remover elementos arbitrarios de dicha estructura, habría que alterar un poco el código de ''minimoEnVentana'', para que vaya sacando elementos hasta encontrar un valor que siga en la ventana, pero la idea central sería la misma. ==== Implementación eficiente con deque ==== Veremos ahora una implementación muy elegante, que utiliza estructuras de datos mucho más sencillas (ya que si bien ya vienen programadas, ''set'' y ''multiset'' son en sí estructuras mucho más complejas que ''vector'' o ''deque''), y que realiza las 3 operaciones que queremos en $O(1)$. Para esto, utilizaremos la idea de identificar "elementos dominados", que es una idea muy útil en muchos problemas y no solo en este. === Idea de elementos dominados === Supongamos que tenemos una situación como la del paso $A=1, B=5$ del ejemplo anterior: $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & 10 & 0\\ \hline & A=1 & & & & B=5 & \\ \end{array} \mbox{, mínimo=$1$}$$ En este caso, los elementos de nuestra ventana resultan ser ''[2,1,4,3]'', **en ese orden**. La pregunta que podemos hacernos, dada la situación actual, es la siguiente: ¿Cuáles de estos elementos tienen oportunidad de convertirse en el mínimo de la ventana **en algún momento**? Nuestro objetivo final es calcular el mínimo de la ventana **en todo momento**, pero si de alguna manera podemos asegurar que un elemento ya no podrá ser el mínimo jamás, podemos ignorarlo completamente, ya que ese elemento no nos interesa. Si analizamos esta ventana ''[2,1,4,3]'' con cuidado, podemos concluir que los únicos elementos importantes son 1 y 3: los elementos 2 y 4 de esta ventana **ya nunca podrán ser el mínimo de la ventana**. ¿Por qué esto es así? Por un lado, el mínimo es actualmente 1, que es menor que 2. Eso hace que, hasta que ese 1 no se vaya de la ventana, 2 no tenga ninguna oportunidad de convertirse en el mínimo. Pero **ese 1 está a la derecha del 2**: por lo tanto, como todos los elementos se van sacando de la ventana siempre por el lado izquierdo, resulta que **el 2 se va de la ventana antes que el 1**. Resumiendo: desde ahora hasta que el 2 se vaya de la ventana, el 1, que es mejor, siempre estará presente en la ventana, y por lo tanto **lo domina completamente**. No es necesario en absoluto considerar ese 2, porque siempre será mejor opción el 1. Esto ocurrió porque tenemos en la ventana un número 1, **que es menor o igual** que el número 2, y **está a su derecha**. Siempre que tengamos un número menor o igual a nuestra derecha, "no somos un número importante", puesto que el otro es "al menos tan bueno como nosotros", pero "nosotros nos vamos antes". La observación del párrafo anterior nos lleva a definir un elemento como //dominado//, cuando tiene otro a su derecha que es menor o igual. La idea es la que comentamos antes: Un elemento dominado tiene otro que es siempre mejor opción, así que se puede ignorar en favor del otro que lo domina. A los elementos que no son dominados por ningún otro, para ponerles algún nombre, los llamaremos los elementos //dominantes//. La idea será guardar únicamente los elementos dominantes de la ventana, es decir, aquellos que no tengan a su derecha ningún elemento menor o igual. En nuestra ventana de ejemplo, los elementos dominantes son el 1 y el 3. Observemos que el elemento de la derecha de todo de la ventana **siempre es dominante**: Ya que no tiene ningún elemento a su derecha, y por lo tanto nadie puede dominarlo. Esto es lógico, ya que si a partir de ahora hiciéramos todo ''avanzarA'', quedaría ese elemento solo, y se llegaría a convertir en el mínimo, que es algo que no debería nunca pasarle a un dominado. Por ejemplo, si la ventana contuviera en algún momento los valores ''[3,4,2,3,4,7,5,10,11,9]'', podemos encontrar los siguientes dominados: * El primer 3 es dominado por el 2 * El primer 4 es dominado por el 2 * El 7 es dominado por el 5 * El 10 y el 11 son dominados por el 9 Al dejar solo los dominantes, nos quedarían (en orden) los elementos ''[2,3,4,5,9]''. ¿Tiene algo de especial esta lista? Sí: todos sus elementos se encuentran en orden estrictamente creciente. Esta es una de las cosas buenas que tiene la eliminación de dominados: generalmente, cuando nos quedamos solamente con los elementos dominantes, ese conjunto resultante tendrá cierto orden o propiedad particular. En este problema, lo que ocurre es que los elementos dominantes tienen que estar sí o sí en orden creciente estricto: Si $x$ estuviera antes que $y$, pero $x \geq y$, entonces $y$ dominaría a $x$, y no podrían ser ambos dominantes. Si $x$ viene antes que $y$ pero $y$ no lo domina, tiene que ser necesariamente $x < y$. Nuestro plan es entonces guardar todo el tiempo **los índices** del arreglo en donde se encuentran los elementos dominantes de la ventana actual, de izquierda a derecha. Notar que si tenemos los índices, tenemos también los elementos ya que el elemento en el lugar $i$ es $v[i]$. Como ya habíamos dicho, los únicos elementos que importan a la hora de buscar el mínimo son los dominantes, y esos de hecho están ordenados crecientemente, por lo tanto **el mínimo de la ventana siempre es el primer elemento dominante**, lo que llamaremos ''dominantes[0]''. ¿Cómo se ve afectada nuestra lista de dominantes al ''avanzarA''? En este caso, se va un único elemento de la ventana, a la izquierda de todo. Hay dos posibilidades: si ese elemento era dominado, entonces absolutamente nada cambia. Si en cambio ese elemento era dominante, era necesariamente el primer dominante, y hay que eliminarlo de la lista. Podemos distinguir ambos casos mirando el índice, ya que el elemento que se va es el de índice $A$: si ''dominantes[0] == A'', hay que borrar dominantes[0], y sino no. Para poder borrar (e insertar) elementos de cualquiera de los dos extremos, guardaremos la lista de índices de los dominantes en un [[cpp-avanzado:deque|deque]], que declaramos con ''deque dominantes;''. Finalmente, lo único que falta es ver cómo resolver el ''avanzarB''. En este caso, **se agrega** un único elemento **al final** de la ventana, en el índice $B$ del arreglo ''v''. Como ya habíamos notado antes, este último elemento de la ventana siempre es dominante, o sea que sí o sí lo vamos a agregar con ''dominantes.push_back(B)''. Pero antes de eso, ¡hay que **borrar** todos los posibles elementos dominados que se generan! Por ejemplo, supongamos que en la misma ventana que teníamos antes (con los dominantes marcados en verde): $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{green} 1 & \color{red}4 & \color{green}3 & 10 & 0\\ \hline & A=1 & & & & B=5 & \\ \end{array} \mbox{, mínimo=$1$}$$ Realizamos la operación ''avanzarB'': $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{green} 1 & \color{red}4 & \color{green}3 & \color{green}{10} & 0\\ \hline & A=1 & & & & & B=6 \\ \end{array} \mbox{, mínimo=$1$}$$ En este caso, se agrega el 10 al final como nuevo dominante, pero ninguno de los anteriores cambia, porque el 10 no domina a nadie. Sin embargo, tras realizar otro ''avanzarB'': $$\begin{array}{|c|c|c|c|c|c|c|} \hline 2 & \color{red}2 & \color{red} 1 & \color{red}4 & \color{red}3 & \color{red}{10} & \color{green}{0} & \\ \hline & A=1 & & & & & & B=0 \\ \end{array} \mbox{, mínimo=$0$}$$ ¡**Todos** los elementos que había antes quedan dominados por el 0! Entonces, para procesar el ''avanzarB'' debemos sacar de ''dominantes'' todos los elementos que queden dominados por el elemento en la posición $B$, es decir, todos los que sean mayores o iguales que ''v[B]''. Como los dominantes están siempre ordenados, estos elementos que hay que borrar **están todos al final** de la lista de dominantes. Por lo tanto, podemos ir haciendo ''dominantes.pop_back()'' continuamente, mientras el ''dominantes.back()'' sea el índice de un elemento que queda dominado por el de la posición $B$. Lo anterior describe absolutamente todas las ideas de esta implementación. Recomendamos intentar programarla por uno mismo antes de mirar el código de ejemplo que sigue, como práctica de programación. === Implementación === deque dominantes; int A=0, B=0; void avanzarA() { // Solo cambia algo si el que sacamos no estaba dominado. if (dominantes.front() == A) dominantes.pop_front(); A++; } void avanzarB() { while (!dominantes.empty() && v[dominantes.back()] >= v[B]) dominantes.pop_back(); dominantes.push_back(B); B++; } int minimoEnVentana() { if (A == B) return INF; // VENTANA VACIA!!! else return v[dominantes.front()]; // dominantes.front() nos dice el indice } === Complejidad === Salvo la operación de ''avanzarB'', todas las demás realizan $O(1)$ operaciones $O(1)$, así que son de tiempo constante. La complejidad de todas las operaciones resulta ser $O(1)$ amortizado, [[algoritmos-oia:analisis-amortizado#ejemplopila_con_eliminacion_multiple|por exactamente la misma razón que en el ejemplo de pila con eliminación múltiple]]: lo único "caro" en ''avanzarB'' es el ''while'' para ir borrando los elementos dominados, pero cada elemento del arreglo original se puede borrar una única vez, y por lo tanto la complejidad total del algoritmo resultará ser $O(N)$, con lo cual el costo promedio por operación fue $O(1)$. ==== Problemas de aplicación ==== Ordenados en orden creciente de dificultad (subjetivamente): * [[https://leetcode.com/problems/sliding-window-maximum/description| Sliding Window RMQ]] * [[http://wcipeg.com/problem/smac081p3| Jumpscotch]] * [[http://juez.oia.unsam.edu.ar/#/task/fila/statement| Fila]] * [[https://coj.uci.cu/24h/problem.xhtml?pid=3568 | Pyramid]]