Round 4 Saturday, April 28, 2007 Match summaryOne hundred and fortyeight of the top algorithm coders gathered in a rumble for one of 48 spots in the 2007 TCO finals. As expected, the competition was vicious, denying three of the top 10 rated coders a place in the finals.Over recent years, it has often been the case that a single problem was enough to advance through the later online rounds of a TopCoder tournament. This was not the case this time around  16 contestants solved all three problems and plenty of coders found themselves below the cutoff line with two problems solved. liympanda recovered from his recent rating decline in the best possible way, winning the match with the fastest hard despite resubmitting the easy. The main subject of postmatch chat, however, was underdog nemesis_nitt, who now boasts a new yellow color thanks to his performance in this tournament, including his secondplace finish in this match. Close behind them were usual suspects SnapDragon and tomek. The ProblemsPolishNotationUsed as: Division One  Level One: It didn't take long for most coders to warm up their dynamic programming circuits, as evidenced by the high success rate on this problem. The rules in the problem statement describing a valid expression in prefix notation form the backbone of the DP solution:
SortingInIterations Used as: Division One  Level Two: With constraints as high as 400000 on all parameters, quadratic solutions were bound to time out, for example on the decreasingsubsequence case, which can easily be generated with a0=399999, X=1, Y=399999, M=400000 and n=400000. Suppose the distinct numbers appearing in the sequence are sorted and labeled x_{1}, x_{2}, x_{3} etc. so that x_{1} < x_{2} < x_{3} ... and so on. Here is another way to rephrase the process in the problem:
This is because each distinct value is considered at most twice – once in step 2 and possibly again in step 1 (if not all occurrences were removed in step 2 and a new iteration was started). If we handle multiple elements in step 2, we will go back to step 1 fewer times. The final trick is the If x_{2} appears after condition in step 2. To evaluate the condition, we need to keep track of where numbers are on the blackboard and be able to update this information efficiently. Various structures were used by contestants, for example mapping numbers to lists containing indices where they appear (and keeping these sorted), or having a big sorted list of (number, position) pairs. All of these suffice as long as they guarantee that the amortized operation complexity doesn't become linear on degenerate cases. As described by Ying in this forum post, this operation can even be done in amortized constant time, for a total time running time of O(n+M). FourSubstrings Used as: Division One  Level Three: The problem begged for a dynamic programming solution, but it wasn't necessarily obvious what the solution was. Suppose we scan the text from left to right and, at each character, we contemplate placing substrings there (if any of them match the text). In order to be able to calculate how many of the newly covered letters have already been covered by words placed recently (and shouldn't be counted again), we also need to keep track of how many letters starting from the current character have already been covered. Additionally, we need to know which of the four substrings we've already placed – a 4bit bitmask will do. The state space in our DP solution will thus consist of (index, covered, mask) triplets, indicating that we're currently at character index, that the next covered letters have already been covered by previously placed substrings and should not be counted towards the score again, and that strings still to be found in the text are represented by mask. A sample state using the example in the problem statement is (1, 3, 0001), meaning that we're at character 1, have just placed the substring "our" (last bit in bitmask is set), and since we only just did it, the next 3 letters are already covered: Since we have to calculate two different values (the least and most covered characters), we calculate two DP functions in parallel (say, mini and maxi). Sample code for the calculation function (without the base cases): mini[index][covered][mask] = mini[index+1][max(0, covered1)][mask]; maxi[index][covered][mask] = maxi[index+1][max(0, covered1)][mask]; for ( int i=0; i<4; ++i ) { if ( (mask&(1<<i)) != 0  !starts[index][i] ) continue; int nextc = max( covered, len[i] ); int nextm = mask  (1<<i); calc( index, nextc, nextm ); mini[index][covered][mask] = min( mini[index][covered][mask], mini[index][nextc][nextm] + max(0, len[i]covered) ); maxi[index][covered][mask] = max( maxi[index][covered][mask], maxi[index][nextc][nextm] + max(0, len[i]covered) ); } 
