USACO NOV06 Problem 'cowtag' Analysis

by Rob Kolstad

The 'cowtag' problem requires one to search a list of cows repeatedly to find the cow nearest to some other cow. The program breaks down into:

• input
• distance caching
• eliminating the cows one by one

The input section is simple: just grab 'n' and the x,y coordinates.

Because this problem depends on speed, first observe that the distance is, for sorting purposes, equivalent to sorting on the square of the distance (thus avoiding n*n/2 sqrt calls). Second, observe that the distance is symmetric, so we can calculate the distance matrix twice as fast as otherwise.

All that remains is 'playing cow tag'. An outer loop runs n-1 times, starting at the first cow (the cows are numbered 0..n-1 on the inside of this solution). A 'boolean' array named "dead" keeps track of which cows are not dead yet. The inner loop searches non-dead cows for the closest one.

The answer is printed as one more than the 0-offset cow id.