
Match Editorial 
SRM 106Thursday, August 1, 2002
The Problems
DivisionII, Level 1: Insomnia (250pt)
Submission rate  91% (169/186)
Success rate  93% (158/169)
Avg. Score  216.78pt
Best Score  dre2xl, 248.09pt
I'll have to try this creative cure for insomnia sometime...
This problem can be simply solved by looping through all of the minutes and adding or
subtracting sheep (+15 or 10) depending on where you are in the count.
For the first hour, third hour, fifth hour, etc. add 15 sheep per minute.
At all other times subtract 10 sheep per minute. Just make sure to switch
from +15 to 10 and viceversa every 60 minutes.
DivisionII, Level 2 & DivisionI, Level 1: Auction
DivII (500pt)
Submission rate  75% (140/186)
Success rate  59% (83/140)
Avg. Score  313pt
Best Score  leibniz, 440.19pt
DivI (250pt)
Submission rate  99% (106/107)
Success rate  79% (84/106)
Avg. Score  196.67pt
Best Score  b0b0b0b, 241.02pt
A clever scheme for selling "counterintuitive math problems" to math geeks was
described in this problem. Given a number of email bids for a math paper, the
task is to find the maximum possible profit, also given that the selling price
will be equal to the maximum nonwinning bid, and anyone bidding higher than the
maximum nonwinning bid will pay the nonwinning bid price for the paper.
Probably the fastest and simplest way to solve this problem is to make a copy of
the bids input, sort the copy, then iterate through the copy, looking for consecutive
elements that are nonidentical. In the event that consecutive elements differ,
compute the profit which would ensue from using the lower of the two elements as the
maximum nonwinning bid. If the profit is greater than the maximum profit calculated
so far, then store the maximum nonwinning bid. After this loop simply generate the
output by finding all of the indices with bids greater than the maximum nonwinning bid.
DivisionII, Level 3: Handles (1000pt)
Submission rate  35% (66/186)
Success rate  23% (15/66)
Avg. Score  481.4pt
Best Score  Gojira, 578.12pt
This problem was a straightforward parsing exercise to determine the complexity of
a given string based on 11 predefined rules. None of these rules in themselves poses
an extreme challenge, but coding all of them takes some time, and of course it only
takes one bug to mess up your solution. Familiarity with easytouse text parsing
routines in the language of your choice would be a definite asset for solving this problem in a timely fashion.
DivisionI, Level 2: Dance (500pt)
Submission rate  49% (52/107)
Success rate  63% (33/52)
Avg. Score  283.76pt
Best Score  leibniz, 440.19pt
TopCoders need to have fun at dances too...
This problem asked you to find the total number of distinct combinations of
dancing pairs, given a list of who everyone would be willing to dance with.
The problem can be broken down by counting the number of distinct combinations
with just 1 pair, the number of distinct combinations with 2 pairs, and so on.
There are at most 10 elements to the input of this problem, so no more than 10
people are willing to dance with others. One good way to keep track of things
for this problem (inspired by kv) would be to parse the input strings and form
a bitmask for each of the dancers which describes which other dancers they were
willing to dance with. Then start an array list whose elements describe all of
the various dance combinations. Loop through all of the possible dancing pairs
(in which person A is willing to dance with B and viceversa) and if there is an
element in the list whose bitmask does NOT indicate person A dancing with person B,
then add an element to the list whose bitmask is the same as the previous bitmask,
in addition to including person A dancing with person B. Also create an element in
the list whose mask indicates just A dancing with B. The total number of dance combos
will just be the number of elements in the list.
DivisionI, Level 3: FakeCoin (900pt)
Submission rate  23% (25/107)
Success rate  52% (13/25)
Avg. Score  515pt
Best Score  SnapDragon, 679.06pt
Given that one coin out of twelve is known to be a fake, how do you figure out from
a series of balance weighings which one is the fake, and whether it is heavier,
lighter, etc.? dmwright came up with a rather elegant solution to this problem.
He basically used two status flags for each coin to indicate whether or not that coin
could be (a)"fake and heavier" or "not fake and heavier" and (b)"fake and lighter" or
"not fake and lighter". All status flags for all 12 coins were initialized as being both
fake and heavier and fake and lighter. Each of the balance readings were parsed, and the
following steps were taken for the coins in each equation:
If a coin appears on either side of an "=" sign, then it must be real (since there can only be one fake coin) so set the flags for this coin to be "not fake and heavier" and "not fake and lighter".
If a coin appears to the left of a "<" sign or to the right of a ">" sign then there is no way that it can be fake and heavier, so set the "not fake and heavier" flag for this coin.
If a coin appears to the right of a "<" sign or to the left of a ">" sign then there is no way that it can be fake and lighter, so set the "not fake and lighter" flag for this coin.
If a coin does NOT appear to the left or right of any given "<" or ">" sign then it can not be a fake, once again for the reason that there can be only one fake coin. Set the flags for this coin to be "not fake and heavier" and "not fake and lighter".
Once these steps are completed for each of the balance equations, enough information
exists to solve the problem. Count the number of fake coins by checking to see if either
the "fake and heavier" or "fake and lighter" flags are set for each of the coins. If the
number of fake coins is zero, then this is obviously a contradiction of the problem statement.
Output "CONTRADICTION". Otherwise, output one of the following for each coin, depending on the
status of its flags and the total number of fakes counted:
If both flags for the coin are set to "not fake and heavier" and "not fake and lighter" then this coin is obviously not a fake, so output 'R'.
Otherwise, one of the flags indicates a fake; if there is more than one fake counted (out of 12), then you have not been given enough equations to determine which coin is the fake, so output 'U' for this coin.
If only one fake was counted and the "fake and heavier" flag is set, output 'H'.
If only one fake was counted and the "fake and lighter" flag is set, output 'L'.
If only one fake was counted and both the "fake and heavier" and "fake and lighter" flags are set, you are sure the coin is a fake, but have not been given enough equations to determine whether or not it is heavier or lighter, so output 'F'.
By
Penwiper
TopCoder Member