
Match Editorial 
2003 TopCoder Open
Online Round 4Wednesday, November 5, 2003
Summary
Call it nerves. Call it writers pulling out all the stops.
Call it Round 4 of the TopCoder Open! Faced with an Easy problem
that would have been a Medium on any other night, and a Medium
problem that would have been a Hard on any other night,
50 of TopCoder's top coders managed 37 correct
submissions. That's 37 total. On all three problems combined.
tjq was first on the scoreboard with a quick submission on the Easy.
But by about the 12 minute mark, Easy submissions were rolling in. The coders
quickly turned to the Medium and then...nothing. Silence. Not even any hopeful
compiles. Eventually, many programmers began to abandon the Medium and
turn to the Hard. Finally, 39 minutes into the coding phase, SnapDragon
grabbed the top spot with the first submission on the Medium. Two minutes later
tomek came out of nowhere to steal the lead. tomek had
struggled with the Easy, taking 24 minutes to complete it. But then he
flew through the Medium in an amazing 17 minutes to gain back all the
points he had lost. And so, with 34 minutes of coding still on the clock,
the contest
was decided, as not a single Hard submission would later system tests.
Congratulations to tomek, SnapDragon, and the other 14 advancers!
The Problems
WhichData
Used as: Division One  Level One:
Value

300

Submission Rate

45 / 50 (90.00%)

Success Rate

32 / 45 (71.11%)

High Score

tjq for 282.05 points (7 mins 15 secs)

Average Score

202.98 (for 32 correct submissions)

In this problem, you enumerate all possible nonempty subsets
of the data and calculate the variance of each, keeping the subset
whose variance is closest to the target.
There are two easy approaches to generating the subsets: bit masks and
recursion. To iterate through the subsets using bit masks, you count from 1 to
2^N1, where N is the number of elements in the data.
Then you treat each index as an Nbit number. If the
ith bit of this number is 1, then element i of the data
is in the subset. If the ith bit is 0, then element i
is not in the subset. Usually in these kinds of loops, you count from
0 to 2^N1, but this time you start at 1 to avoid the
empty set.
To enumerate subsets using recursion, you consider the elements one at a
time, trying all the subsets with that element and then trying
all the subsets without that element, as shown in the following pseudocode:
enumerateSubsets(i, currentSet)
if i == N then return
otherwise,
process variance of currentSet + element i
enumerateSubsets(i+1, currentSet + element i)
enumerateSubsets(i+1, currentSet)
Most coders went for the bitmask solution, but the recursive algorithm had
one compelling advantage for this problem. Assuming you sort the sample
data first, then it is trivial to make the recursive solution generate
the subsets in lexicographic order. In fact, the pseudocode above does exactly
that! With the bitmask version, checking lexicographic order to break
ties is somewhat tricky.
The main remaining issue is precision. If you had a prewritten Fraction
class, this would have been a good time to bring it out. Otherwise,
you probably used doubles. When comparing two doubles, you had to treat
them as equal if the difference between them was less than 10^9. And
if they were equal, then the tiebreaker rules involving lexicographic order
apply.
There was a minor but useful trick that could be used to avoid recomputing
the variance of each subset from scratch.
The formula for the variance was given as
mean = ( s(0) + s(1) + s(2) + ... + s(n1) )/n
varsum = (means(0))^2 + (means(1))^2 + ... + (means(n1))^2
variance = varsum/n
At first glance, it looks like you can't compute varsum until you know the
mean, and you can't compute the mean until you know the size of the
subset. But note that
varsum = (means(0))^2 + (means(1))^2 + ... + (means(n1))^2
= n*mean^2  2*mean*sum + sumOfSquares
where
sum = s(0) + s(1) + ... + s(n1)
sumsOfSquares = s(0)^2 + s(1)^2 + ... + s(n1)^2
Therefore,
varsum = n*mean^2  2*mean*sum + sumOfSquares
= n*(sum/n)^2  2*(sum/n)*sum + sumOfSquares
= sum^2/n  2*sum^2/n + sumOfSquares
= sumOfSquares  sum^2/n
and
variance = varsum/n
= sumOfSquares/n  sum^2/n^2
Therefore, to calculate the variance, you only need to keep track of
the sum of the elements, the sum of the squares of the elements, and
the number of elements. This fact is particularly handy in the recursive
formulation, where you use the partial sums to calculate the variance
of one sample and then pass the partial sums on to the recursive calls,
instead of recalculating the variance from scratch each time you want
to process a new set.
For an example of the bitmask approach, see the solutions of practically
anybody that passed.
For an example of the recursive approach, see my practice room solution.
Jewelry
Used as: Division One  Level Two:
Value

500

Submission Rate

7 / 50 (14.00%)

Success Rate

5 / 7 (71.43%)

High Score

tomek for 378.97 points (17 mins 15 secs)

Average Score

286.10 (for 5 correct submissions)

At first glance, this problem appears to be a straightforward
variation on the knapsack theme. As lars announced in his
trademark fashion, "It's TRIVIAL!" You would expect a crowd as
wellversed in dynamic programming as this one to breeze through the
problem. Ah, but there was a twist! The treatment of equal elements
gave folks fits.
Without equal elements, the problem could be solved as follows:
sort the elements in increasing order
count = 0
for each i from 1 .. # of elements do
// assume element i is Bob's highest valued item
waysBelow = ways to make sums using elements below i
waysAbove = ways to make sums using elements above i
for each sum s from element i upto max do
count += waysBelow[s  element i] * waysAbove[s]
return count
Given
K elements 1..
K, you can calculate the number of ways to
make various sums of those values using a typical knapsack
algorithm:
initialize array ways[0..Max] to all zeros
ways[0] = 1
for each i from 1 upto K do
for each sum s from max downto element i do
ways[s] += ways[s  element i]
At the end of these loops,
ways[s] contains the number of ways
to choose elements that sum to
s.
Equal elements complicate the picture because we can no longer guarantee
that Bob's elements are all to the left of Frank's elements in the sorted
list. However, the only exceptions occur when Bob and Frank take
elements of equal value. In each such case, we need to consider all the
different ways that Bob and Frank can exchange their equal elements.
Fortunately, the changes to the overall algorithm are relatively minor.
We now need to process the elements group by group instead of element by element,
where each group contains equal elements.
Suppose there are G equal elements in a group. For
each size g between 1 and G, we calculate how many distributions
there are in which Bob gets g items from this group. Then we multiply
by Choose(G,g) to account for the different ways to pick
g elements out of the group. Altogether, the final algorithm looks
like
sort the elements in increasing order
count = 0
for each group of equal elements do
i = first index of group
G = size of group
waysBelow = ways to make sums using elements below i
for each g from 1 to G do
waysAbove = ways to make sums using elements above i+g1
for each sum s from g * element i upto max do
count += Choose(G,g) * waysBelow[s  g * element i] * waysAbove[s]
return count
Clue
Used as: Division One  Level Three:
Value

1000

Submission Rate

6 / 50 (12.00%)

Success Rate

0 / 6 (0.00%)

High Score

n/a

Average Score

No correct submissions

"No correct submissions." That's not something you see
very often in TopCoder, especially in a match involving coders like
SnapDragon, tomek, and snewman. And you wouldn't
have seen it in this match either if folks hadn't spent so much time working
on the previous problem.
There are two basic approaches you can take to this problem. First,
you can try to use logical reasoning and trace through the implications
of each guess. I tried this, but 2 1/2; hours later, I was still
hacking away, with no end in sight. I'm eager to see somebody submit
a complete deductive solution in the practice room!
Or you can try brute force. Check all possible combinations of cards and
rule out any combinations that are inconsistent with one or more of
the guesses. First, you have to convince yourself that this is feasible.
There are at most 6*6*9 = 324 ways to assign the secret cards and
Choose(12,6) = 12!/6!6! = 924 ways to assign the remaining cards.
So there are at most 324 * 924 ~ 300000 ways to deal the
cards. For each deal, you have to check at most 50 guesses for consistency,
so you have to check at most 300000 * 50 = 15 million guesses. This is just
barely possible within the 8 second time limit, but only if you use
a very efficient representation of guesses, such as bitmasks. If you
use something like strings to represent the guesses, you're doomed. However,
you don't really need to check all 6*6*9 ways to assign the secret cards,
because
you can immediately rule out any combination that includes one or more
cards from player 1's hand. That leaves less than 6 million guesses to check,
which is easily possible using bitmasks.
Many other optimizations are conceivable. Of these, the most useful is
to skip any combination of three secret cards in which the three cards
have already been determined to be part of the result as parts of
other combinations. For example, if you already know that the
secret cards could have been S1W2L3 or S3W2L1, then you don't
need to test whether the secret cards could have been S3W2L3 because
those cards will all be in the final result even if that particular
combination is not allowed.
To check that a particular guess is consistent with a deal, you need
to check four things:
 If responder is 0, make sure the two nonguesser players don't have
one of the guessed cards.
 If responder is the player on guesser's right, make sure the player
on guesser's left doesn't have one of the guessed cards.
 If responder is not 0, make sure responder actually has one of
the guessed cards.
 If the response is not "N0", make sure the responder actually
has the card that was shown.
If all of these tests are satisfied, then the guess is consistent with the
deal. All four of these tests are easy to code using bitmasks—see my
solution in the practice room.
By
vorthys
TopCoder Member