Saturday, December 14, 2013

USACO Training Problem: Cow Tours

Here's an interesting graph theory problem:
http://cerberus.delos.com:790/usacoprob2?a=osacVNAncMv&S=cowtour

What makes this problem hard is the incorrect assumption that many people (including me) make.

The first part is relatively simple. The idea is to calculate the Euclidean distances between connected vertices and store these distances in a matrix. Even though the problem gives that vertex i is not connected to itself, we can assume it is with no harm. Thus, dist(i,i) = 0 for all i.

The next step is to use Floyd-Warshall on the matrix of distances such that for each i,j, dist(i,j) stores the shortest path from vertex i to vertex j. dist(i,j) is infinity if j is unreachable from i.

Make an array of size n that stores the farthest distance that can be traveled from a given vertex taking only shortest paths (not counting infinity). Thus farthest[i]=max_not_infinity(dist[i]).

It is advantageous but not necessary to find the diameter of each field by precalculation.

Keep track of a global variable that has initial value infinity.
Finally loop through the entire matrix, and every time dist(i,j)==infinity (which means that edge(i,j) does not exist and is a candidate to be filled in), find the maximum of the following values:
d1 - farthest[i]+distance(P_i,P_j)+farthest[j]
d2 - max(diameter[i],diameter[j])  //This is the part that most people forget
where distance(Point a, Point b) returns the Euclidean distance between two points and where P_i and P_j denote the two points that are connected by edge (i,j).
Now update the global variable if max(d1,d2) < current value of global variable.

*If you are getting an error on test case 7 or higher, it is probably because you overlooked the value d2, and to see why it is necessary consider the test case (from TopCoder):

4
0 0
10 0
20 0
10 1
0100
1010
0100
0000

The answer should be: 20.000000
Runtime: O(N^3)


2 comments:

  1. Thanks for posting this info. I just want to let you know that I just check out your site and I find it very interesting and informative. I can't wait to read lots of your posts. puerto maldonado amazon tours

    ReplyDelete
  2. Just admiring your work and wondering how you managed this blog so well. It’s so remarkable that I can't afford to not go through this valuable information whenever I surf the internet! Rainbow Mountain Peru

    ReplyDelete