Saturday, April 30, 2005 Match summary This problem set gave competitors a hard time. The only problem with success rate over 50% was the division 1 easy... with 52,75%. At the end of the coding phase, 18 people submitted all three problems and antimatter, dgarthur and nicka81 were in the lead. But the challenge phase claimed over 60 submissions (natori was responsible for 7 of them) and systests even more. When the dust settled, only Eryx and bladerunner had three correct submissions and they took the top spots. nicka81 rounded out the top 3 with the help of 2 successful challenges. In division 2 no one was able to solve all three problems. Only two people solved the hard, first timer Weeblie and lschyt, and they took the top two spots. Third place was for fluffy_, also with the help of 2 successful challenges. The ProblemsPronunciationUsed as: Division Two  Level One:
To check whether a word is pronouncable, most people looped through the letters of a word, checking whether ith, (i+1)th and (i+2)th letters are all consonants and checking whether the ith and (i+1)th letters are vowels, that are different. You should ignore case doing this. In Java you can also solve it by using regular expressions. After this, just loop through the words and return the first one that isn't pronouncable or return an empty string if they all are. TravellingByTrainUsed as: Division Two  Level Two: Used as: Division One  Level One:
The key observation here is that in order to arrive at the destination station as early as possible, it is always good to arrive at each transfer station as early as possible. With this in mind, split each element of the timetable into the individual trains and process them as follows:
In the end this gives the earliest arrival moment for the destination station. MoneyExchangeUsed as: Division Two  Level Three:
This problem basically consisted of two parts. First you have to parse the input rates. It's convenient to give each money type a number and store the rates in an array rate[i][j], indicating the best rate from type i to type j. Next you have to find all combined best rates. To find them, you can use a slight variation of the FloydWarshall all shorthest paths algorithm: for (int k=0; k<N; k++) for (int i=0; i<N; i++) for (int j=0; j<N; j++) rate[i][j] >?= rate[i][k] * rate[k][j]; After this rate[numberOf(type1)][numberOf(type2)] contains the desired result. WatchTowerUsed as: Division One  Level Two:
This medium problem gave most coders a hard time, proving that geometry is always difficult. If you want to build the watchtower at a certain position x, it's not very difficult to find out the necessary height. You have to be able to watch over each piece of the landscape. To be able to oversee the piece of the landscape (x1,y1)(x2y2), just extrapolate this line segment to position x. So the tower must have height of at least y1 + (xx1) * (y2y1)/(x2x1). Taking the maximum of these terms over all pieces of the landscape results in the minimum height. But where to place the tower? You can show that you have to place it on either one of the given points or on a position where two of the (extrapolated) pieces of the landscape intersect. If you build it on another place, shifting it to either the left or the right will always result in a tower of at least the same height, as the picture shows. Working out these intersection points requires a little math. We can also do without this math: with the above observation you can also show that the minimal height is convex on each piece, so a ternary search also works. MailArchivingUsed as: Division One  Level Three:
This problem asked for a dynamic programming approach. We call best[i][j] the minimal number of selections to archive emails i to j, not including j. If j equals i, the range is empty, so the result is 0. If j is greater than i, we can express the result in smaller pieces. To do so, we note that we have to archive email i at some time. We can archive it on its own, giving the result 1 + best[i+1][j], or we can archive it together with equal emails. If we archive it together with an email on position k, we cannot archive emails with positions smaller than k together with emails with positions greater than k, so this results in best[i+1][k] + best[k][j] Taking the minimum of these terms results in the desired answer. The easiest way to implement this is recursion with memoization. 
