Qualification Round 3 Tuesday, April 3, 2007 Match summaryA total of 831 coders waited until the third and final qualification round for the 2007 TopCoder Open. Of these, only 488 scored greater than zero points, so all of those will advance to the next round. Several coders solved all 3 problems, with TopCoder member icanadi finishing on top thanks to two successful challenges. Coders sean_henderson and fpmc were close behind, and liux0229, cz.vx.bc and ltdtl also finished with impressive scores.The ProblemsPacketRepackUsed as: Division One  Level One: This problem may have taken some time to read and understand, but implementing the solution turned out to be quite simple. All this problem asks is for you to move some bits around, which is something that any programmer should be comfortable with. Many coders chose to proceed directly as the problem statement described. First, they contatenated the input words into a string of 0's and 1's. Then, they extracted each of the fields. Next, they reversed their order and put them back into a long string (remembering to include the leading zeros). Finally, they broke this string into words. This solution certainly works, but it is more complex and time consuming to code than necessary. A simpler approach is to consider each bit of the input, and copy it to the correct location in the output. Mootz used this approach: int[] res = new int[input.length]; for (int f=num_fields; f>0; ) { for (int b=field_size; b>0; ) { int ip = f*field_size + b; int op = (num_fields1f)*field_size + b; int bit = (input[ip / ws] >> (ip%ws)) & 1; res[op / ws] ^= bit << (op%ws); } } return res;In this code, "ip" is the position of the current bit in the input, "op" is the corresponding position of this bit in the output, and "bit" is the value of the bit. MemorizingPi Used as: Division One  Level Two: This problem consisted of three parts: evaluating the complexity of a group of 3 or 4 digits, finding the optimal segmentation, and formatting the output. The first part is a simple task of just implementing the rules in the problem statement, altough there are 7 rules, so speed and confidence were a bit of a help here. Finding the optimal segmentation is most easily done with dynamic programming. Starting at 3, find the optimal segmentation and complexity for the last N characters of the input. The solution for N is either the next group of 3 digits (followed by the solution for N3) or the next group of 4 digits (followed by the solution for N4). There are a few special cases that you must handle correctly to get started. N=3 and N=4 are the base cases. N=5 is undefined, because there is no way to segment a string of 5 digits into groups of 3 or 4. For N=6, N=8, and N=9 the string can only be broken up in one way. BalancingGame Used as: Division One  Level Three: This is a simple game theory problem. Note that with only 20 objects, there are only s^{2} possible board configurations. With the use of dynamic programming or memoization, you only need to analyze each configuration once. Define each configuration as "winning" or "losing" if the next player to move can force a win, or if he will lose regardless of what move he makes next. First, compute the magnitude of the torque as described in the problem statement. If the board does not balance, then the previous player must have caused the board to fall, and this is therefore a "winning" position for the next player. If the board does balance, then you consider all possible moves the current player could make. If all possible moves leave the board in a winning position, then this is a losing position for the current player. However, if one or more moves leaves the board in a losing position, then this is a winning position for the current player. One tricky rule is that if all objects are removed from the board, then the first player loses. This means that the final position is "winning" if there are initially an odd number of objects, and "losing" otherwise. 
