Match Editorial

With some of the fastest submission times, and some of the highest scores seen in recent times, the first round of the Collegiate Challenge 2004 proved to be an exciting event. An ambiguity in the medium problem which slipped past the testers and I caused quite a bit of confusion on what should have been a very simple medium problem. It ended up costing many dearly, as the success rate of the medium problem was much lower than the other two problems, and in fact, more people successfully submitted the hard problem than the medium. However, due to a very easy level 1 problem, the zero void did not consume otherwise eligible contestants as it did for some of the qualification rounds.

In just under 2 minutes, antimatter started off the match with a 199 point submission for the level 1. After that, watching the scoreboard was like watching the lights in a house turn on after a loud noise woke everyone up. Within a few minutes, almost every room had a score on the board. Oddly enough, very early on in the competition a green coder by the name of yuranlu had submitted all three problems, making it clear that his only intention for participating was to receive a free t-shirt. At the end of the coding phase, antimatter had edged out the favorite, tomek, by about 3 points. However, both coders weren't finished yet. tomek fought back with a challenge, which antimatter answered with his own. But late in the challenge phase, tomek submitted another challenge against the same coder, propelling him to his first tournament round win. Returning champion dgarthur, and tournament regulars ZorbaTHut and reid rounded out the top 5.

The Problems

Value	200
Submission Rate	363 / 376 (96.54%)
Success Rate	339 / 363 (93.39%)
High Score	antimatter for 199.03 points (1 mins 59 secs)
Average Score	178.66 (for 339 correct submissions)

Aloha! This problem asks you to identify words that only consist of a given set of characters. There are two parts to this problem -- the tokenization of the words, and the identification of Hawaiian words.

First, the tokenization. Java has the split method for string, and StringTokenizer, giving it an advantage. C++ users can use istringstream to parse the words. I'm not too familiar with C# and VB.net, so I'm not sure how it's done there. In any case, tokenization is a well-solved problem here at topcoder, and should be in every coder's library of knowledge.

Next, the identification of Hawaiian words. The easiest way to do this is with regex in Java:

if(word.toLowerCase().matches("[aeiouhklmnpw]+"))

Of course, checking each character is the language agnostic method, and works very efficiently. The last step is to add all matched words to an array and return that array.

Value	500
Submission Rate	230 / 376 (61.17%)
Success Rate	109 / 230 (47.39%)
High Score	tomek for 469.94 points (7 mins 16 secs)
Average Score	311.32 (for 109 correct submissions)

This problem is pretty simple to solve -- as long as you are solving the correct problem! A subtle ambiguity in the problem statement made the problem seem more difficult than it really was. For those of you who missed the broadcast, the problem statement will be updated soon to make the statement clear for the practice room. In short, you are looking to make flowers which are closest to the front of the garden as tall as possible, not trying to put the tallest flower as close as possible.

Sorting the flowers in this garden isn't as simple as writing a sort comparison routine, because you can't always tell what the ordering will be with just two elements. In reality, the ordering is easy to compute if you think about the flowers one at a time. The first step is to determine which flowers cannot go in front of other flowers. This is done by comparing the bloom date of each flower with the bloom and wilt date of every other flower. If two flowers conflict, then the bloom date of one will lay between the bloom and wilt date of the other. Within a conflict, the larger of the two cannot be placed in front of the other, or blockage will occur.

When figuring out which type of flower to place next, you can only place flowers that can go in front of all the flowers left to place. Of those, you should place the type which is tallest. For the next type, the flower type just placed no longer can be blocked, so it could allow more flower types to be placed. Because there can be no circular dependencies, this algorithm can be used to place the entire garden.

Value	1000
Submission Rate	134 / 376 (35.64%)
Success Rate	119 / 134 (88.81%)
High Score	mathijs for 958.39 points (5 mins 58 secs)
Average Score	731.11 (for 119 correct submissions)

A simple-minded simulation of rock skipping, this problem asks you to determine how successful the skipping of a rock will be on a lake riddled with lily pads. This problem requires DP or memoization as a simple DFS would most certainly time out. There are two ways to represent the state of the system. One is to represent each state as the distance from the shore, combined with the number of skips left in a 2 dimensional array. The other method is to reduce the lake into one pattern, and assume rocks that travel off the edge of the pattern on the right, re-enter the lake from the left. Since the pattern repeats every n characters, the space which is D spaces from the shore can be represented by the pattern space D % n. In this method, each skip creates a new set of probabilities which continues with the next step.

I'll go over the specifics of the first method. If each skip travels the maximum distance, the furthest space acheived will be the sum of all the numbers from 1 to maxDist. The formula for this sum is maxDist * (maxDist + 1) / 2. With maxDist = 100, this comes out to a 5050x100 array.

The base is the first lake space, which is represented by state[0][maxDist], and we set its probability to 1.0. Then for each lake space and each number of skips left (n), the probability is spread over the n spaces ahead evenly. If we traverse the lake in increasing distance from the shore, then we will be sure to get to each space and each number of skips left after all the spaces it depends on. However, we will not process spaces which have lily pads, and each time the number of skips left reaches 0, we add the probability to a global variable which represents the successful rock skips. After processing the entire lake, the global variable will contain the probability of a successful skip.

The second method is similar, but I'll leave it as an exercise for the reader.