Skip to Content
CTRL K

Garden

Análisis oficial 

Explicación

Notar que entre cualesquiera dos rectángulos disjuntos, podemos dibujar una línea vertical u horizontal entre esos dos rectángulos. Podemos considerar cada línea vertical y horizontal posible, y hallar los dos mejores rectángulos entre las líneas.

Consideremos primero cada línea vertical. Fijemos las dos filas de nuestro rectángulo. Si podemos calcular el mejor perímetro de rectángulo para cada prefijo y sufijo de nuestras columnas disponibles, podemos hallar nuestra respuesta barriendo el punto de corte. La implementación de abajo itera sobre la columna derecha y luego usa dos punteros para hallar la mejor columna izquierda. Se puede aplicar una lógica similar para hallar el mejor resultado para cada línea horizontal.

Implementación

Complejidad temporal: O(l2w+w2l)\mathcal{O}(l^{2}w + w^{2}l)

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int l, w;
	cin >> l >> w;
	int n, k;
	cin >> n >> k;
	vector<vector<int>> grid(l + 1, vector<int>(w + 1));
	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		grid[x][y]++;
	}
 
	// usamos 1e9 como INF para evitar overflow en la línea 66
	const int INF = 1e9;
	int res = INF;
	/*
	 * Primero calculamos la respuesta para cada línea vertical posible,
	 * luego rotamos la grilla y hacemos el mismo cálculo para obtener
	 * la respuesta para cada línea horizontal.
	 */
	for (int _ = 0; _ < 2; _++) {
		vector<int> pref_min(w + 1, INF);
		vector<int> suff_min(w + 1, INF);
		for (int row_1 = 1; row_1 <= l; row_1++) {
			vector<int> col_sum(w + 1);
			for (int row_2 = row_1; row_2 <= l; row_2++) {
				int ptr = 0;
				int rect_sum = 0;
				for (int col = 1; col <= w; col++) {
					col_sum[col] += grid[row_2][col];
					rect_sum += col_sum[col];
 
					// seguir moviendo la columna izquierda hasta que rect_sum < k
					// luego, compensamos para que la suma >= k al final
					while (rect_sum >= k) {
						rect_sum -= col_sum[ptr++];
						if (rect_sum < k) {
							rect_sum += col_sum[--ptr];
							break;
						}
					}
 
					if (rect_sum == k) {
						// actualizar los arreglos de mínimo de prefijo y sufijo
						int perimeter = 2 * (row_2 - row_1 + 1 + col - ptr + 1);
						pref_min[col] = min(pref_min[col], perimeter);
						suff_min[ptr] = min(suff_min[ptr], perimeter);
					}
				}
			}
		}
 
		// calcular mínimos de prefijo y sufijo
		for (int i = 2; i <= w; i++) {
			pref_min[i] = min(pref_min[i], pref_min[i - 1]);
		}
		for (int i = w - 1; i >= 1; i--) {
			suff_min[i] = min(suff_min[i], suff_min[i + 1]);
		}
 
		// barrer un punto de corte entre nuestros dos rectángulos
		for (int i = 2; i <= w; i++) { res = min(res, pref_min[i - 1] + suff_min[i]); }
 
		vector<vector<int>> rotated_grid(w + 1, vector<int>(l + 1));
		for (int i = 1; i <= l; i++) {
			for (int j = 1; j <= w; j++) { rotated_grid[j][i] = grid[i][j]; }
		}
		grid = move(rotated_grid);
		swap(l, w);
	}
 
	if (res < INF) {
		cout << res << endl;
	} else {
		cout << "NO" << endl;
	}
}
Fundamentos