
Match Editorial 
SRM 117Tuesday, October 22, 2002
The Problems
DrinkMix
Used as: DivisionII, Level 1:
Value

250 
Submission Rate

133/196 (67.86%)

Success Rate

85/133 (63.91%)

High Score

androm for 244.74 points

Reference implementation: fvolny4
For this problem, one only has to work with the amount of rum in the two bowls the punch can be ignored). That is, one should have two variables, rumAand rumB, representing the number of units of rum in bowls A and B, respectively. Initially, rumA = 360000 and rumB = 0.
Now, for each time the bowls are mixed, 120000 units of the liquid in bowl A are poured into bowl B. There will always be 360000 units of liquid in bowl A at the beginning of each mix. Thus one third of the units of rum in bowl A will be transferred to bowl B. That is, rumB += rumA / 3, and rumA = rumA / 3. This brings the total volume of liquid in bowl B to480000 units.
Then 120000 units of liquid are poured back into bowl A. In this case, one fourth of the units of liquid in bowl B are poured into bowl A. Thus, rumA += rumB / 4 and rumB = rumB / 4.
We simply repeat this simple process (which is just four lines of code) mixes times and return the final value of rumB.
BinTree
Used as: DivisionII, Level 3:
Value

1000 
Submission Rate

21/196 (10.71%)

Success Rate

4/ 21 (19.05%)

High Score

smai for 514.86 points

Reference implementation: smai
The easiest way to conceptualize this problem is to transform the input string array into a single array that can be indexed using the method described in the problem statement. To do this, initialize an empty array to represent the tree. If one needs to allocate storage initially (e.g., if using a java array), it helps to know that the exact size needed will be (1 << levels.length)  1. Iterate through each string in the input array, and for each token in this string add a value to the tree array. To represent entries of *, use a value that is not between 100 and 100 inclusive.
Next, iterate through each element of the tree array (skipping the first), verifying that the element does not violate any of the rules for a binary search tree. To do this we check the value against each of its ancestors. It helps to know the following information that can be determined from a value's index in the tree array (note that all indices are counting from 1 in the following):
 The parent of the element at index i is at index i / 2
 If i is even, then it is the left child of its parent; if i is odd, it is the right child of its parent
So, for each element we check it against its ancestors, noting whether it is in the left or
right subtree of each ancestor. If i is the 1based index of the current element,
initialize j = i. While j > 1, we compare the value at i to the
value at j / 2. We do the division after the comparison so that we can determine
which subtree of j / 2 that i is in (this information is lost after we
do the integral division). If j % 2 == 0 and the value at i (which would
be i  1 using 0based indexing) is greater than the value at j / 2
(which would be j / 2  1 using 0based indexing), then a rule has been violated.
Similarly, if j % 2 == 1 and the value at i is less than the value at
j / 2, a rule has been violated. Also note that if the value of i's
immediate ancestor is *, a rule has been violated. If you check this rule
properly, there's no need to check it for all ancestor's of i. To continue
to the next ancestor of i, divide j by 2.
If one can iterate through the elements from 2 to (1 << levels.length)  1
inclusive using 1based indexing without finding a rule violation, then the tree is valid. Otherwise,
return the 1based index of the first element found that violates a rule. The only trick
is to keep the 0based and 1based indexing straight. The sample cases are sufficient for
working this out.
Piano
Used as: DivisionII, Level 2:
Value

550 
Submission Rate

81/196 (41.33%)

Success Rate

46/81 (56.79%)

High Score

rschutt for
495.06 points

Used as: DivisionI, Level 1:
Value

300 
Submission Rate

125
/
136
(91.91%)

Success Rate

100
/
125
(80%)

High Score

Saxophonist for
281.77 points

Reference implementation:
Saxophonist
Reference implementation:
NDBronson
There are two basic methods for solving this problem. The first is to simply
hard code a mapping of keys to scales for all the possible inputs. The mapping
is as follows:
C > C D E F G A B C
B# > ERROR
C# > C# D# E# F# G# A# B# C#
Db > Db Eb F Gb Ab Bb C Db
D > D E F# G A B C# D
D# > ERROR
Eb > Eb F G Ab Bb C D Eb
E > E F# G# A B C# D# E
Fb > ERROR
F > F G A Bb C D E F
E# > ERROR
F# > F# G# A# B C# D# E# F#
Gb > Gb Ab Bb Cb Db Eb F Gb
G > G A B C D E F# G
G# > ERROR
Ab > Ab Bb C Db Eb F G Ab
A > A B C# D E F# G# A
A# > ERROR
Bb > Bb C D Eb F G A Bb
B > B C# D# E F# G# A# B
Cb > Cb Db Eb Fb Gb Ab Bb Cb
This is simple enough, particularly if one has this mapping already available.
However, for those that did not, the second method must be used.
This method uses the table given in the problem specification:
1 
C 
B# 
2 
C# 
Db 
3 
D 
 
4 
D# 
Eb 
5 
E 
Fb 
6 
F 
E# 
7 
F# 
Gb 
8 
G 
 
9 
G# 
Ab 
10 
A 
 
11 
A# 
Bb 
12 
B 
Cb 
It helps to note that each row represents a particular pitch, while the values
in that row represent valid representations for that pitch.
The first note of a scale will begin with the note specifying its key,
and we will start at the row containing the key.
To find the next note of the scale, skip ahead the appropriate number of
rows to find the row representing the next pitch of the scale. The
amount of rows to skip are: 2, 2, 1, 2, 2, 2, and then 1. Note that
this sums up to 12, and there are twelve rows in the table, so we will
always end up where we started.
For each note in the scale, we have to pick the appropriate representation.
If the previous note was A#, we need to pick a representation with
a B at the beginning of it. If the previous note was a G,
we need to pick a representation with a A at the beginning of it.
We simply check the available representations at the current row to see if
any begin with the appropriate note. If none do, then we return ERROR.
Otherwise we append that note to our string.
This is simple enough to implement once the table has been initialized properly
in the code. The rest is just handling the spaces between notes so that there
is no trailing space.
Tiling
Used as: DivisionI, Level 2:
Value

650 
Submission Rate

38
/
136
(27.94%)

Success Rate

22
/
38
(57.89%)

High Score

NDBronson for
540.33 points

Reference implementation:
jms137
To solve this problem we iteratively tile over portions of the floor (following
the rules given) until the entire floor is tiled. We then return how many
iterations it took. Thus the problem reduces to locating the rectangle that
should be tiled next.
A na•ve implementation would have six nested for loops: one for the top row
of a rectangle; one for the bottom row; one for the leftmost column; and
for the rightmost column; and then two more for loops to iterate through
all the tiles within these bounds. However, the na•ve solution will never finish
in time on a 50 x 50 input, as 50 ^ 6 is greater than 15 billion
iterations.
However, a more efficient implementation that is equivalent to the na•ve solution
is possible. Let h be the number of rows in the floor, and w
be the number of columns.
We iterate through each row and column (r, c) of the floor.
Initialize a variable rwidth to w.
If (r, c) is already tiled, skip it. Otherwise, we iterate through each
r <= r' < h such that (r', c) has not yet been tiled and
requires the same type of tile as (r, c). For each r' we find
the smallest c' < c such that (r', c') cannot be part of a
rectangle of the same type of tiles. If c'  c < rwidth, we update
rwidth with the value of c'  c. At this point we know the
dimensions of the largest possible rectangle with a topleft corner of (r, c)
and bottom row of r'. We can then compare it against the best rectangle
found so far, and update that if appropriate. The area is (r'  r + 1) * rwidth.
After a rectangle is chosen for tiling, we "tile" it by modifying the array in which
we store the floor information (e.g., marking with 'T' as in the examples
given in the problem statement).
RadioTower
Used as: DivisionI, Level 3:
Value

850 
Submission Rate

32
/
136
(23.53%)

Success Rate

18
/
32
(56.25%)

High Score

John Dethridge for
724.82 points

Reference implementation:
DjinnKahn
Like many Level 3 problems, the solution to this problem embodies dynamic programming.
That is, one can determine an appropriate algorithm via induction.
Suppose we sort the customers from left to right. Then suppose we already know the
minimum cost for reaching just the first customer, and the minimum cost for reaching
the first two customers, and so on up to the first n customers. Let these
costs be stored in an array cost such that cost[i] is the minimum
cost of reaching the leftmost i customers (and cost[0] = 0 is the
base case). Can we use this information to add a customer from the right?
In an optimal configuration, any tower that we build should always have a customer
located at either extreme end of its range (for towers of height one it's the
same customer on both ends). There's no sense in having the extent of the range
terminate somewhere in the noman's land between two customers. This means that
if we add any customer to the right of a set of other customers, then there must
exist a tower that just reaches this rightmost customer. The leftmost extent
of this tower's arrange must be the location of either the new customer or one
of the customers preceding it on the left.
We iterate through each of the customers that are to the left of the customer being
added. For each one, we compute the cost of erecting a tower that can reach that customer
and the new customer simultaneously (if the required height of such a tower exceeds the
maximum height, its cost is infinity). This gives a cost (not necessarily the minimum)
for covering all the previous customers as well as the new one. If we add a tower that
covers both customer i and customer n + 1, then the resulting configuration
costs cost[i  1] plus the cost of that tower. If we consider all these possible
configurations, as well as the configuration resulting from adding a tower of height 1
at the location of the new customer, we will encounter the one of minimum cost. We take the
minimum and store it in cost[n + 1].
Once the problem and its solution are understood, it is trivial to implement. Other dynamic
programming solutions are possible (I managed to come up with a very different O(n^2)
one during the match), but this is the simplest one I've seen. One mistake
that several people made (such as myself) was to implement their solution in such a way that an input
of no customers caused a runtime error. This shows how important it is to read carefully over the
notes and input constraints and consider their ramifications.