Match summary

A 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 Problems

PacketRepack

Used as: Division One - Level One:

Value 300

Submission Rate 532 / 783 (67.94%)

Success Rate 470 / 532 (88.35%)

High Score m00tz for 288.85 points (5 mins 37 secs)

Average Score 171.27 (for 470 correct submissions)

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_fields-1-f)*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:

Value 500

Submission Rate 134 / 783 (17.11%)

Success Rate 60 / 134 (44.78%)

High Score NauCoder for 353.11 points (20 mins 10 secs)

Average Score 262.09 (for 60 correct submissions)

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 N-3) or the next group of 4 digits (followed by the solution for N-4).

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:

Value 1000

Submission Rate 36 / 783 (4.60%)

Success Rate 14 / 36 (38.89%)

High Score cz.vx.bc for 817.66 points (14 mins 5 secs)

Average Score 606.41 (for 14 correct submissions)

This is a simple game theory problem. Note that with only 20 objects, there are only s² 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.

By legakis
TopCoder Member