Skip to Content
CTRL K

Lights Out

Análisis oficial (C++) 

Explicación

La solución oficial simplemente no usa hashing.

Queremos poder identificar la ubicación de Bessie después de recorrer algunas aristas y vértices, y luego sumar la distancia más corta hasta la salida desde esta ubicación para cada índice de partida. Luego, queremos comparar esta distancia total con la distancia más corta hasta el final solo desde el vértice de partida para encontrar la respuesta. Encontrar la distancia mínima hasta el final desde cada vértice se puede hacer en tiempo O(N2)\mathcal{O}(N^2), como se ilustra en el código. La pregunta que queda es cómo identificar la ubicación de Bessie después de recorrer algunas aristas y vértices desde cada punto de partida.

Como indica la solución oficial, es mejor visualizar el mapa como un string compuesto de ángulos y aristas en lugar de un polígono. Podemos identificar la ubicación de Bessie si el camino actual no se repite en otra parte del mapa. Si lo planteamos como un problema de matching de strings, querríamos encontrar la subcadena más corta del mapa tal que aparezca una sola vez.

Para manejar los ángulos, podemos notar que solo hay dos ángulos interiores posibles, 90∘90^\circ y 270∘270^\circ.

angle pic

Usamos hashing para encontrar la subcadena más corta del mapa. Distinguiendo vértices de ángulos, recorremos por fuerza bruta las longitudes en orden creciente y usamos un hash polinómico con base uno para comprobar si la subcadena aparece una sola vez. Si encontramos una subcadena apropiada, encontramos la distancia total que recorremos antes de saber dónde estamos.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
 
const ll P = 31;
const ll MOD = 1e9 + 7;
// máxima distancia vertical/horizontal
const int MX = 2e5;
 
struct Coord {
	int x, y;
};
 
int main() {
	freopen("lightsout.in", "r", stdin);
	freopen("lightsout.out", "w", stdout);
 
	int n;
	cin >> n;
 
	vector<Coord> dt(n);
	for (int i = 0; i < n; i++) { cin >> dt[i].x >> dt[i].y; }
 
	function<int(int i, int j)> calc_dist = [&](int i, int j) {
		return abs(dt[i].x - dt[j].x) + abs(dt[i].y - dt[j].y);
	};
 
	vector<vector<vector<int>>> dist(n,
	                                 vector<vector<int>>(n, vector<int>(2, INT32_MAX)));
 
	/*
	 * dist[i][j][0] - dist horaria de i -> j
	 * dist[i][j][1] - dist antihoraria de i -> j
	 */
	for (int i = 0; i < n; i++) {
		for (int j = i; j < i + n; j++) {
			if (i == j) {
				dist[i][j][0] = 0;
			} else {
				int x = (j + n) % n;
				int y = (j - 1 + n) % n;
				dist[i][x][0] = dist[i][y][0] + calc_dist(x, y);
			}
		}
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = i; j > i - n; j--) {
			if (i == j) {
				dist[i][j][1] = 0;
			} else {
				int x = (j + n) % n;
				int y = (j + 1 + n) % n;
				dist[i][x][1] = dist[i][y][1] + calc_dist(x, y);
			}
		}
	}
 
	vector<int> ang(n);
	for (int i = 0; i < n; i++) {
		int prev = (i - 1 + n) % n;
		int nxt = (i + 1) % n;
 
		/*
		 * dos tipos de ángulos posibles (90 deg adentro o afuera)
		 * recordatorio: todas las aristas son paralelas al eje x o al eje y y se alternan
		 */
 
		// derivado de la pendiente
		ll rt = ((dt[i].y - dt[prev].y) * (dt[nxt].x - dt[i].x) -
		         (dt[nxt].y - dt[i].y) * (dt[i].x - dt[prev].x));
 
		// ningún ángulo debería ser nunca colineal
		assert(rt);
 
		ang[i] = rt > 0 ? MX + 2 : MX + 1;
	}
 
	vector<int> hash(1);
	hash[0] = 0;
 
	vector<ll> poly(2 * n + 1);
 
	poly[0] = 1;
	for (int i = 1; i < (int)(poly.size()); i++) {
		poly[i] = (int)(poly[i - 1] * P % MOD);
	}
 
	for (int i = 1; i < n; i++) {
		hash.push_back((hash.back() * P + dist[(i - 1 + n) % n][i][0]) % MOD);
		hash.push_back((hash.back() * P + ang[i]) % MOD);
	}
	hash.push_back(hash.back() * P + dist[n - 1][0][0]);
 
	function<int(int i, int j)> get_hash = [&](int i, int j) {
		// obtiene el hash de la subcadena de i -> j
		// también se puede calcular usando el inverso modular de poly_i
		return ((hash[j] - ((hash[i] * poly[j - i]) % MOD) + MOD) % MOD);
	};
 
	int ans = 0;
	for (int i = 1; i < (int)(hash.size()) - 2; i++) {
		int fin = -1;
 
		for (int len = 1; len < (int)(hash.size()) - i; len++) {
			int cr = get_hash(i, i + len);
			int occ = 0;
 
			for (int j = 0; j < (int)(hash.size()) - len; j++) {
				if (get_hash(j, j + len) == cr) { occ++; }
			}
 
			// bessie puede identificar de forma única su posición
			if (occ == 1) {
				fin = (i + len + 1) / 2;
				break;
			}
		}
 
		int start = (i + 2) / 2;
		if (fin >= n) { fin = -1; }
 
		int a = dist[start][0][0];
		if (fin != -1) {
			// tiempo para llegar al punto único + mejor dist desde ahí
			a = min(dist[fin][0][0], dist[fin][0][1]) + dist[start][fin][0];
		}
		// tiempo por defecto para llegar a la salida desde el inicio
		int b = min(dist[start][0][0], dist[start][0][1]);
 
		ans = max(ans, a - b);
	}
 
	cout << ans << endl;
}
Fundamentos