Skip to Content
CTRL K

Reflection

Análisis oficial (C++) 

Explicación

Consideremos cada casilla individual del cuadrante superior izquierdo y calculemos la cantidad mínima de operaciones necesarias para que esta casilla y las celdas correspondientes de los otros tres cuadrantes coincidan.

  1. Si hay tres casillas pintadas, pintamos la celda restante, lo que toma una operación.
  2. Si hay dos casillas pintadas, podemos o bien pintar las otras dos celdas o quitar la pintura de las dos celdas pintadas, lo que toma dos operaciones.
  3. Si hay una casilla pintada, quitamos la pintura de esa celda, lo que toma una operación.
  4. Por último, si las cuatro están pintadas o las cuatro no lo están, ya coinciden, así que se necesitan cero operaciones.

Sumar todas las contribuciones de cada celda nos da la cantidad mínima de operaciones necesarias para cumplir la condición de reflexión. Luego, para cada una de las UU actualizaciones, solo hace falta considerar el cambio de contribución de la celda actualizada y de las celdas correspondientes en los otros tres cuadrantes. La forma más simple de manejarlo es restar la contribución actual de esas cuatro celdas, actualizar la grilla y después sumar la nueva contribución.

Implementación

Complejidad temporal: O(N2+U)\mathcal{O}(N^{2}+U)

#include <bits/stdc++.h>
using namespace std;
 
int n, u;
vector<string> grid;
 
int contribution(int r, int c) {
	// 4 symmetric cells
	vector<char> cells = {grid[r][c], grid[n - r - 1][c], grid[r][n - c - 1],
	                      grid[n - r - 1][n - c - 1]};
	// Min flips to make them all equal
	int painted = 0;
	for (char ch : cells) {
		if (ch == '#') painted++;
	}
	return min(painted, 4 - painted);
}
 
int main() {
	cin >> n >> u;
	grid.resize(n);
	for (int i = 0; i < n; i++) { cin >> grid[i]; }
 
	// Initial answer (only need top-left quadrant)
	int ans = 0;
	for (int row = 0; row < n / 2; row++) {
		for (int col = 0; col < n / 2; col++) { ans += contribution(row, col); }
	}
 
	cout << ans << '\n';
 
	for (int i = 0; i < u; i++) {
		int r, c;
		cin >> r >> c;
		r--;
		c--;
		ans -= contribution(r, c);                     // remove old contribution
		grid[r][c] = (grid[r][c] == '.') ? '#' : '.';  // toggle
		ans += contribution(r, c);                     // add new contribution
		cout << ans << '\n';
	}
}
n, u = map(int, input().split())
grid = [list(input()) for i in range(n)]
 
 
def contribution(r, c):
	# 4 symmetric cells
	cells = [
		grid[r][c],
		grid[n - r - 1][c],
		grid[r][n - c - 1],
		grid[n - r - 1][n - c - 1],
	]
	# Min flips to make them all equal
	painted = cells.count("#")
	return min(painted, 4 - painted)
 
 
# Initial answer (only need top-left quadrant)
ans = 0
for row in range(n // 2):
	for column in range(n // 2):
		ans += contribution(row, column)
print(ans)
 
for i in range(u):
	r, c = map(int, input().split())
	r -= 1
	c -= 1
	ans -= contribution(r, c)  # remove old contribution
	grid[r][c] = "#" if grid[r][c] == "." else "."  # toggle
	ans += contribution(r, c)  # add new contribution
	print(ans)
Fundamentos