
Match Editorial 
2004 TopCoder Collegiate Challenge
Online Round 1Saturday, February 28, 2004
Summary
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 tshirt. 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
Hawaiian
Used as: Level One:
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 wellsolved 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.
FlowerGarden
Used as: Level Two:
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.
RockSkipping
Used as: Level Three:
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 simpleminded 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, reenter 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.
By
schveiguy
TopCoder Member