Mountain Time

Pista 1

En vez de pensar el problema como una grilla, considerémoslo un grafo, donde vamos agregando una celda a la vez.

Como queremos obtener el camino con las montañas más altas, las procesaremos en orden decreciente de altura.

Pista 2

Cada vez que procesamos una celda, queremos fusionarla con todos sus vecinos que ya se hayan agregado (más altos que ella).

¿Qué estructura de datos deberíamos usar para fusionar dos componentes de forma eficiente?

Respuesta a la Pista 2

Podemos usar un DSU para resolver el problema.

Solución

Explicación

Imaginemos que estamos actualmente en la celda $x$ , parte de la componente $A$ , y fusionamos con alguna celda adyacente $y$ , parte de la componente $B$ .

Podemos dividirlo en dos casos.

Las montañas más altas de $A$ y $B$ tienen la misma altura. En este caso, combinamos todas las celdas en una componente usando fusión small-to-large para minimizar el número de celdas que hay que actualizar.
Las montañas más altas de $A$ y $B$ tienen alturas distintas. Sin pérdida de generalidad, supongamos que la montaña $A$ tiene la montaña más alta; conocemos la respuesta para las celdas de la componente $B$ porque $x$ es la montaña más alta que puede conectarlas a ambas.

Para simplificar el proceso, enraizamos cada componente en su celda máxima y guardamos sus índices correspondientes en el DSU. Así, podemos iterar fácilmente sobre las celdas para las que ya hallamos la respuesta.

Implementación

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

C++


#include <bits/stdc++.h>
using namespace std;
 
struct DSU {
	vector<int> par;
	vector<list<int>> comp;
	DSU(int n) {
		par = vector<int>(n);
		// al inicio cada nodo es su propio padre
		iota(par.begin(), par.end(), 0);
 
		comp = vector<list<int>>(n);
		for (int i = 0; i < n; i++) { comp[i].push_back(i); }
	}
 
	// obtener la raíz (usa compresión de caminos)
	int get(int x) { return par[x] == x ? x : par[x] = get(par[x]); }
 
	void unite(int x, int y, vector<int> &grid, vector<int> &ans) {
		int intermediate = grid[x];
		x = get(x), y = get(y);
 
		if (x == y) { return; }
 
		if (grid[x] > grid[y]) { swap(x, y); }
 
		if (grid[y] > grid[x]) {
			/*
			 * como todo elemento de comp[x] < comp[y] y están conectados por
			 * intermediate, podemos fijar la respuesta para todos los elementos
			 * de esta componente.
			 */
			for (int i : comp[x]) { ans[i] = grid[i] - intermediate; }
 
			comp[x].clear();
			par[x] = y;
		} else if (grid[x] == grid[y]) {
			// fusionar las dos componentes (small to large)
			if ((int)comp[x].size() < (int)comp[y].size()) { swap(x, y); }
 
			comp[x].splice(comp[x].end(), comp[y]);
			par[y] = x;
		}
	}
};
 
int main() {
	int n, m;
	cin >> n >> m;
 
	vector<int> grid(n * m);
	vector<int> ans(n * m);
 
	DSU dsu(n * m);
 
	vector<pair<int, int>> mountains;
	for (int i = 0; i < n * m; i++) {
		cin >> grid[i];
		ans[i] = grid[i];
 
		mountains.push_back({grid[i], i});
	}
 
	sort(mountains.begin(), mountains.end());
 
	// iterar por todas las celdas de la más alta a la más baja
	while (!mountains.empty()) {
		pair<int, int> cur = mountains.back();
		mountains.pop_back();
 
		int idx = cur.second;
 
		// comprobar todas las celdas adyacentes ya procesadas
		if (idx % m != 0 && grid[idx - 1] >= grid[idx]) {
			dsu.unite(idx, idx - 1, grid, ans);  // a la izquierda
		}
		if (idx >= m && grid[idx - m] >= grid[idx]) {
			dsu.unite(idx, idx - m, grid, ans);  // arriba
		}
		if (idx % m != m - 1 && grid[idx + 1] >= grid[idx]) {
			dsu.unite(idx, idx + 1, grid, ans);  // a la derecha
		}
		if (idx < (n * m) - m && grid[idx + m] >= grid[idx]) {
			dsu.unite(idx, idx + m, grid, ans);  // abajo
		}
	}
 
	for (int i = 0; i < n * m; i++) {
		if ((i + 1) % m == 0) {
			cout << ans[i] << endl;
		} else {
			cout << ans[i] << ' ';
		}
	}
}