USACO Cow Tours Problem

I had been trying to solve the problem named Cow Tours on USACO for the last 3 months. I had a hard time figuring out some of the issues I came across, so I decided to do a writeup about it.

Solution

The basic solution had the pure brute force approach of trying to place an edge between any two nodes on the given graph. For each such possible edge, once it is added to graph, the longest of the shortest paths on the modified graph is computed. Finally the temporarily added edge is removed. If one maintains a variable for minimum diameter and updates it using each of the diameters found while adding and removing temporary edges to the graph, the solution is found.

Complexity

Considering the purely brute force approach, the algorithm I outlined in the previous paragraph takes O(n4) time. I tried to figure out a way to reduce the computation of the longest of the shortest paths, but could not find anything.

Eventually I came across an algorithm to find out the diameter of an undirected tree in O(n), which basically used Breadth-First Search(BFS) in a manner that utilizes priority queues. ( Don't know why they called it BFS and not Dijkstra's ) The algorithm conducts a search from any node of a connected component of the tree. Then it conducts a second search, this time starting from the node which had the highest shortest path cost in the first search. It's proof is explained here in a great manner.

This meant that the complexity of my solution dropped to O(n3logn). Yet, USACO's judge system was not that merciful.

Issues with Submission

My solution initially exceeded the given time limit by about 1.5 seconds. After making all the possible optimizations I could think of, it was still exceeding the limit with .05 seconds. After doing my best and getting nowhere, I decided to transform the code from C++ to C. It meant that I couldn't use stuff like std::priority_queue<> of Standard Template Library(STL), but it did work in the required time, and was accepted by the judge.

Short of the time limit issue, the potential issues a solution with this approach may face include the usage of float instead of double, and neglecting the fact that the problem questions the minimum value of the maximum diameter of the graph among the diameters of the connected components.

Most online sources do not work on this issue, since the diameter algorithm is not that intuitive, and the O(n3logn) complexity is probably deemed too high to give a try. (i.e. it doesn't work even in C++ soon as we start using any of STL data structures)

Endorsed Solution

As you may have encountered, USACO lets its users view the analysis of a problem once he/she solves it. Now, as I have been benefiting from their work thus far, I will not go against their philosophy and will not share with you the endorsed solution here. However, having spent months on this problem, to those of you who have been dealing with it as long as I have, I would not feel guilty about hinting you in the direction of Floyd-Warshall's algorithm, and urge you to think in terms of connected components as much as you may have been thinking in nodes' terms.