Modern Art

Explicación

Observación inicial

Hay solo una observación pequeña que deberíamos hacer antes de continuar con el problema en sí, y es que, dado el lienzo final, es óptimo asumir que cada color ocupa solo el rectángulo mínimo necesario para cubrir las celdas que se muestran.

Por ejemplo, si solo estas celdas azules están presentes en el lienzo:

Es mejor pensar que este es el rectángulo que pintó Picowso:

Análisis

El problema principal es hallar qué rectángulos deben superponerse a otros rectángulos, porque mientras sepamos que el color A se superpone al color B, el color A no puede haber sido pintado primero.

Sin embargo, no podemos recorrer todos los pares de colores, ya que eso daría una complejidad de al menos $\mathcal{O}(N^4)$ . Como eso descarta considerar las cosas desde el ángulo de los colores, ¿por qué no intentar considerarlas desde el ángulo de cada celda del lienzo?

Dada la observación que hicimos, conocemos la caja envolvente de cada rectángulo. Así, con sumas de prefijos, es posible determinar cuántos rectángulos se pintaron sobre una sola celda.

Con esto, podemos construir nuestra respuesta con el hecho de que si una celda tiene más de 2 rectángulos pintados encima, entonces el color mostrado en la pintura dada no puede haber sido pintado primero. Así, mantenemos un conjunto de todos los colores mostrados y lo actualizamos en consecuencia, quitando un color que se encuentra superpuesto a algún otro color. Todos los colores no mostrados en el lienzo final podrían haber sido pintados primero.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++JavaPython


#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
struct Bound {
	int min_r, max_r, min_c, max_c;
};
 
int main() {
	std::ifstream read("art.in");
 
	int width;
	read >> width;
	vector<vector<int>> canvas(width, vector<int>(width));
	std::map<int, Bound> visible;
	for (int r = 0; r < width; r++) {
		for (int c = 0; c < width; c++) {
			read >> canvas[r][c];
			if (!visible.count(canvas[r][c])) {
				visible[canvas[r][c]] = Bound{r, r, c, c};
			}
			Bound &bounds = visible[canvas[r][c]];
			bounds.min_r = std::min(r, bounds.min_r);
			bounds.max_r = std::max(r, bounds.max_r);
			bounds.min_c = std::min(c, bounds.min_c);
			bounds.max_c = std::max(c, bounds.max_c);
		}
	}
	visible.erase(0);  // 0 no es un color
 
	// todos los colores no visibles podrían haberse pintado primero
	int poss_first = width * width - visible.size();
	// manejamos el caso borde donde hay un solo color
	if (visible.size() > 1) {
		/*
		 * rect_num[r][c] *va a* contener la cantidad de rectángulos
		 * que deben contener el punto (r, c)
		 */
		vector<vector<int>> rect_num(width + 1, vector<int>(width + 1));
		std::set<int> valid_colors;
		for (const auto &[c, b] : visible) {
			// lo inicializamos como un arreglo de diferencias
			valid_colors.insert(c);
			rect_num[b.min_r][b.min_c]++;
			rect_num[b.min_r][b.max_c + 1]--;
			rect_num[b.max_r + 1][b.min_c]--;
			rect_num[b.max_r + 1][b.max_c + 1]++;
		}
 
		for (int r = 0; r < width; r++) {
			for (int c = 0; c < width; c++) {
				if (r > 0) { rect_num[r][c] += rect_num[r - 1][c]; }
				if (c > 0) { rect_num[r][c] += rect_num[r][c - 1]; }
				if (r > 0 && c > 0) { rect_num[r][c] -= rect_num[r - 1][c - 1]; }
 
				/*
				 * si 2 rectángulos se superponen, el de arriba
				 * (o sea, el que se muestra) no puede haberse pintado primero
				 */
				if (rect_num[r][c] > 1) { valid_colors.erase(canvas[r][c]); }
			}
		}
		poss_first += valid_colors.size();
	}
 
	std::ofstream("art.out") << poss_first << endl;
}


import java.io.*;
import java.util.*;
 
public class Art {
	// BeginCodeSnip{Color Rectangle Bound Class}
	static class Bound {
		public int minR, maxR, minC, maxC;
		public Bound(int minR, int maxR, int minC, int maxC) {
			this.minR = minR;
			this.maxR = maxR;
			this.minC = minC;
			this.maxC = maxC;
		}
	}
	// EndCodeSnip
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("art.in"));
 
		int width = Integer.parseInt(read.readLine());
		int[][] canvas = new int[width][width];
		Map<Integer, Bound> visible = new HashMap<>();
		for (int r = 0; r < width; r++) {
			canvas[r] = Arrays.stream(read.readLine().split(" "))
			                .mapToInt(Integer::parseInt)
			                .toArray();
			for (int c = 0; c < width; c++) {
				if (!visible.containsKey(canvas[r][c])) {
					visible.put(canvas[r][c], new Bound(r, r, c, c));
				}
				Bound bounds = visible.get(canvas[r][c]);
				bounds.minR = Math.min(r, bounds.minR);
				bounds.maxR = Math.max(r, bounds.maxR);
				bounds.minC = Math.min(c, bounds.minC);
				bounds.maxC = Math.max(c, bounds.maxC);
			}
		}
		visible.remove(0);  // 0 no es un color
 
		// todos los colores no visibles podrían haberse pintado primero
		int possFirst = (int)Math.pow(width, 2) - visible.size();
		// manejamos el caso borde donde hay un solo color
		if (visible.size() > 1) {
			/*
			 * rectNum[r][c] *va a* contener la cantidad de rectángulos
			 * que deben contener el punto (r, c)
			 */
			int[][] rectNum = new int[width + 1][width + 1];
			for (Bound b : visible.values()) {
				// lo inicializamos como un arreglo de diferencias
				rectNum[b.minR][b.minC]++;
				rectNum[b.minR][b.maxC + 1]--;
				rectNum[b.maxR + 1][b.minC]--;
				rectNum[b.maxR + 1][b.maxC + 1]++;
			}
 
			Set<Integer> validColors = visible.keySet();
			for (int r = 0; r < width; r++) {
				for (int c = 0; c < width; c++) {
					if (r > 0) { rectNum[r][c] += rectNum[r - 1][c]; }
					if (c > 0) { rectNum[r][c] += rectNum[r][c - 1]; }
					if (r > 0 && c > 0) { rectNum[r][c] -= rectNum[r - 1][c - 1]; }
 
					/*
					 * si 2 rectángulos se superponen, el de arriba
					 * (o sea, el que se muestra) no puede haberse pintado primero
					 */
					if (rectNum[r][c] > 1) { validColors.remove(canvas[r][c]); }
				}
			}
			possFirst += validColors.size();
		}
 
		PrintWriter written = new PrintWriter("art.out");
		written.println(possFirst);
		written.close();
	}
}


class Bound:
	def __init__(self, min_r: int, max_r: int, min_c: int, max_c: int):
		self.min_r = min_r
		self.max_r = max_r
		self.min_c = min_c
		self.max_c = max_c
 
 
with open("art.in") as read:
	width = int(read.readline().strip())
	canvas = [list(map(int, read.readline().split())) for _ in range(width)]
 
visible = {}
for r in range(width):
	for c in range(width):
		color = canvas[r][c]
		if color not in visible:
			visible[color] = Bound(r, r, c, c)
 
		bounds = visible[color]
		bounds.min_r = min(r, bounds.min_r)
		bounds.max_r = max(r, bounds.max_r)
		bounds.min_c = min(c, bounds.min_c)
		bounds.max_c = max(c, bounds.max_c)
 
 
visible.pop(0, None)  # 0 no es un color
 
# todos los colores no visibles podrían haberse pintado primero
poss_first = width * width - len(visible)
 
# manejamos el caso borde donde hay un solo color
if len(visible) > 1:
	# rect_num[r][c] *va a* contener la cantidad de rectángulos
	# que deben contener el punto (r, c)
	rect_num = [[0] * (width + 1) for _ in range(width + 1)]
	valid_colors = set(visible.keys())
 
	for color, bounds in visible.items():
		# lo inicializamos como un arreglo de diferencias
		rect_num[bounds.min_r][bounds.min_c] += 1
		rect_num[bounds.min_r][bounds.max_c + 1] -= 1
		rect_num[bounds.max_r + 1][bounds.min_c] -= 1
		rect_num[bounds.max_r + 1][bounds.max_c + 1] += 1
 
	# Aplicamos el arreglo de diferencias para obtener el conteo real
	for r in range(width):
		for c in range(width):
			if r > 0:
				rect_num[r][c] += rect_num[r - 1][c]
			if c > 0:
				rect_num[r][c] += rect_num[r][c - 1]
			if r > 0 and c > 0:
				rect_num[r][c] -= rect_num[r - 1][c - 1]
 
			# si 2 rectángulos se superponen, el de arriba
			# (o sea, el que se muestra) no puede haberse pintado primero
			if rect_num[r][c] > 1:
				valid_colors.discard(canvas[r][c])
 
	poss_first += len(valid_colors)
 
print(poss_first, file=open("art.out", "w"))