Match Editorial

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 Problems

Value	250
Submission Rate	240 / 291 (82.47%)
Success Rate	111 / 240 (46.25%)
High Score	fluffy_ for 238.96 points (6 mins 9 secs)
Average Score	180.79 (for 111 correct submissions)

To check whether a word is pronouncable, most people looped through the letters of a word, checking whether i-th, (i+1)-th and (i+2)-th letters are all consonants and checking whether the i-th 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.

Value	500
Submission Rate	86 / 291 (29.55%)
Success Rate	18 / 86 (20.93%)
High Score	Egor for 429.56 points (11 mins 54 secs)
Average Score	275.28 (for 18 correct submissions)

Value	250
Submission Rate	182 / 193 (94.30%)
Success Rate	96 / 182 (52.75%)
High Score	Zis for 228.02 points (8 mins 59 secs)
Average Score	168.68 (for 96 correct submissions)

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:

• determine the departure time;
• check whether you can catch it this day or you have to wait until the next day;
• determine the arrival time and day;
• if the arrival moment is earlier than the best found sofar, update the earliest arrival moment.

In the end this gives the earliest arrival moment for the destination station.

Value	1000
Submission Rate	34 / 291 (11.68%)
Success Rate	2 / 34 (5.88%)
High Score	lschyt for 722.88 points (19 mins 12 secs)
Average Score	721.94 (for 2 correct submissions)

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 Floyd-Warshall 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.

Value	600
Submission Rate	48 / 193 (24.87%)
Success Rate	12 / 48 (25.00%)
High Score	Eryx for 486.18 points (14 mins 28 secs)
Average Score	345.78 (for 12 correct submissions)

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)-(x2-y2), just extrapolate this line segment to position x. So the tower must have height of at least

y1 + (x-x1) * (y2-y1)/(x2-x1).

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.

Value	900
Submission Rate	49 / 193 (25.39%)
Success Rate	22 / 49 (44.90%)
High Score	rem for 814.96 points (9 mins 22 secs)
Average Score	596.38 (for 22 correct submissions)

This problem asked for a dynamic programming approach. We call best[i][j] the minimal number of selections to archive e-mails 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 e-mail 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 e-mails. If we archive it together with an e-mail on position k, we cannot archive e-mails with positions smaller than k together with e-mails 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.