Skip to Content
CTRL K

The Lazy Cow

Análisis oficial (C++) 

Pista 1

Si el rango de valores a los que Bessie puede moverse formara un cuadrado en vez de este diamante, podríamos aplicar sumas de prefijos normales.

Pista 2

¿Qué transformación llevaría un diamante a un cuadrado?

Solución

Explicación

Aplicamos una rotación de 45 grados sobre la grilla como sigue. Nuestro objetivo es que, en vez de un diamante como en el enunciado, las celdas a las que Bessie puede caminar formen un cuadrado.

005000
01450
0993250
81026
1071717
05221
07823800
01110
00900

Si simplemente apretamos todas las diagonales en filas, se crea esta estructura extraña tipo ladrillo. Esto no tiene sentido, porque hay medias distancias. ¿Cómo se pone siquiera esto en un arreglo 2D? Para resolver el problema de las medias distancias, expandimos la grilla por un factor de 2, insertando ceros como relleno. Notemos que agregamos ceros porque no pueden afectar la suma final.

0000500000
0001405000
00990302500
0801002060
100701 (B)07017
0005020210
007802308000
0001011000
000090000

Para demostrar lo que logramos, ahora miremos las celdas que Bessie (B) puede alcanzar cuando K = 2, la situación exacta del enunciado.

9903025
010020
701 (B)07
05020
78023080

Este rango ahora es un cuadrado, ¡lo que nos da muchas más posibilidades!

Para calcular la suma de los números en estos cuadrados, que ahora tienen forma de cuadrados, podemos usar sumas de prefijos 2D para calcular la suma de cada cuadrado en tiempo constante. Así, podemos hacer fuerza bruta sobre todos los cuadrados en los que Bessie puede estar y tomar la suma máxima.

Implementación

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

#include <fstream>
#include <iostream>
#include <vector>
 
using std::endl;
using std::max;
using std::min;
using std::vector;
 
int main() {
	std::ifstream read("lazy.in");
 
	int n;
	int k;
	read >> n >> k;
	// la longitud del lado necesaria para acomodar la rotación de 45 grados
	int new_n = 2 * n - 1;
	// -1 indica ubicaciones inválidas
	vector<vector<int>> field(new_n, vector<int>(new_n, -1));
 
	// leemos la entrada y la guardamos rotada 45 grados
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { read >> field[i + j][n - i + j - 1]; }
	}
 
	vector<vector<int>> prefix(new_n + 1, vector<int>(new_n + 1));
	for (int i = 0; i < new_n; i++) {
		for (int j = 0; j < new_n; j++) {
			// evitar incluir -1s en la suma de prefijos
			int val = std::max(field[i][j], 0);
			prefix[i + 1][j + 1] =
			    (val + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j]);
		}
	}
 
	int most_grass = 0;
	for (int i = 0; i < new_n; i++) {
		for (int j = 0; j < new_n; j++) {
			if (field[i][j] == -1) {
				continue;  // no empezar en ubicaciones inválidas
			}
 
			int sr = max(i - k, 0), er = min(i + k, new_n - 1);
			int sc = max(j - k, 0), ec = min(j + k, new_n - 1);
			most_grass = max(most_grass, prefix[er + 1][ec + 1] - prefix[er + 1][sc] -
			                                 prefix[sr][ec + 1] + prefix[sr][sc]);
		}
	}
 
	std::ofstream("lazy.out") << most_grass << endl;
}
import java.io.*;
import java.util.*;
 
public class Lazy {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("lazy");
		int n = io.nextInt();
		int k = io.nextInt();
 
		// la longitud del lado necesaria para acomodar la rotación de 45 grados
		int newN = 2 * n - 1;
		int[][] field = new int[newN][newN];
		for (int r = 0; r < newN; r++) {
			Arrays.fill(field[r], -1);  // -1 indica ubicaciones inválidas
		}
 
		// leemos la entrada y la guardamos rotada 45 grados
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) { field[i + j][n - i + j - 1] = io.nextInt(); }
		}
 
		int[][] prefix = new int[newN + 1][newN + 1];
		for (int i = 0; i < newN; i++) {
			for (int j = 0; j < newN; j++) {
				// evitar incluir -1s en la suma de prefijos
				int val = Math.max(field[i][j], 0);
				prefix[i + 1][j + 1] =
				    (val + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j]);
			}
		}
 
		int mostGrass = 0;
		for (int i = 0; i < newN; i++) {
			for (int j = 0; j < newN; j++) {
				if (field[i][j] == -1) {
					continue;  // no empezar en ubicaciones inválidas
				}
 
				int sr = Math.max(i - k, 0), er = Math.min(i + k, newN - 1);
				int sc = Math.max(j - k, 0), ec = Math.min(j + k, newN - 1);
				mostGrass =
				    Math.max(mostGrass, prefix[er + 1][ec + 1] - prefix[er + 1][sc] -
				                            prefix[sr][ec + 1] + prefix[sr][sc]);
			}
		}
 
		io.println(mostGrass);
		io.close();
	}
 
	// CodeSnip{Kattio}
}
import sys
 
sys.stdin = open("lazy.in", "r")
 
n, k = map(int, input().split())
# la longitud del lado necesaria para acomodar la rotación de 45 grados
new_n = 2 * n - 1
field = [[-1] * new_n for _ in range(new_n)]  # -1 indica ubicaciones inválidas
 
# leemos la entrada y la guardamos rotada 45 grados
for i in range(n):
	for j, x in enumerate(map(int, input().split())):
		field[i + j][n - i + j - 1] = x
 
prefix = [[0] * (new_n + 1) for _ in range(new_n + 1)]
for i in range(new_n):
	for j in range(new_n):
		val = max(field[i][j], 0)  # evitar incluir -1s en la suma de prefijos
		prefix[i + 1][j + 1] = val + prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j]
 
most_grass = 0
for i in range(new_n):
	for j in range(new_n):
		if field[i][j] == -1:
			continue  # no empezar en ubicaciones inválidas
 
		sr = max(i - k, 0)
		er = min(i + k, new_n - 1)
		sc = max(j - k, 0)
		ec = min(j + k, new_n - 1)
		most_grass = max(
			most_grass,
			prefix[er + 1][ec + 1]
			- prefix[er + 1][sc]
			- prefix[sr][ec + 1]
			+ prefix[sr][sc],
		)
 
print(most_grass, file=open("lazy.out", "w"))
Fundamentos