Painting the Barn

Pista 1

Digamos que FJ solo pudiera pintar un rectángulo de pintura sobre el establo. Entonces, este problema se convertiría en hallar la suma máxima de una submatriz .

Pista 2

Así que ya tienes tu un rectángulo. ¿Cómo haces que este algoritmo funcione para dos?

Hay que pensar cómo se pueden garantizar rectángulos disjuntos.

Respuesta a la pista 2

Si dos rectángulos son disjuntos, siempre puede haber una recta horizontal o vertical que los separe.

Solución

Análisis oficial (C++)

Explicación

Observaciones iniciales

Empezamos calculando las capas de pintura sobre cada celda del establo con sumas de prefijos, pero a partir de ahí es un poco difícil determinar qué capas pintar. Es difícil calcularlo directamente desde este arreglo, pero notemos que hay dos estados generales en los que puede estar una celda.

Si se pinta encima, o bien suma $1$ al área óptima (porque inicialmente tiene $K-1$ capas de pintura) o resta $1$ del área óptima (porque ya tiene $K$ capas de pintura).
No pasará nada al área óptima si se pinta encima.

Como FJ debe pintar dos rectángulos disjuntos, no tenemos que considerar las celdas que necesitan dos capas de pintura para volverse óptimas.

Llamemos a este arreglo $\texttt{leftovers}$ . Con nuestra entrada de ejemplo, se vería así (está reducido: el arreglo real siempre será una matriz $200\times200$ ):


     0   1   2   3   4   5   6   7   8   9
0  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
1  [ 0,  1,  1,  1,  0,  0,  0,  0,  0,  0]
2  [ 0,  1, -1, -1,  1,  1,  1,  1,  0,  0]
3  [ 0,  1, -1,  0, -1, -1, -1,  1,  0,  0]
4  [ 0,  0,  1, -1, -1, -1, -1,  1,  0,  0]
5  [ 0,  0,  1, -1, -1, -1, -1,  1,  0,  0]
6  [ 0,  0,  1,  1,  1,  1,  1,  1,  0,  0]
7  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
8  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]
9  [ 0,  0,  0,  0,  0,  0,  0,  0,  0,  0]

Usando Kadane

Ahora redujimos este problema a hallar la suma máxima de submatriz en una matriz, dado que podemos tener dos submatrices disjuntas. Aunque es una tarea ambiciosa, intentemos abordarla de a poco, primero considerando si solo hay 1 matriz que podemos pintar.

Para eso, usamos una versión 2D del algoritmo de Kadane .

La versión 1D $\mathcal{O}(N)$ se puede implementar con el siguiente código:

C++JavaPython


int max_subarray(const vector<int> &arr) {
	int best_sum = 0;
	int curr_sum = 0;
	for (int i : arr) {
		curr_sum = max(curr_sum + i, 0);
		best_sum = max(best_sum, curr_sum);
	}
	return best_sum;
}


public static int maxSubarray(int[] arr) {
	int bestSum = 0;
	int currSum = 0;
	for (int i : arr) {
		currSum = Math.max(currSum + i, 0);
		bestSum = Math.max(bestSum, currSum);
	}
	return bestSum;
}


def max_subarray(arr: List[int]) -> int:
	curr_sum = 0
	best_sum = 0
	for i in arr:
		curr_sum = max(curr_sum + i, 0)
		best_sum = max(best_sum, curr_sum)
	return best_sum

Podemos extender esto a la segunda dimensión (aunque con un factor extra $N^2$ en la complejidad) iterando sobre todos los rangos de columnas de la matriz y ejecutando un Kadane 1D sobre el arreglo donde cada elemento es la suma del subarreglo del rango de columnas de una fila.

Por ejemplo, si nuestro rango de columnas actual fuera $[0,2]$ , entonces ejecutaríamos nuestro Kadane 1D sobre el siguiente arreglo:

[0,2,0,0,1,1,1,0,0,0]

El primer elemento del arreglo es la suma del subarreglo de la fila $0$ en el rango de columnas $[0, 2]$ (es decir, $0 + 0 + 0 = 0$ ), el segundo elemento es la suma del subarreglo de la fila $1$ en el rango de columnas $[0, 2]$ (es decir, $0 + 1 + 1 = 2$ ), el tercer elemento es la suma del subarreglo de la fila $2$ en el rango de columnas $[0, 2]$ (es decir, $0 + 1 + (-1) = 0$ ), etc.

Resolviendo la segunda matriz

La clave para obtener el máximo con dos submatrices es notar que siempre habrá una recta, vertical u horizontal, que puede dividir la grilla de modo que un rectángulo quede en una sección y el otro en la otra.

A partir de esta observación, podemos recorrer todas las rectas que podemos trazar a través de la matriz y obtener el subarreglo máximo de ambos lados. Después de esto, podemos tomar el máximo de los resultados de estas rectas y sumarlo al número de celdas que inicialmente estaban pintadas con el número óptimo de capas de pintura para obtener nuestra respuesta final.

Necesitamos un método para calcular de forma eficiente las submatrices máximas de todas las regiones partidas. Para empezar, definamos cuatro arreglos que tendrán los siguientes valores iniciales:

$\texttt{top\\_best[i]}$ : la mejor matriz cuyo lado inferior es la fila $i$ .
$\texttt{bottom\\_best[i]}$ : la mejor matriz cuyo lado superior es la fila $i$ .
$\texttt{left\\_best[i]}$ : la mejor matriz cuyo lado derecho es la columna $i$ .
$\texttt{right\\_best[i]}$ : la mejor matriz cuyo lado izquierdo es la columna $i$ .

Llenamos estos arreglos ejecutando un Kadane 2D empezando desde arriba, abajo, izquierda o derecha, y actualizando los arreglos correspondientes con el valor de la submatriz máxima.

Luego, hacemos un máximo acumulado desde el inicio o desde el final según el arreglo para obtener los arreglos con los siguientes valores actualizados:

$\texttt{top\\_best[i]}$ : la mejor matriz que queda en o por encima de la fila $i$ .
$\texttt{bottom\\_best[i]}$ : la mejor matriz que queda en o por debajo de la fila $i$ .
$\texttt{left\\_best[i]}$ : la mejor matriz que está en o a la izquierda de la columna $i$ .
$\texttt{right\\_best[i]}$ : la mejor matriz que está en o a la derecha de la columna $i$ .

Implementación

Complejidad temporal: $\mathcal{O}(\max(x,y)^3)$

C++Java


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::max;
using std::vector;
 
const int WIDTH = 200;
 
int main() {
	std::ifstream read("paintbarn.in");
	int rect_num;
	int optimal_amt;
	read >> rect_num >> optimal_amt;
 
	vector<vector<int>> barn(WIDTH, vector<int>(WIDTH));
	for (int r = 0; r < rect_num; r++) {
		int x1, y1, x2, y2;
		read >> x1 >> y1 >> x2 >> y2;
		for (int y = y1; y < y2; y++) {
			barn[y][x1]++;
			if (x2 < WIDTH) { barn[y][x2]--; }
		}
	}
 
	for (int r = 0; r < WIDTH; r++) {
		int so_far = 0;
		for (int c = 0; c < WIDTH; c++) {
			so_far += barn[r][c];
			barn[r][c] = so_far;
		}
	}
 
	/*
	 * leftovers[r][c] = si pintamos la celda ahí,
	 * da el cambio en el tamaño óptimo de pintura
	 */
	vector<vector<int>> leftovers(WIDTH, vector<int>(WIDTH));
	int rn_amt = 0;
	for (int r = 0; r < WIDTH; r++) {
		for (int c = 0; c < WIDTH; c++) {
			if (barn[r][c] == optimal_amt) {
				leftovers[r][c] = -1;
				rn_amt++;
			} else if (barn[r][c] == optimal_amt - 1) {
				leftovers[r][c] = 1;
			}
		}
	}
 
	// creamos un arreglo de sumas de prefijos para consultar fácil en 2D el arreglo leftovers
	vector<vector<int>> pref_leftovers(WIDTH + 1, vector<int>(WIDTH + 1));
	for (int r = 1; r < WIDTH + 1; r++) {
		for (int c = 1; c < WIDTH + 1; c++) {
			pref_leftovers[r][c] =
			    (pref_leftovers[r - 1][c] + pref_leftovers[r][c - 1] -
			     pref_leftovers[r - 1][c - 1] + leftovers[r - 1][c - 1]);
		}
	}
 
	// devuelve la suma de leftovers[from_r][from_c] a leftovers[to_r][to_c]
	auto rect_sum = [&](int from_r, int from_c, int to_r, int to_c) {
		return (pref_leftovers[to_r + 1][to_c + 1] - pref_leftovers[from_r][to_c + 1] -
		        pref_leftovers[to_r + 1][from_c] + pref_leftovers[from_r][from_c]);
	};
 
	vector<int> top_best(WIDTH), bottom_best(WIDTH), left_best(WIDTH),
	    right_best(WIDTH);
	// iteramos sobre todos los pares de columnas y filas para el Kadane 2D
	for (int start = 0; start < WIDTH; start++) {
		for (int end = start; end < WIDTH; end++) {
			int top_sum = 0;
			int left_sum = 0;
			int rect;
			for (int i = 1; i < WIDTH; i++) {
				rect = top_sum + rect_sum(i - 1, start, i - 1, end);
				top_best[i] = max(top_best[i], top_sum = max(0, rect));
 
				rect = left_sum + rect_sum(start, i - 1, end, i - 1);
				left_best[i] = max(left_best[i], left_sum = max(0, rect));
			}
 
			int bottom_sum = 0;
			int right_sum = 0;
			for (int i = WIDTH - 1; i >= 1; i--) {
				rect = bottom_sum + rect_sum(i, start, i, end);
				bottom_best[i] = max(bottom_best[i], bottom_sum = max(0, rect));
 
				rect = right_sum + rect_sum(start, i, end, i);
				right_best[i] = max(right_best[i], right_sum = max(0, rect));
			}
		}
	}
 
	// ejecutamos una operación de máximo acumulado sobre estos arreglos
	for (int i = 1; i < WIDTH; i++) {
		top_best[i] = max(top_best[i], top_best[i - 1]);
		left_best[i] = max(left_best[i], left_best[i - 1]);
	}
	for (int i = WIDTH - 2; i >= 0; i--) {
		bottom_best[i] = max(bottom_best[i], bottom_best[i + 1]);
		right_best[i] = max(right_best[i], right_best[i + 1]);
	}
 
	// y por último recorremos todas las rectas para la mejor combinación
	int max_paintable = 0;
	for (int i = 0; i < WIDTH; i++) {
		max_paintable = max(max_paintable, top_best[i] + bottom_best[i]);
		max_paintable = max(max_paintable, left_best[i] + right_best[i]);
	}
 
	std::ofstream("paintbarn.out") << rn_amt + max_paintable << endl;
}


import static java.lang.Math.max;
 
import java.io.*;
import java.util.*;
 
public final class PaintBarn {
	static final int WIDTH = 200;
 
	static int[][] prefLeftovers;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("paintbarn.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int rectNum = Integer.parseInt(initial.nextToken());
		int optimalAmt = Integer.parseInt(initial.nextToken());
		int[][] barn = new int[WIDTH][WIDTH];
		for (int r = 0; r < rectNum; r++) {
			int[] rect = Arrays.stream(read.readLine().split(" "))
			                 .mapToInt(Integer::parseInt)
			                 .toArray();
			for (int y = rect[1]; y < rect[3]; y++) {
				barn[y][rect[0]]++;
				if (rect[2] < WIDTH) { barn[y][rect[2]]--; }
			}
		}
		for (int r = 0; r < WIDTH; r++) {
			int soFar = 0;
			for (int c = 0; c < WIDTH; c++) {
				soFar += barn[r][c];
				barn[r][c] = soFar;
			}
		}
 
		/*
		 * leftovers[r][c] = si pintamos la celda ahí,
		 * da el cambio en el tamaño óptimo de pintura
		 */
		int[][] leftovers = new int[WIDTH][WIDTH];
		int rnAmt = 0;
		for (int r = 0; r < WIDTH; r++) {
			for (int c = 0; c < WIDTH; c++) {
				if (barn[r][c] == optimalAmt) {
					leftovers[r][c] = -1;
					rnAmt++;
				} else if (barn[r][c] == optimalAmt - 1) {
					leftovers[r][c] = 1;
				}
			}
		}
 
		// creamos un arreglo de sumas de prefijos para consultar fácil en 2D el arreglo leftovers
		prefLeftovers = new int[WIDTH + 1][WIDTH + 1];
		for (int r = 1; r < WIDTH + 1; r++) {
			for (int c = 1; c < WIDTH + 1; c++) {
				prefLeftovers[r][c] =
				    (prefLeftovers[r - 1][c] + prefLeftovers[r][c - 1] -
				     prefLeftovers[r - 1][c - 1] + leftovers[r - 1][c - 1]);
			}
		}
 
		int[] topBest = new int[WIDTH];
		int[] bottomBest = new int[WIDTH];
		int[] leftBest = new int[WIDTH];
		int[] rightBest = new int[WIDTH];
		// iteramos sobre todos los pares de columnas y filas para el Kadane 2D
		for (int start = 0; start < WIDTH; start++) {
			for (int end = start; end < WIDTH; end++) {
				int topSum = 0;
				int leftSum = 0;
				int rect;
				for (int i = 1; i < WIDTH; i++) {
					rect = topSum + rectSum(i - 1, start, i - 1, end);
					topBest[i] = max(topBest[i], topSum = max(0, rect));
 
					rect = leftSum + rectSum(start, i - 1, end, i - 1);
					leftBest[i] = max(leftBest[i], leftSum = max(0, rect));
				}
 
				int bottomSum = 0;
				int rightSum = 0;
				for (int i = WIDTH - 1; i >= 1; i--) {
					rect = bottomSum + rectSum(i, start, i, end);
					bottomBest[i] = max(bottomBest[i], bottomSum = max(0, rect));
 
					rect = rightSum + rectSum(start, i, end, i);
					rightBest[i] = max(rightBest[i], rightSum = max(0, rect));
				}
			}
		}
 
		// ejecutamos una operación de máximo acumulado sobre estos arreglos
		for (int i = 1; i < WIDTH; i++) {
			topBest[i] = max(topBest[i], topBest[i - 1]);
			leftBest[i] = max(leftBest[i], leftBest[i - 1]);
		}
		for (int i = WIDTH - 2; i >= 0; i--) {
			bottomBest[i] = max(bottomBest[i], bottomBest[i + 1]);
			rightBest[i] = max(rightBest[i], rightBest[i + 1]);
		}
 
		// y por último recorremos todas las rectas para la mejor combinación
		int maxPaintable = 0;
		for (int i = 0; i < WIDTH; i++) {
			maxPaintable = max(maxPaintable, topBest[i] + bottomBest[i]);
			maxPaintable = max(maxPaintable, leftBest[i] + rightBest[i]);
		}
 
		PrintWriter written = new PrintWriter("paintbarn.out");
		written.println(rnAmt + maxPaintable);
		written.close();
	}
 
	// devuelve la suma de leftovers[from_r][from_c] a leftovers[to_r][to_c]
	static int rectSum(int fromR, int fromC, int toR, int toC) {
		return (prefLeftovers[toR + 1][toC + 1] - prefLeftovers[fromR][toC + 1] -
		        prefLeftovers[toR + 1][fromC] + prefLeftovers[fromR][fromC]);
	}
}