Divide & Conquer
Primero que nada, vamos a asumir que la cantidad de osos es potencia de 2. Implementativamente, podemos llenar con 0’s al final de la fila (que es menor que la cota inferior de las alturas) hasta que sea potencia de 2.
Supongamos que tenemos dos arreglos contiguos de tamaño 2^k, para los cuales conocemos la respuesta. Queremos generar la respuesta que se obtiene al tener el arreglo de tamaño 2^{k+1}, dado por la concatenación de los dos arreglos originales.
Notemos que al conocer la respuesta en cada mitad, podemos dar (para cada mitad) la respuesta al problema con tamaños de grupos hasta 2^k. Queremos usar esa información para obtener la respuesta en el arreglo grande.
Para ello, vamos a separar en dos casos, según el tamaño del grupo por el que respondemos. Primero veamos qué ocurre en casos pequeños.
CASO 1: (Tamaño de grupo menor o igual que 2^k)
-
Si el tamaño de grupo es 1: La respuesta en el arreglo grande es el máximo entre las respuestas para tamaños 1 de cada mitad
-
Si el tamaño de grupo es 2: La respuesta en el arreglo grande es el máximo entre:
- Las respuestas para tamaños 2 de cada mitad
- El mínimo para todos los arreglos de tamaño 2 que tengan al menos un elemento en cada mitad.
-
…
-
Si el tamaño de grupo es x: La respuesta en el arreglo grande es el máximo entre:
- Las respuestas para tamaños x de cada mitad
- El mínimo para todos los arreglos de tamaño x que tengan al menos un elemento en cada mitad.
Está claro que esto sirve para todos los tamaños de grupo menores o iguales que 2^k.
CASO 2: (Tamaño de grupo mayor que 2^k)
En este caso no nos sirven las respuestas que tenemos sobre cada mitad, por lo tanto necesitamos simplemente calcular:
- Si el tamaño de grupo es x: La respuesta en el arreglo grande es el máximo entre:
2. El mínimo entre todos los arreglos de tamaño x que tengan al menos un elemento en cada mitad.
Entonces, la clave radica en cómo calculamos los últimos puntos en cada caso.
La cantidad de subarreglos de tamaño x que cruzan entre mitades es x - 1, por lo tanto en total hay \mathcal{O}(n^2) subarreglos, y calcular el mínimo en cada uno de ellos llevaría una pasada lineal (O no, podríamos evitarlo si hacemos “Sliding Window RMQ”, para cada largo x). De todas formas, mirar todos los subarreglos no es una opción si queremos una solución subcuadrática.
Por lo tanto, vamos dar la respuesta al segundo punto para todos los largos con una pasada lineal en el arreglo. La respuesta para largo 2 es trivial, pues solo hay una opción. La idea será ir incrementalmente generando la respuesta para largo 3, 4, 5, … etc.
Si ya tenemos la respuesta de largo x, podemos extenderla alguno de sus dos vecinos. Si queremos maximizar el mínimo en el subarreglo, debemos extenderla hacia el lado del número vecino más grande (pensar por qué).
Idea
Si tenemos una solución de largo x+1 que utiliza al vecino más pequeño de lo que estamos generando, la que obtenemos con el procedimiento es mejor o igual.
Con esto resuelto, se termina el problema.
Ejemplo (Merge y Problema)
Ojo, Siempre para responder los subarreglos que cruzan la frontera miramos el arreglo original.
Código
#include <iostream>
#include <vector>
#define forn(i,n) for(int i=0;i<(int)(n); i++)
#define forsn(i,s,n) for(int i=(s);i<(int)(n); i++)
using namespace std;
const int INFINITO = 2e9;
int main()
{
int n;
while (cin >> n)
{
int q = 1, pasos = 0;
while (q < n)
{
q *= 2;
pasos++;
}
vector<int> a (q,0), ans (q,0);
// LEEMOS ENTRADA
forn(i,n)
{
cin >> a[i];
ans[i] = a[i];
}
int bloque = 2;
forn(p,pasos)
{
forn(i,q/bloque)
{
int izq = i*bloque, der = (i+1)*bloque-1; // primer y ultimo indice del bloque en el arreglo (inclusive)
int l = (izq + der) / 2, r = (izq + der) / 2 + 1; // indices de los dos numeros en la frontera
int mini = min(a[l],a[r]), tam = 1; // tamanho del segmento formado
ans[izq] = max(ans[izq],ans[izq+bloque/2]); // tamanho 1 por separado
forsn(j,izq+1,der+1)
{
if (tam >= bloque / 2 ) // CASO 2
ans[j] = mini;
else
ans[j] = max(mini,max(ans[j],ans[j+bloque/2])); // CASO 1
// CHEQUEAMOS HACIA DONDE EXPANDIRSE
int left = 0, right = 0;
if (l-1 >= 0)
left = a[l-1];
if (r+1 < q)
right = a[r+1];
if (left > right)
l--;
else if (right > 0)
r++;
mini = min(mini,min(a[l],a[r]));
tam++;
}
}
bloque *= 2;
}
// IMPRIMIR SALIDA
forn(i,n)
{
if (i)
cout << " ";
cout << ans[i];
}
cout << "\n";
}
return 0;
}
(?). Como el Foro es en español, voy a ponerlo en español, igual dejo el link.
).