Monday, July 1, 2002 The Problems
DivisionI  Level 1 BitFlipper
DivisionI  Level 2 GirlFriend
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 nonrecursively 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.
DivisionI  Level 3 DNA Strand
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 (i1) will be 'N' and stay 'N' for the next state and emit the proper nucleotide at state i, or the probability that the state (i1) 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 (i1) will be 'R' and stay 'R' for the next state and emit the proper nucleotide at state i, or the probability that the state (i1) 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[i1]*(1PNR)*NEMIT[i], PR[i1]*PRN*NEMIT[i]) PR[i] = Maximum(PR[i1]*(1PRN)*REMIT[i], PN[i1]*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. 
