Tractor

Explicación

Podemos crear un grafo donde las celdas del campo son vértices y dos campos adyacentes están conectados por una arista. Para encontrar la componente conexa con al menos $\lceil\frac{N^2}{2}\rceil$ vértices, podemos usar Union-Find / conjuntos disjuntos (DSU) para llevar la cuenta de las componentes y agregar aristas en orden creciente de costo hasta tener una componente conexa que cubra al menos la mitad de los vértices.

Primero, iteramos sobre cada celda y agregamos las aristas entre ella y sus vecinos al vector $\texttt{edges}$ . Solo agregamos una arista si la celda actual tiene mayor altura que su vecino para no agregar una arista dos veces. Luego, ordenamos las aristas en orden creciente de costo. Para cada arista, unimos los conjuntos de los dos vértices y paramos cuando el tamaño de la componente conexa es al menos $\lceil\frac{N^2}{2}\rceil$ .

Implementación

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

C++


#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
void init();
bool unite(int a, int b);
 
struct Cell {
	int i, j;
};
struct Edge {
	Cell from, to;
	int cost;
};
 
const int MAX_N = 500;
int parent[MAX_N * MAX_N];
int comp_size[MAX_N * MAX_N];  // tamaño de cada componente
int n;
 
int main() {
	freopen("tractor.in", "r", stdin);
	freopen("tractor.out", "w", stdout);
	cin >> n;
	int field[MAX_N][MAX_N];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) { cin >> field[i][j]; }
	}
	init();
	vector<Edge> edges;
	int di[]{-1, 0, 1, 0}, dj[]{0, 1, 0, -1};
	for (int row = 0; row < n; row++) {
		for (int col = 0; col < n; col++) {
			for (int d = 0; d < 4; d++) {
				Cell to = {row + di[d], col + dj[d]};
				// asegurarnos de que la siguiente celda esté dentro de los límites
				// y tenga menor altura para no agregar una arista dos veces
				if (to.i >= 0 && to.i < n && to.j >= 0 && to.j < n &&
				    field[row][col] >= field[to.i][to.j]) {
					edges.push_back(
					    {{row, col}, to, field[row][col] - field[to.i][to.j]});
				}
			}
		}
	}
	// ordenar las aristas en orden creciente de costo
	sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.cost < b.cost; });
 
	for (Edge edge : edges) {
		// si la componente conexa cubre al menos la mitad de las celdas
		if (unite(edge.from.i * n + edge.from.j, edge.to.i * n + edge.to.j)) {
			cout << edge.cost << endl;
			return 0;
		}
	}
}
 
void init() {
	for (int i = 0; i < n * n; i++) {
		parent[i] = i;
		comp_size[i] = 1;
	}
}
 
int find(int a) {
	if (a == parent[a]) { return a; }
	return parent[a] = find(parent[a]);
}
 
bool unite(int a, int b) {
	int root_a = find(a), root_b = find(b);
	if (root_a == root_b) { return false; }
	if (comp_size[root_a] > comp_size[root_b]) { swap(root_a, root_b); }
	parent[root_a] = root_b;
	comp_size[root_b] += comp_size[root_a];
	return comp_size[root_b] >= (n * n + 1) / 2;
}