Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?

The Problems

Division-I - Level 1 BitFlipper 
The goal of this problem was to find out the minimum number of "bit flips" necessary to take an arbitrary binary number and convert it to all zeros, given that only a contiguous range of numbers could be flipped. By finding the minimum and maximum occurrences of the '1' bit in the string, and flipping all bits between (and including) these minimum and maximum values it is possible to keep iterating until no more 1's are left. By counting the number of flips made, you have the answer. SnapDragon had a very understandable, concise solution for this one.

Division-I - Level 2 GirlFriend 
This problem was a nice creative example of how TopCoder members can optimize their social lives. A girlfriend that wants to talk on the phone every night from 6 to 8 pm is happy (tolerance increases) every night that she does talk on the phone and is unhappy every night that her boyfriend shuns her (tolerance decreases). So long as her tolerance of the boyfriend remains above some minimum level, she will remain with the boyfriend.

Given that there can be no more than 20 nights in which TopCoder will be scheduled, there are at most 2^20 or about one million possibilities of significant decisions that the boyfriend can make as to whether or not he competes in TopCoder or talks to his girlfriend. The only situations in which he is forced to decide between the two, are when TopCoder starts at 6 pm or 7 pm. If it starts at 8 pm or 9 pm he can do both, and if it isn't scheduled for that particular day he can of course talk to his girlfriend. The catch when evaluating each sequence of possibilities is to remember to take into account the "quadratic effect" of talking (or not talking) to his girlfriend for consecutive days.

All of the compete / don't compete decision possibilities can be evaluated recursively. A good example of this can be found in radeye's and SnapDragon's solutions. Alternatively, the problem could be solved non-recursively using bitmasks. Both Yarin and dmwright elected to do it this way. John Dethridge was even able to solve the problem using dynamic programming, although it is not as easy to comprehend as the brute force solutions, and may not be significantly faster for many of the examples and system test cases.

Division-I - Level 3 DNA Strand 
This problem required some careful reading (and re-reading for myself and probably others unfamiliar with genetics) in order to figure out exactly what was going on. Given a DNA strand that has up to 25 consecutive regions, that can either be normal ('N') or special "CpG Island" regions ('R'), the task is to find the most likely sequence of N and R. The inputs to the problem, include a list of probabilities that a normal region will emit a particular nucleotide (one of adenine ('A'), guanine ('G'), thymine ('T'), or cytosine ('C')), a list of probabilities that an island region will emit a particular nucleotide, the probability that the sequence will switch from a normal region to an island region at any given point, the probability that the sequence will switch from an island region to a normal one at any given point, and the actual nucleotide sequence being investigated.

The first element of the sequence is known to be a normal region. This means that there can be at most 2^24 or roughly 16.8 million possible sequences of N and R. Only the most likely sequence of N and R is required however, and since the probability of each state in the sequence can be expressed as a function of the previous state, it is possible to use dynamic programming to solve this problem very quickly.

The ith state of the DNA sequence is either 'N' or 'R'. The probability that the ith state will be 'N' is either the probability that the state (i-1) will be 'N' and stay 'N' for the next state and emit the proper nucleotide at state i, or the probability that the state (i-1) will be 'R' and then become 'N' for the next state and emit the proper nucleotide at state i. Whichever is greater. Likewise, the probability that the ith state will be 'R' is either the probability that the state (i-1) will be 'R' and stay 'R' for the next state and emit the proper nucleotide at state i, or the probability that the state (i-1) will be 'N' and then become 'R' for the next state and emit the proper nucleotide at state i.

The probability that the initial state will be 'N' is 1, and the probability that the initial state will be 'R' is 0. i.e. PN[0]=1, PR[0]=0. If we call PNR the probability of switching from N to R, PRN the probability of switching from R to N, NEMIT[i] the probability of emitting the proper nucleotide in a 'N' region i, and REMIT[i] the probability of emitting the proper nucleotide in an 'R' region i, we get the following general equations for the ith state for i>0:

PN[i] = Maximum(PN[i-1]*(1-PNR)*NEMIT[i], PR[i-1]*PRN*NEMIT[i])

PR[i] = Maximum(PR[i-1]*(1-PRN)*REMIT[i], PN[i-1]*PNR*REMIT[i])

By finding PN and PR for all elements of the sequence, and keeping track of where the changeovers occur (from R to N and N to R) you ultimately figure out which state it is best to end with, and then use your saved changeover results to produce the final output. radeye and ZorbaTHut produced clear, concise examples of how to do this in Java and C++ respectively.