Cross Swapping

Análisis oficial 

Explicación

Nótese que $a[i][j]$ solo se puede intercambiar con $a[j][i]$ sin importar qué operaciones se hagan.

Para todo $j$ tal que $i < j$ (solo necesitamos considerar cada par una vez y mantener $i < j$ lo garantiza), podemos determinar si queremos intercambiarlos o dejarlos iguales.

Si $a[i][j] > a[j][i]$, queremos intercambiarlos. Si $a[i][j] < a[j][i]$ queremos dejarlos iguales. Si son iguales no importa.

Sin embargo, es posible que no todas las condiciones puedan funcionar juntas y que intercambiar algo/dejar algo igual signifique que no podemos intercambiar algo más/dejar algo igual más adelante. Consideremos la siguiente entrada:

0 2 1
1 0 1
3 2 0

Primero queremos intercambiar $a[0][1]$ y $a[1][0]$ porque $1$ es menor que $2$. Podemos hacer esto volteando la fila/columna $0$. Esto nos daría el arreglo:

0 1 3
2 0 1
1 2 0

Luego queremos intercambiar $a[0][2]$ y $a[2][0]$ porque $1$ es menor que $3$. Para hacer esto o bien podemos intercambiar la fila/columna $0$ o la fila/columna $2$. Sin embargo, intercambiar la fila/columna $0$ desharía el esfuerzo de nuestra primera operación, así que intercambiaremos la fila/columna $2$ y obtenemos:

0 1 1
2 0 2
3 1 0

Ahora queremos intercambiar $a[1][2]$ y $a[2][1]$ porque $1$ es menor que $2$ y queremos el lexicográficamente mínimo. Sin embargo, intercambiar la fila/columna $1$ arruinaría el intercambio que hicimos en la primera operación e intercambiar la fila/columna $2$ arruinaría el intercambio que hicimos en la segunda operación. Así, es imposible hacer todos los intercambios de forma óptima.

Como queremos la respuesta lexicográficamente más pequeña, los índices anteriores importan más que los posteriores, así que hallamos intercambios de filas óptimos para los índices anteriores primero.

Podemos crear un Union-Find / conjuntos disjuntos (DSU) para modelar este problema. El DSU tendrá $2n$ nodos donde el nodo $i$ representa el estado en el que se hace la operación sobre la $i$-ésima fila y el nodo $i + n$ representa el estado en el que no se hace la operación sobre la $i$-ésima fila.

A medida que recorremos el arreglo de forma voraz, podemos unir ($i$ y $j$) e ($i + n$ y $j + n$) si no queremos intercambiar. Esto funciona porque si no intercambiamos ninguno o intercambiamos ambos, el arreglo permanece igual. Si sí queremos intercambiar, podemos unir ($i$ y $j + n$) e ($i + n$ y $j$). Esto funciona porque si intercambiamos exactamente uno de estos, entonces el arreglo cambia.

Después de esto podemos construir la respuesta iterando sobre cada celda de la grilla. Si el índice de fila de la celda es igual a su índice de columna (es decir, está en la diagonal de la grilla) nunca puede cambiar independientemente de los volteos. Si $a[i][j] == a[j][i]$ entonces podemos asignarlos manualmente (como no los unimos en el Union-Find al compararlos, los estados podrían no haberse unido). En caso contrario, podemos comprobar si $i$ y $j$ están unidos en el Union-Find. Si no lo están, intercambiaremos $a[i][j]$ y $a[j][i]$. En caso contrario los dejaremos iguales.

Implementación

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

#include <iostream>
#include <vector>
 
 
using namespace std;
 
// BeginCodeSnip{DSU}
struct DSU {
	vector<int> e;
	DSU(int n) { e = vector<int>(n, -1); }
 
	int get(int x) {
		if (e[x] < 0) {
			return x;
		} else {
			e[x] = get(e[x]);
			return e[x];
		}
	}
 
	bool same(int a, int b) { return get(a) == get(b); }
 
	int size(int x) { return -e[get(x)]; }
 
	bool unite(int x, int y) {
		x = get(x);
		y = get(y);
		if (x == y) { return false; }
		if (e[x] > e[y]) { swap(x, y); }
		e[x] += e[y];
		e[y] = x;
		return true;
	}
};
// EndCodeSnip
 
void solve() {
	int n;
	cin >> n;
	int a[n][n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { cin >> a[i][j]; }
	}
 
	DSU dsu(2 * n);
 
	for (int i = 0; i < n; i++) {
		// Only check each pair once and diagnals don't matter
		for (int j = i + 1; j < n; j++) {
			// If they are the same we should not merge either way
			// because it could affect later merges
			if (a[i][j] == a[j][i]) {
				continue;
			} else if (a[i][j] > a[j][i]) {
				// Swap the elements if the states are not already merged the
				// opposite way
				if (dsu.get(i) != dsu.get(j)) {
					dsu.unite(i, j + n);
					dsu.unite(j, i + n);
				}
			} else {
				// Keep the elements the same if the states
				// are not already merged the opposite way
				if (dsu.get(i) != dsu.get(j + n)) {
					dsu.unite(i, j);
					dsu.unite(i + n, j + n);
				}
			}
		}
	}
 
	// Construct the answer
	vector<vector<int>> ans(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = i; j < n; j++) {
			/*
			 * If a[i][j] is part of a diagonal or the pair is equal (a[i][j] ==
			 * a[j][i]), manually set it to be the same as the original array
			 */
			if (i == j) {
				ans[i][j] = a[i][j];
			} else if (a[i][j] == a[j][i]) {
				ans[i][j] = ans[j][i] = a[i][j];
			} else {  // Otherwise check whether the i and j states are merged
				if (dsu.get(i) == dsu.get(j)) {
					ans[i][j] = a[i][j];
					ans[j][i] = a[j][i];
				} else {
					ans[i][j] = a[j][i];
					ans[j][i] = a[i][j];
				}
			}
		}
	}
 
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { cout << ans[i][j] << " "; }
		cout << '\n';
	}
}
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
 
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) { solve(); }
}