Saturday, October 16, 2004 Match summary In division 1, coders had a pretty easy time with the easy and medium problems, but no one was able to get a tricky hard problem. As a result, the top scores were quite close going into the challenge phase. Not surprisingly, the results ended up being determined by challenges, and wleite was able to get 4 of them, to take first. kirkifer took second with 5 challenges, and AdrianKeugel was a distant third, with only one challenge. In division 2, coders had an easier time, as 40 coders solved the hard problem. 35C4P3 took first by a respectable margin, followed by first timer Rud0lf and Artist_ in second and third, respectively.
The ProblemsDivisorDigitsUsed as: Division Two  Level One:
The key to this problem is to first represent the input integer as a string. Once that is complete, loop through each character and test for divisibility. Just be sure not to try 0, since your divisibility check may throw an exception. MailboxUsed as: Division Two  Level Two:
For each address, we need to check and see if that address can be formed from the letters in the collection. There are a number of ways to do this. Perhaps the simplest is to write two nested loops, keeping track of which letters have been used from the collection: bool[] used = new bool[collection.size()]; for(int i = 0; i<address.size(); i++){ bool found = false; for(int j = 0; j<collection.size(); j++){ if(!used[j] && collection[j] == address[i]){ used[j] = true; found = true; break; } } if(!found){ ret++; break; } }Another way to solve this, which has a faster runtime (unnecessary in this case), is to sort both the characters in collection and the characters in address: sort(collection); sort(address); int ptr = 0; for(int i = 0; i < collection.size(); i++){ if(ptr < address.size() && collection[i] == address[ptr]){ ptr++; } } if(ptr!=address.size())ret++;Thesaurus Used as: Division Two  Level Three: Used as: Division One  Level Two:
The basic algorithm for this problem is relatively straightforward. The basic idea is to merge entries in the thesaurus until no more entries can be merged: bool merged = true while(merged){ merged = false for each pair of entries (i,j){ if(entries i and j share 2 or more words){ merge entries i and j merge = true } } }The details of the implementation, however, leave a lot of room for variation. There are a number of different ways to represent the entries. You can use arrays of strings, or more complicated data structures. If you use your language's built in set data structure, you can use the intersection method and the union method, which make it easy to determine if two entries share 2 or more elements, and also easy to merge two entries. Using arrays to represent the entries is probably a bit more work, but its not too hard to code. In the end, you need to sort words in the entries, and then sort the entries, but this is just standard sorting, with no bells or whistles. Diving Used as: Division One  Level One:
First, you should parse the input by finding the 4 ratings that are known.
While you can use floating point numbers, you have to be careful, and its safer
to just stick with integers so that you end up storing the 4 ratings as integral
numbers of 10^{th}s. For example, you parse 4.5 as 45 10^{th}s.
Similarly, you store the degree of difficulty and the needed score as integral
values. By storing the degree of difficulty and ratings in 10^{th}s,
and needed in 100^{th}s, the multiplication works out the same so that
multiplying the ratings by the degree of difficulty can be directly compared to
needed.
If ?.? is a middle rating, then we discard the highest and lowest given ratings and find the sum of the remaining two given ratings, sum. So, the final score is degree of difficulty * (sum + x) where x is the value of the ?.?. Since this has to be greater than or equal to need, we have: degree of difficulty * (sum + x) >= need > x >= (need  degree of difficulty*sum)/(degree of difficulty) So, we pick the smallest valid x that satisfies this inequality, and make sure that it is not greater than the largest given rating (which was discarded). Finally, there is the case where the ?.? is the highest score. In this case, the final score is the sum of the 3 highest given ratings times the degree of difficulty. If this is high enough, then return the value of the highest given rating. If none of these three cases works, return "1.0". ShortCut Used as: Division One  Level Three:
Clearly, there is no way to evaluate all possible offroad paths, so we need to figure out what sort of cases warrant going offroad. First off, let's look at the general case where we start at some point on one road, and travel offroad to some part of another road, and then travel to the endpoint of the destination road. Assume that our origin point is fixed, and we want to figure out the optimal point to head for on the destination road. Also, assume that the optimal point is somewhere in the middle of the destination road, not one of its endpoints.
In this case, the time required to travel from the start to finish is: Therefore, we find that an optimal path need never travel from the midpoint of
one road to the midpoint of another road. Each offroad leg of the trip will either
start or end at an endpoint of one of the roads. Once you come to that
conclusion, there are a number of ways to proceed. One way is to find all of
the important points along the roads. A point is important if it is an
endpoint, of if it is a point in the middle of a road such as that in the first
figure (noting that start and finish can be swapped in the figure, and the case
is essentially the same). Once you find all of the important points, you can run
any standard graph algorithm. However, finding all of the important points is a
bit tricky with all the geometry, so I elected to take an approach that required
less geometry. 
