Analysis: Tractor by Travis Hance

First, let us think about how we could check if a tractor of cost K would suffice. We know that a tractor of cost K can traverse two adjacent cells if the difference in elevation is at most K. Suppose we make a graph whose vertices are the cells of the graph, and there is an edge between any two cells that the tractor can traverse. Then we are just looking for a connected component of this graph which has at least N*N/2 vertices. We can search for such a connected component using flood fill.

Now that we have a way to check if a given cost K is possible, we can simply binary search to find the answer. This solution is O(N2 log(D)), where D is the maximum height difference.

Another solution is to, rather than binary search on the cost of the tractor, increase the cost monotonically. While doing so, keep track of the connected components using union-find. Stop when some connected component becomes large enough. Depending on implementation, this algorithm could be either O(N2log(N)) or O(D + N2 alpha(N)), depending on how you sort the edges.

Here is a solution in C++, implementing the binary search solution: 
#include <cstdio>
#include <algorithm>
using namespace std;

#define NMAX 500
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

int n;
int grid[NMAX][NMAX];
bool visited[NMAX][NMAX];

// dfs for flood-fill
int dfs(int i, int j, int d) {
    if (visited[i][j]) {
        return 0;
    }
    visited[i][j] = true;
    int count = 1;
    for (int dir = 0; dir < 4; dir++) {
        int i1 = i + dx[dir];
        int j1 = j + dy[dir];
        if (i1 >= 0 && i1 < n && j1 >= 0 && j1 < n &&
                abs(grid[i1][j1] - grid[i][j]) <= d) {
            count += dfs(i1, j1, d);
        }
    }
    return count;
}

// check if for a given cost d, it is possible for FJ to acheive his goal
bool is_possible(int d) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            visited[i][j] = false;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (!visited[i][j]) {
                if (dfs(i, j, d) * 2 >= n*n) {
                    return true;
                }
            }
        }
    }
    return false;
}

int main() {
    freopen("tractor.in","r",stdin);
    freopen("tractor.out","w",stdout);

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &grid[i][j]);
        }
    }

    // binary search on answer
    // invariant: lo < ans <= hi
    int lo = -1, hi = 1000000;
    while (hi > lo + 1) {
        int mid = (lo + hi) / 2;
        if (is_possible(mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    printf("%d\n", hi);
}
Here is Jonathan Paulson's solution, in Java, implementing the union-find solution: 
import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;

public class tractor {
    static int[] dr = new int[]{1, 0, -1, 0};
    static int[] dc = new int[]{0, 1, 0, -1};

    static int[] size;
    static int[] uf;
    static int find(int x) {
        if(uf[x] == x) return x;
        return uf[x] = find(uf[x]);
    }
    static void union(int x, int y) {
        if(find(x) == find(y)) return;
        size[find(y)] += size[find(x)];
        uf[find(x)] = find(y);
    }
    static int size(int x) { return size[find(x)]; }

    static void require(boolean b) {
        if(!b) {
            throw new RuntimeException("Assert failed");
        }
    }
    public static int i(String s) { return Integer.parseInt(s); }
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new FileReader("tractor.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("tractor.out")));
        int n = in.nextInt();
        require(1<=n && n<=500);
        uf = new int[n*n];
        size = new int[n*n];
        for(int r=0; r<n; r++)
            for(int c=0; c<n; c++) {
                uf[r*n+c] = r*n+c;
                size[r*n+c] = 1;
            }

        int[][] G = new int[n][n];
        for(int r=0; r<n; r++)
            for(int c=0; c<n; c++) {
                G[r][c] = in.nextInt();
                require(0<=G[r][c] && G[r][c]<=1000*1000);
            }
        
        List<int[]> E = new ArrayList<int[]>();
        for(int rr=0; rr<n; rr++)
            for(int cc=0; cc<n; cc++)
                for(int d=0; d<4; d++) {
                    int r = rr+dr[d];
                    int c = cc+dc[d];
                    if(r<0 || c<0 || r>=n || c>=n) continue;
                    E.add(new int[]{rr*n+cc, r*n+c, Math.abs(G[r][c]-G[rr][cc])});
                }
        Collections.sort(E, new Comparator<int[]>() {
            public int compare(int[] A, int[] B) {
                return A[2]-B[2];
            }
        });

        int ans = 0;
        for(int i=0; i<E.size(); i++) {
            int[] e = E.get(i);
            union(e[0], e[1]);
            ans = Math.max(ans, e[2]);
            if(size(e[0])*2 >= n*n)
                break;
        }
        out.println(ans);
        out.flush();
    }
}