Pond

Pista

Hay que hallar una formulación para comprobar si la mediana de un cuadrado $K \times K$ es menor o igual que $M$ .

Explicación

Solución

Para resolver este problema, hacemos búsqueda binaria sobre la respuesta. Para un valor dado $M$ , preguntamos si existe una región $K \times K$ cuya mediana es menor o igual que $M$ . Según las respuestas a estas preguntas, actualizamos el rango de la búsqueda binaria y calculamos la mediana más baja entre todos los parques.

Ahora nos concentramos en cómo comprobar de forma eficiente si existe tal cuadrado $K \times K$ . Construimos un arreglo $Q$ en el que cada casilla $(i, j)$ tiene $Q_{i, j}=1$ si $A_{i, j} \le M$ y $Q_{i, j}=-1$ en caso contrario. Como se muestra en el módulo de sumas de prefijos 2D, podemos calcular las sumas de prefijos 2D de $Q$ y usarlas para determinar de forma eficiente si las casillas $(i, j)$ que cumplen $A_{i, j} \le M$ forman una mayoría dentro de alguna región $K \times K$ .

Sea $P_{i , j}$ la suma de las entradas en la región de $(1, 1)$ a $(i, j)$ . Entonces, la suma de una región $K \times K$ con esquina inferior derecha en $(i, j)$ sería

P_{i, j} - P_{i - k, j} - P_{i, j - k} + P_{i - k, j - k}.

Como cada entrada con valor a lo sumo $M$ contribuye $1$ y $-1$ en caso contrario, la suma representa la cantidad de casillas con valor menor o igual que $M$ menos la cantidad de casillas cuyo valor es mayor que $M$ dentro de la región.

Si alguna región $K \times K$ tiene suma neta mayor o igual que $0$ , entonces es posible una mediana de a lo sumo $M$ , y la prueba fue exitosa. En caso contrario, hay que considerar valores más grandes de $M$ en la búsqueda binaria.

Implementación

Complejidad temporal: $\mathcal{O}(N^2\log(\max A_{i}))$

Código de la solución

C++


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, k;
	cin >> n >> k;
 
	vector<vector<int>> a(n, vector<int>(n));
	vector<vector<int>> p(n + 1, vector<int>(n + 1));
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { cin >> a[i][j]; }
	}
 
	int lo = 0, hi = 1e9;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
 
		// Construimos el arreglo de prefijos 2D
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
				p[i][j] += (a[i - 1][j - 1] <= mid) ? 1 : -1;
			}
		}
 
		// Calculamos las regiones K x K
		bool found = false;
		for (int i = k; i <= n; i++) {
			for (int j = k; j <= n; j++) {
				int vl = p[i][j] - p[i - k][j] - p[i][j - k] + p[i - k][j - k];
				if (vl >= 0) {
					found = true;
					break;
				}
			}
			if (found) break;
		}
 
		if (found) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}
 
	cout << lo << '\n';
}