Skip to Content
CTRL K

2021 - Sateliti

Análisis oficial 

Pista 1

Un truco útil para manejar rotaciones es aumentar nuestro arreglo.

Digamos que tenemos un arreglo de longitud nn y queremos considerar todas las rotaciones cíclicas del arreglo. Entonces, podemos construir un arreglo de tamaño 2n2n, donde cada elemento ii se mapea a ii y a i+ni+n. A partir de ahí, solo hay que considerar cada subarreglo de longitud nn de este arreglo aumentado.

Podemos usar la misma idea sobre nuestra grilla 2D. Así, el problema se reduce a hallar la subgrilla de nn filas por mm columnas lexicográficamente más pequeña en nuestra grilla aumentada.

Pista 2

Consideremos el proceso de comparar dos strings lexicográficamente. Primero recorremos un montón de caracteres idénticos, y luego llegamos a un índice donde los dos strings difieren.

Para comparar subgrillas rápido, queremos atravesar todos los caracteres idénticos lo más rápido posible. Recordemos el problema de strings de hallar el prefijo común más largo entre dos strings: una solución es usar búsqueda binaria y hashing. ¿Cómo podemos extender esta solución a una grilla?

Solución

Para hallar el mejor rectángulo, recorremos por fuerza bruta cada subgrilla relevante de nuestra grilla aumentada, y nos quedamos con la mejor.

Comparar dos rectángulos lexicográficamente es un poco delicado. Recordemos el problema del prefijo común más largo: hacemos búsqueda binaria sobre el último índice donde los dos strings tienen hashes equivalentes.

Separamos el problema de hallar el primer índice distinto en dos partes:

  1. Hallar la primera fila donde hay valores distintos
  2. Dentro de esta primera fila, hallar el primer índice donde las posiciones difieren

El paso 2 se hace fácilmente con búsqueda binaria y hashing. ¿Pero cómo logramos nuestro objetivo en el paso 1?

Para una celda dada (i,j)(i, j), solo nos importa un subarreglo en la fila ii, a saber [j,j+m)[j, j + m). Así, lo que podemos hacer es hashear nuestros hashes: mantenemos una tabla hash para cada columna que lleva la cuenta de los hashes de las filas.

De forma similar al paso 2, usamos búsqueda binaria para completar el paso 1 del proceso de comparación.

Implementación

Complejidad temporal: O(NMlog⁡(NM))\mathcal{O}(NM \log(NM))

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
constexpr int M = 1e9 + 9;
constexpr int B = 9973;
 
int main() {
	int n, m;
	cin >> n >> m;
	vector grid(2 * n, vector<int>(2 * m));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c;
			cin >> c;
			grid[i][j] = c;
			grid[i + n][j] = c;
			grid[i][j + m] = c;
			grid[i + n][j + m] = c;
		}
	}
 
	vector<ll> pows(max(n, m) + 1);
	pows[0] = 1;
	for (int i = 1; i < pows.size(); i++) { pows[i] = (pows[i - 1] * B) % M; }
 
	// col[i] es nuestro arreglo de hash polinómico de la i-ésima fila
	// row[i] es el hash de nuestros hashes de la i-ésima columna
	vector row(m, vector<int>(2 * n));
	vector col(2 * n, vector<int>(2 * m));
 
	/** @return el hash del subarreglo [l, r] */
	const auto get_hash = [&](const vector<int> &arr, int l, int r) -> int {
		ll raw = arr[r] - pows[r - l + 1] * (l <= 0 ? 0 : arr[l - 1]);
		return (raw % M + M) % M;
	};
 
	for (int i = 0; i < 2 * n; i++) {
		ll cur = 0;
		for (int j = 0; j < 2 * m; j++) {
			cur = (cur * B + grid[i][j]) % M;
			col[i][j] = cur;
		}
 
		for (int j = 0; j < m; j++) {
			ll prv = (i > 0) ? row[j][i - 1] : 0;
			row[j][i] = (prv * B + get_hash(col[i], j, j + m - 1)) % M;
		}
	}
 
	int best_r = 0, best_c = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int lo = 0, hi = n - 1;
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				bool mismatch = get_hash(row[best_c], best_r, best_r + mid) !=
				                get_hash(row[j], i, i + mid);
				(mismatch) ? hi = mid : lo = mid + 1;
			}
 
			if (get_hash(row[best_c], best_r, best_r + n - 1) ==
			    get_hash(row[j], i, i + n - 1)) {
				continue;
			}
 
			int off = lo;
 
			lo = 0, hi = m - 1;
			while (lo < hi) {
				int mid = (lo + hi) / 2;
				bool mismatch = get_hash(col[best_r + off], best_c, best_c + mid) !=
				                get_hash(col[i + off], j, j + mid);
				(mismatch) ? hi = mid : lo = mid + 1;
			}
 
			if (grid[i + off][j + lo] < grid[best_r + off][best_c + lo]) {
				best_r = i, best_c = j;
			}
		}
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) { cout << char(grid[best_r + i][best_c + j]); }
		cout << "\n";
	}
}
Fundamentos