
Match Editorial 
SRM 131Thursday, January 30, 2003
Match summary
With the Collegiate Championship only a few weeks down the road,
competition attendance is growing steadily. Over 400 coders registered
for SRM 131 including top ranked competitors Yarin, John Dethridge,
SnapDragon, and ZorbaTHut. Competition was fierce, with the top scoring
spot changing hands multiple times in the coding, challenge, and system
test phases. In the end, Yarin prevailed with SnapDragon and John Dethridge
close behind.
As a departure from the standard types of problems used, this competition
featured an assorted set of algorithmic solutions unlike those seen in
previous competitions. It is very exciting to see competitors struggle with
problems that challenge their minds, forcing them to develop innovative
techniques with little time to think. For example, the division 1 hard
problem required the efficient generation of minimum weight Steiner trees,
a topic none of the top ranked coders seemed to have experience with. It was
this problem that ended up deciding who won SRM 131.
The Problems
CSCourse
Used as: DivisionII, Level 1:
Value

250 
Submission Rate

252
/
264
(95.45%)

Success Rate

138
/
252
(54.76%)

High Score

stingant for
245.21 points

Reference Solution: brett1479 in the practice room
Implementation
In this problem, coders were asked to determine the final letter grade a
student should receive given their exam scores, and the number of TopCoder
competitions they competed in. The intelligent Professor M. forces his
students to compete in at least 3 competitions per semester. Their final
grade will fall a single letter if they compete in less than 3 competitions.
To solve this problem one must add up the given scores and then account for
the number of competitions.
SpellCheck
Used as: DivisionII, Level 2:
Value

500 
Submission Rate

196
/
264
(74.24%)

Success Rate

96
/
196
(48.98%)

High Score

Karshikinpa for
474.04 points

Reference Solution: brett1479 in the practice room
Implementation
Here coders needed to implement the spelling rule: I before E except after C.
To make things slightly more complicated, the I's, E's, and C's can be either
capital or lowercase. In addition, the rule must be continually applied until
every place where E comes before I is removed unless after C. For example,
after a single application of this rule to the string "eeei" we end up with
"eeie". There is still an I before an E so we must apply the rule again
producing "eiee". Applying the rule a final time produces the string "ieee"
and we are done. Code to solve this problem basically consisted of swapping i's
and e's until no more swaps could be made, is in the practice room under brett1479.
FloorTile
Used as: DivisionIII, Level 3:
Value

1000 
Submission Rate

119
/
264
(45.08%)

Success Rate

103
/
119
(86.58%)

High Score

vipernky for
996.22 points

Used as: DivisionI, Level 1:
Value

300 
Submission Rate

126
/
136
(92.65%)

Success Rate

109
/
126
(86.51%)

High Score

Yi Zhang for
298.28 points

Reference Solution: brett1479 in the practice room
Implementation
Given a 2^k by 2^k square floor, you have been asked to lay down tiling
covering the entire area incurring the smallest cost. The two types of
tiles at your disposal are: a 1 by 1 square tile, and a 2 by 2 tile with a
1 by 1 square removed from one of its corners (an Lshaped tile). The
Lshaped tile may be flipped or rotated in any fashion. In addition, both
the small square shaped tiles, and the Lshaped tiles cost $1 to lay down.
To solve this problem, one could theoretically try to bruteforce every
possible arrangement of tiles, but a simpler method is possible. Consider
the solution to the 2 by 2 square floor below. Using a single Lshaped piece
with a square piece costs a total of $2. The key insight here is to realize
that the 4x4 case can be produced by placing four of the 2x2 cases next to
each other. We can align the single squares in each of the four 2x2 components
so that they lie in the middle of the resulting 4x4 block thus giving us the
opportunity to use another Lshaped block. In other words, when four of the
2x2 diagrams are used to produce the 4x4 diagram 1, we aligned the B's to all
occur in the middle. In 4x4 diagram 2, three of these B's are replaced by the
Lshaped E block. Different letters have been used to illustrate the different
blocks. Furthermore, we can align four 4x4 blocks to produce a 16x16 block.
4x4 diagram 3 shows how I have slightly changed the organization of diagram 2
to place the single leftover square 'F' in the lower righthand corner allowing
four diagram 3 blocks to be connected to form a 16x16 block analogously to how
we generated the 4x4 block.
2x2 4x4 (diagram 1) 4x4 (diagram 2) 4x4 (diagram 3)
   
AB AAAA AABB AABB
AA ABBA AEEB AEEB
 ABBA DEFC DECC
AAAA DDCC DDCF
  
The moral of this story is, you never need to use more than a single square in
any of the problem sizes. Thus the answer can be calculated by finding the
total area, dividing by 3, and then adding 1 for the remaining square block.
RedChart
Used as: DivisionI, Level 2:
Value

500 
Submission Rate

121
/
136
(88.97%)

Success Rate

73
/
121
(60.33%)

High Score

SnapDragon for
480.25 points

Reference Solution: brett1479 in the practice room
Implementation
In this problem, coders were asked to find the minimum size chart containing
rating information for a bunch of "red" ranked TopCoder competitors. If a
coder is red for a period of time, the chart must contain a contiguous bar
from the column designating the start of this period, to the column designating
the end. Since no overlap may occur, if multiple competitors are red
simultaneously, multiple rows must be used. Arranging these bars such that the
fewest number of rows is used solves the problem. To accomplish this, we sort
the ranges by starting competition numbers and loop through them in ascending
order. When processing each item, if one of the rows we have already used is
free we can place the bar in that row. Otherwise we must allocate a new row.
ChipWire
Used as: DivisionI, Level 3:
Value

1000 
Submission Rate

24
/
136
(17.65%)

Success Rate

8
/
24
(33.33%)

High Score

Yarin for
777.13 points

Reference Solution: brett1479 in the practice room
Implementation
In computer chips, wires usually must travel only horizontally and vertically
between two points. When trying to build a chip such that all parts on it are
connected, many wires must often be used. These parts and wires are often
modeled by vertices and edges in a graph. In order to produce a more efficient
wiring scheme extra vertices, called Steiner points, may be added allowing for
cheaper solutions. To solve this problem, we realize that the only points that
need be considered share x and y coordinates with the given points. For example,
if the points given are (5,5), (0,0) and (10,0) the xcoordinate of added points
must be 0, 5, or 10, where as the ycoordinate must be 0 or 5. Since the maximum
number of input points is 5, the largest number of added points we have to consider
is 25. In addition, we will never need more than 5 added points to solve this
problem, so we can check all subsets of these 25 elements up to 5 elements
determining which set of added points produces the best answer. Each time we
want to check, we can run a minimum spanning tree algorithm such as Prim's
algorithm.
By
brett1479
TopCoder Member