
Match Editorial 
SRM 141Thursday, April 10, 2003
Match summary
SnapDragon brought his A game to this match, beating everyone by over 200 points. Most people were
able to get the first two problems, but dynamic programming is always a little tricky, and after
solving the first two problems, few people had time to finish the third. sjelkjd also showed why
he made it to the CC finals, taking second overall, helped largely by his 4 successful challenges.
Over in Division 2, first timer dary also won by over 200 points, with three fast submissions, and
a challenge.
The Problems
StatementCounter
Used as: Division II  Level 1:
Value 
250 
Submission Rate 
212/227 (93.39%) 
Success Rate 
195/212 (91.98%) 
High Score 
Ceranith for 249.20 points 
Implementation
Once your realize what the problem is asking for, it is pretty trivial. All you have to
do is count the number of semicolons in a String[] (vector <string>). So, its just two nested
loops, and then a check to see if a character is a semicolon.
PrioritySort
Used as: Division II  Level 2:
Value 
500 
Submission Rate 
108/227 (47.58%) 
Success Rate 
47/108 (43.52%) 
High Score 
Sabu for 464.99 points 
Implementation
This problem was a little bit tricky if you didn't know the sorting functions in your language of
choice. The simplest way to do it was to write a comparator function and then use Arrays.sort()
in Java or stable_sort() in C++. Your comparator method can be made pretty simple, since all of
the numbers are exactly one character. This causes the ith number in the string to be character 2*i.
So, you could just loop through all the elements of priorities, and compare the appropriate
characters  no tokenizing required.
Widget
Used as: DivisionII, Level 3:
Value 
1000 
Submission Rate 
37 / 227 (16.30%) 
Success Rate 
28 / 37 (75.68%) 
High Score 
dary for 782.05 points 
Used as: DivisionI, Level 2:
Value 
500 
Submission Rate 
93 / 127 (73.23%) 
Success Rate 
79 / 93 (84.95%) 
High Score 
ZorbaTHut for 468.58 points 
Implementation
Widget layout can be a pretty complicated problem, especially when you have
widths that are percentages, and you want all of the coordinates to be relative
to the window size. However, this problem simplified widget layout be forcing
all of the lines to be either in absolute positions, or else offset an absolute
amount from another line. Also, since there were no dependency loops, a straight
recursive approach allowed you to easily find the coordinates of the edges in
question. If the edge is relative to another edge, then recursively find the
position of that edge, and then add the offset, to get the position for the edge
you want. If the position of an edge is not relative to any other edge, then you
are done, and can just return the position. Using this approach, you can easily
find the location of any edge. The last thing you have to do is a little error
checking. First, go through all vertical and horizontal edges, and make sure
they are not at negative positions. Last, find the coordinates of the widget,
and make sure that the right is to the right of left, and the top is above
bottom. If everything checks out, just return the location of the widget.
Bounce
Used as: Division I  Level 1:
Value 
250 
Submission Rate 
118/127 (92.91%) 
Success Rate 
103/118 (87.29%) 
High Score 
Yarin for 236.85 points 
Implementation
This problem required you to do a little bit of physics, and to determine at what integral speed a
bouncing ball would be above a certain height after traveling a certain distance. The obvious thing
to do is to loop through every speed, starting at 1. You then have to determine the amount of time
the ball will take to reach the other building, at each speed (time = distance / velocity).
If the time is less than 5, there is no way that the ball will bounce before getting to the
other building, and you should return 1. Next, since the ball first bounces after 5 seconds,
subtract 5 from the time. Now, the ball bounces every 10 seconds, so take the remaining time
modulo 10. This gives us the amount of time the ball has been in the air after the last bounce.
We then plug this into the formula given in the problem statement (Y = 50*b +g*b*b/2), and if Y
is greater than height, return the current speed.
LazyGuitar
Used as: Division I  Level 3:
Value 
1000 
Submission Rate 
19/127 (14.96%) 
Success Rate 
10/19 (52.63%) 
High Score 
SnapDragon for 715.61 points 
Implementation
SnapDragon showed why he is the highest rated TopCoder by destroying the competition on this problem.
The first thing that should always pop into your mind when you see a problem like this is Dynamic
Programming. We clearly can't try all possible sequences of positions, so we must come up with some
recurrence about how the cumulative cost after playing a chord in a particular position depends on
the costs of the previous chord. If you are experienced with dynamic programming, you shouldn't have
too much trouble seeing that:
if(chord i can be played in position j)
cost(i,j) = min over k(cost(i1,k)+abs(jk)+(1 if j!=k))
else
cost(i,j) = infinity
Where cost(i,j) represents the cost of playing i+1 chords, and ending up in position j. Since we can
start in any position, when i = 0, we have cost(0,j) = 0 if chord 0 is playable in position j, and cost
(0,j) = infinity otherwise. The recurrence is pretty easy to implement, and all that we have left to
do is write a function to determine if a chord can be played in a given position. At first glance,
it seems that a greedy approach to assigning notes would work, but then you have the open notes,
which make things tricky. Since there are only 6 strings, the simplest way to determine if a chord
is playable is probably just to try all possible assignments of notes to strings. 6! is pretty small,
so timeout shouldn't be an issue. Then, all you have to do is figure out what to return. Since you can
end in any position, you want to return the minimum cost for any position to have played all chords.
If this value is infinity, return 1.
One noteworthy thing to watch for is that there are only 24 frets. So, if position is 23, you can
only use frets 23 and 24. It turns out that there is no reason to ever be in a position above 21.
By
lbackstrom
TopCoder Member