Analysis: Cross Country Skiing by Fatih Gelgi and Brian Dean

Suppose we have a function Reachable(X) that tells us (i.e. returns true) if all waypoints are reachable with absolute elevation difference at most X. Then by calling Reachable with different X values we can find D. Obviously, we cannot try all X values since X is in the range 0..1,000,000,000. Remember that we're looking for the minimum value of D which means we can use binary search:

Dmin=0, Dmax=1000000000
while Dmin < Dmax
    X = (Dmin + Dmax) / 2
    if Reachable(X)
        Dmax = X
    else 
        Dmin = X + 1
D = Dmin

Now we can work on a Reachable function which implements floodfill algorithm: starting from one waypoint, continue expanding cells while elevation difference is D between adjacent cells. As you know, we can use either Depth First Search (DFS) or Breath First Search (BFS) for floodfill. However, this is a little tricky since DFS may fail on some of the inputs. The depth of recursion can go up to NM which is too deep. On the other hand, using BFS will be safe.

For each Reachable function call, O(NM) time is required. Since binary search calls the function O(log R) times (where R is the range 0..1,000,000,000), the total running time is O(MN log R). Here is a sample code:

#include <fstream>
#include <cmath>
#include <queue>

#define MAX 501

using namespace std;

const int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int m,n,mat[MAX][MAX],wp[MAX][MAX],mark[MAX][MAX],wy,wx;

// floodfill with BFS within elevation difference d
void floodfill(int d)
{
	queue<pair<int,int> > q;

	q.push(make_pair(wy,wx));
	mark[wy][wx]=1;

	while (!q.empty())
	{
		pair<int,int> p=q.front();
		q.pop();

		for (int i=0; i<4; i++)
		{
			int ny=p.first+dy[i],nx=p.second+dx[i];
			if (ny>=0 && ny<m && nx>=0 && nx<n)
				// if the target cell is not visited before
				//    and the elevation difference is within D
				//    push the cell into the queue
				if (!mark[ny][nx] && abs(mat[p.first][p.second]-mat[ny][nx])<=d)
				{
					q.push(make_pair(ny,nx));
					mark[ny][nx]=1;
				}
		}
	}
}

// check if all waypoints are reachable with elevation difference D
bool reachable(int d)
{
	// reset the grid that keeps the reachable points
	for (int i=0; i<m; i++)
		for (int j=0; j<n; j++) mark[i][j]=0;

	floodfill(d);

	// check if there is any unreachable waypoints
	for (int i=0; i<m; i++)
		for (int j=0; j<n; j++)
			if (wp[i][j] && !mark[i][j]) return false;
	return true;
}

int main()
{
	ifstream fin("ccski.in");
	fin >> m >> n;
	for (int i=0; i<m; i++)
		for (int j=0; j<n; j++)
			fin >> mat[i][j];
	for (int i=0; i<m; i++)
		for (int j=0; j<n; j++)
		{
			fin >> wp[i][j];
			// keep one of the waypoints as the starting point
			if (wp[i][j]) wy=i,wx=j;
		}
	fin.close();

	// binary search
	int dmin=0,dmax=1000000000;
	while (dmin<dmax)
	{
		int d=(dmin+dmax)/2;
		if (reachable(d)) dmax=d;
		else dmin=d+1;
	}

	ofstream fout("ccski.out");
	fout << dmin << "\n";
	fout.close();
}

In addition to being solvable by a floodfill wrapped inside a binary search, this problem also has a nice solution using ideas from minimum spanning trees. Whereas a standard shortest path between two nodes in a graph minimizes the sum of the edge weights along the path, a so-called "bottleneck" shortest path minimizes the largest edge weight along the path. One can compute bottleneck shortest paths using a variant of Dijkstra's algorithm (which is actually the same as the minimum spanning tree algorithm of Prim/Jarnik). Moreover, a nice property of minimum spanning trees is that the unique path through an MST between any two nodes is actually a bottleneck shortest path; hence, computing a minimum spanning tree effectively computes bottleneck shortest paths between all pairs of nodes.

Armed with the insight above, we can now solve this problem by computing a minimum spanning tree, say by using Kruskal's well-known algorithm that adds edges in sorted order. We first pre-sort all the edges (differences between adjacent cells) and then add them one by one to our MST. The only difference is that instead of running this process to completion to build a full MST, we stop at the moment when our partial MST contains all the waypoints. The last edge weight we added will give us the value of D we seek, since we need at least this value of D to connect all the waypoints together. The running time for this approach would be the same as that of Kruskal's algorithm, which is dominated by the time required to sort the edges: O(MN log MN).