
Match Editorial 
SRM 86May 8, 2002
Match summary
Division 1  275  Shade
Everyone pretty much took the same approach to solving this problem:
create a big twodimensional array, fill it in according to the elements
in the coordinates array, and then count all the ones filled in. The
two most common mistakes that I saw were people getting their indices
backwards, and people making the incorrect assumption that x1 < x2 and
y1 < y2.
Division 1  475  Dial
The first step to solving this problem is to parse all of the
relationships between the digits. For each rule, there is a
relationship between two digits that says that the two digits must come,
one after the other. Once you have this figured out you can solve the
problem using recurrence. First, check that the first digit doesn't
have to be after some other digit and that there are no digits which
must be before or after two distinct digits. If those conditions are
not met, return 0, otherwise, try to find valid sequences by recursively
adding one digit at time and keeping track of which digits have been
used. If at any point the last digit in the sequence must come before
another digit, then use that digit next. If there are not restrictions,
then recursively try to add each unused digit to the sequence. See
malpt's solution for an examples of exactly this. The quickest solution
to code was to use the C++ function next_permutation and then just look
at every sequence to check if it was valid. See DjinnKahn's
solution for an examples of this.
Division 1  1000  Battery
Solving this problem required more intuition than knowledge of any
algorithmic technique. With up to 50 candles, it is obviously
impossible to try every combination, or even to try some small subset of
every combination. The key is to note that a candle contributes the
most when it is burning in conjunction with the most candles. So, if we
ignore the restriction about minimum recharge time, then the best way to
burn them is to start them all at once. In order to take the minimum
burn time into account, we take the longest burning candles, and start
them later than the rest, so that we can have some candle burning for
the minimum time. We select the longest burning ones because they have
the lowest contribution to burn time ratios. Thus, the basic algorithm
is to sort the candles by length and select enough of the candles,
starting with the longest, that the minimum will be exceeded. Since we
don't want to exceed the minimum if possible, we will overlap two of
these candles so that the minimum is exactly reached. Then, all of the
other candles are started at the same time as the overlap and burn for
their duration. thekcc's
beat everyone else by implementing this in
fourteen minutes.
By
lbackstrom
TopCoder Member