Get Time
statistics_w  Match Editorial
SRM 240
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 Problems

Pronunciation discuss it
Used as: Division Two - Level One:
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.

TravellingByTrain discuss it
Used as: Division Two - Level Two:
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)
Used as: Division One - Level One:
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.

MoneyExchange discuss it
Used as: Division Two - Level Three:
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.

WatchTower discuss it
Used as: Division One - Level Two:
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.

MailArchiving discuss it
Used as: Division One - Level Three:
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.

By Jan_Kuipers
TopCoder Member