Skip to Content
CTRL K

Modern Art

Análisis oficial (C++) 

Solución

Pista 1

Intentemos resolver la entrada de ejemplo a mano: ¿se podría aplicar un método similar en el código?

Pista 2

¿Qué propiedad tiene un color que no puede ser el primero en pintarse?

Explicación

Primero, observemos que si dos colores se superponen, sabemos que al menos uno de ellos no puede ser el rectángulo original.

Para cada color c1c_1, podemos determinar los límites de ese color y considerar su rectángulo envolvente (bounding rectangle). Cualquier otro color c2c_2 que aparezca dentro de este rectángulo en la grilla final debió pintarse después de c1c_1, y podemos descartar a c2c_2 como el primer color pintado.

Hay que notar que siempre elegimos el rectángulo envolvente más pequeño posible para cada color c1c_1. Esto es porque un rectángulo más grande crea más intersección entre colores, lo que podría eliminar colores iniciales válidos.

Implementación

Complejidad temporal: O(N3)\mathcal O(N^3)

#include <fstream>
#include <iostream>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
const int MAX_COLOR = 9;
 
int main() {
	/*
	 * Cajas envolventes de cada uno de los colores.
	 * El primer elemento no se usa (los colores van de 1 a 9)
	 */
	vector<int> left(MAX_COLOR + 1);
	vector<int> right(MAX_COLOR + 1);
	vector<int> up(MAX_COLOR + 1);
	vector<int> down(MAX_COLOR + 1);
	for (int c = 1; c <= MAX_COLOR; c++) {
		left[c] = up[c] = INT32_MAX;
		right[c] = down[c] = -1;
	}
 
	vector<bool> valid_start(MAX_COLOR + 1);
	std::ifstream read("art.in");
	int width;
	read >> width;
	vector<vector<int>> art(width, vector<int>(width));
	for (int r = 0; r < width; r++) {
		for (int c = 0; c < width; c++) {
			char curr_char;
			read >> curr_char;
			int curr = curr_char - '0';
			art[r][c] = curr;
			if (curr != 0) {
				left[curr] = std::min(left[curr], c);
				right[curr] = std::max(right[curr], c);
				down[curr] = std::max(down[curr], r);
				up[curr] = std::min(up[curr], r);
				valid_start[curr] = true;
			}
		}
	}
 
	for (int color = 1; color <= MAX_COLOR; color++) {
		for (int r = up[color]; r <= down[color]; r++) {
			for (int c = left[color]; c <= right[color]; c++) {
				if (art[r][c] != color) { valid_start[art[r][c]] = false; }
			}
		}
	}
 
	int total_starts = 0;
	for (bool s : valid_start) { total_starts += s ? 1 : 0; }
	std::ofstream("art.out") << total_starts << endl;
}
import java.io.*;
 
public class Art {
	static final int MAX_COLOR = 9;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("art.in"));
		int width = Integer.parseInt(read.readLine());
 
		/*
		 * Cajas envolventes de cada uno de los colores.
		 * El primer elemento no se usa (los colores van de 1 a 9)
		 */
		int[] left = new int[MAX_COLOR + 1];
		int[] right = new int[MAX_COLOR + 1];
		int[] down = new int[MAX_COLOR + 1];
		int[] up = new int[MAX_COLOR + 1];
		for (int c = 1; c <= MAX_COLOR; c++) {
			left[c] = up[c] = Integer.MAX_VALUE;
			right[c] = down[c] = -1;
		}
 
		boolean[] validStart = new boolean[MAX_COLOR + 1];
		int[][] art = new int[width][width];
		for (int r = 0; r < width; r++) {
			String row = read.readLine();
			for (int c = 0; c < width; c++) {
				int curr = Character.getNumericValue(row.charAt(c));
				art[r][c] = curr;
				if (curr != 0) {
					left[curr] = Math.min(left[curr], c);
					right[curr] = Math.max(right[curr], c);
					down[curr] = Math.max(down[curr], r);
					up[curr] = Math.min(up[curr], r);
					validStart[curr] = true;
				}
			}
		}
 
		for (int color = 1; color <= MAX_COLOR; color++) {
			for (int r = up[color]; r <= down[color]; r++) {
				for (int c = left[color]; c <= right[color]; c++) {
					if (art[r][c] != color) { validStart[art[r][c]] = false; }
				}
			}
		}
 
		int totalStarts = 0;
		for (boolean c : validStart) { totalStarts += c ? 1 : 0; }
 
		PrintWriter written = new PrintWriter("art.out");
		written.print(totalStarts);
		written.close();
	}
}
MAX_COLOR = 9
 
"""
Cajas envolventes de cada uno de los colores.
El primer elemento no se usa (los colores van de 1 a 9)
"""
left = [0] * (MAX_COLOR + 1)
right = [0] * (MAX_COLOR + 1)
down = [0] * (MAX_COLOR + 1)
up = [0] * (MAX_COLOR + 1)
for c in range(1, MAX_COLOR + 1):
	left[c], up[c] = float("inf"), float("inf")
	right[c], down[c] = -1, -1
 
valid_start = [False] * (MAX_COLOR + 1)
with open("art.in") as read:
	n = int(read.readline().strip())
	art = [None] * n
	for r in range(n):
		art[r] = [int(x) for x in read.readline().strip()]
		for c in range(n):
			if art[r][c] != 0:
				curr = art[r][c]
				left[curr] = min(left[curr], c)
				right[curr] = max(right[curr], c)
				down[curr] = max(down[curr], r)
				up[curr] = min(up[curr], r)
				valid_start[curr] = True
 
for color in range(1, MAX_COLOR + 1):
	if left[color] == float("inf"):
		continue
 
	for c in range(int(up[color]), int(down[color] + 1)):
		for k in range(int(left[color]), int(right[color] + 1)):
			if art[c][k] != color:
				other = art[c][k]
				if other != 0 and other != color:
					valid_start[other] = False
 
print(sum(valid_start), file=open("art.out", "w"))
Fundamentos