Wednesday, July 23, 2008 Match summary
In this match 73 competitors faced a set of trivial Easy, tricky Medium and neutral Hard
(which ended having more correct solutions than Medium) problems.
The ProblemsDNAConstructionUsed as: Division One - Level One:
Since there is no restriction for the sequence of nucleotides that form each DNA chain,
the DNA molecule can be constructed from any set of complementary pairs, and its length
will be equal to the number of complementary pairs used.
To form an AT pair, we need both A and T nucleotides, so
if we have NA A nucleotides and NT T nucleotides, we can form at most
min(NA, NT) AT pairs. Same logic can be applied to CG pairs.
Used as: Division One - Level Two:
The idea of the solution is pretty straightforward: implement the cancellation procedure exactly as described in the statement. Pseudocode follows: for each subsequence of digits of numerator for each subsequence of digits of denominator check whether cancelling these subsequences of digits is valid: the numbers of digits in both subsequences must be equal the digits in both subsequences are the same and appear in the same order the fraction left after cancelling the subsequences is valid: there are didits left in both numerator and denominator both numerator and denominator are positive the fraction left after cancelling is equal to the original fraction if cancelling the subsequences is valid, compare the resulting numerator and the current minimal numerator (initially it is the original numerator) if the resulting numerator is less than the current minimal one, store the notation of the resulting fraction as the return valueSee neal_wu's solution for a sample implementation. However, the problem turned out to be really tricky for most of the competitors. Two most popular mistakes were cancelling same digits in wrong order and not checking whether the resulting fraction is equal to the original fraction. LockedDoors Used as: Division One - Level Three:
The problem can be solved using BFS with states (x-position of the cell, y-position of the cell, bitmask of the keys carried after entering the cell). The only difference from the ordinary BFS is handling the 6-bit keys bitmask:
|
|