Match Editorials

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 challenge phase was relatively calm, with 12 successfull challenges. Surprisingly, the system test brought down all but 10 submissions on Medium.

neal_wu took home one more match win with 5 successfull challenges, crazyb0y and anastasov.bg rounded out the top three.

The Problems

Value	250
Submission Rate	69 / 71 (97.18%)
Success Rate	65 / 69 (94.20%)
High Score	bbi5291 for 249.17 points (1 mins 38 secs)
Average Score	229.24 (for 65 correct submissions)

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.

Finally, to find the maximal number of complementary pairs in a set of nucleotides (and the maximal length of a DNA molecule which can be constructed using it), we need to count the numbers of nucleotides of each type in the input set, and return min(NA, NT) + min(NC, NG).

Value	500
Submission Rate	45 / 71 (63.38%)
Success Rate	10 / 45 (22.22%)
High Score	neal_wu for 404.83 points (14 mins 30 secs)
Average Score	297.17 (for 10 correct submissions)

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 value

Value	1000
Submission Rate	21 / 71 (29.58%)
Success Rate	16 / 21 (76.19%)
High Score	bbi5291 for 872.43 points (11 mins 12 secs)
Average Score	681.59 (for 16 correct submissions)

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:

• at the start keys bitmask is 000000 (no keys picked up)
• if the cell which is to be entered is a key, the corresponding bit of the keys bitmask must be set to 1
• if the cell which is to be entered is a door, it can be entered only if the corresponding bit of the keys bitmask is set to 1