Google code jam qualification round

This one had two surprises for me: Usually in the qualification round there are three problems and the score rules are such that you have to pass at least one large input to pass. In this case, the qualification cut-off was 25, yet each of the small inputs was worth 10 points. So I knew I qualified much earlier. The second surprise was that there were a couple of non-trivial problems. They are still 'easy' problems but they may be very tricky to think of the solution.

I actually started the match at the whole beginning. I did have to use around 30 minutes in the middle of solving D-large to go to have dinner. That was only because I didn't plan to take so long. Anyway, I ended up in position 93-th. Which is unimpressive seeing how I could notice some people with a better ranking that clearly started solving the problem set after me...

A and B
I am not going to explain problems A and B because... well, they are mostly implementation. A is interesting in that you really need to think about the implementation before dividing, and is tricky, but B is more straightforward. I am not sure I understand why A large gives less points than B large. I really think that B was the easier of the two.

Still, here are some commented versions of my solutions to A and B:

A:

// They contain the input after reading from I/O
int N;
char bot[100];
int  button[100];

// Returns the needed time for a test case:
int solve() {
    int ox = 1, ot = 0; //The last position and the last time we remember
                        //about the orange bot
    int bx = 1, bt = 0; // Same about the blue bot.
    int t = 0;
    for (int i=0; i<N; i++) {
        if (bot[i] == 'O' ) {
            //Orange
            ot += abs(button[i] - ox)+1; //Time required to move to the button
                                         //and push it.
            ox = button[i];         //update position
            ot = std::max(ot, t+1); //wait to time t before pushing if necessary
                                    //(so that the push is done after
                                    // the previous one)
            t = ot;
        } else {
            //Blue
            bt += abs(button[i] - bx)+1;
            bx = button[i];
            bt = std::max(bt, t+1);
            t = bt;
        }
    }
    return t;
}

B:

// The variables that hold the input after reading the input file...
int C;
char base1[36];
char base2[36];
char result[36];
int D;
char opos1[28];
char opos2[28];
int N;
string spells;

// Uses the variables and returns the contents:
// Another function converts "AA" to [A, A] after this one is called...
string solve() {
    string contents = "";
    char transition[26][26];
    memset(transition, '#', sizeof(transition));
    bool opposed[26][26];
    memset(opposed, 0, sizeof(opposed));
    
    // Load the input into a table of transitions.
    for (int i=0; i<C; i++) {
        int a = base1[i]-'A';
        int b = base2[i]-'A';
        transition[a][b] = transition[b][a] = result[i];
    }
    // And a table of opposed characters
    for (int i=0; i<D; i++) {
        int a = opos1[i]-'A';
        int b = opos2[i]-'A';
        opposed[a][b] = opposed[b][a] = true;
    }
    for(int i = 0; i<spells.size(); i++) {
        // Simulate the addition of each element
        if (contents == "" ) {
            contents += spells[i];
        } else {
            //transition?
            char cur = spells[i];
            int x = cur-'A';
            char ls =  *contents.rbegin();
            char & r = transition[ls-'A'][x];
            if ( r != '#' ) {
                //Yes, transition, do the transformation!
                contents.resize( contents.size()-1);
                contents += r;
            } else {
                //opposed?
                bool op = false;
                for_each(ch, contents) {
                    op |= opposed[*ch-'A'][x];
                }
                if (op) {
                    //Yep, opposed = clear it.
                    contents = "";
                } else {
                    //not opposed just append new element.
                    contents += cur;
                }
            }
        }
    }
    return contents;
}

C (small)
This was funny, I was just about to read C's statement and SkidanovAlexander already got his 100 points. Then I read the statement, and I was surprised, it was actually a interesting problem. (Already? In the qualification round?). Anyway, the first thing I noticed is that adding two binary numbers without carriage is the same as a xor operation. I didn't note this as much as remembering it because it is a common theme in some problems. After that it got harder. Usually these problems are solved using dynamic programming. But since the little kid uses xor instead of +, there was not (I thought) an easy way to represent the current "Difference" which you would have to equal to 0... After a while, I decided that since only 25 points were needed, I may as well solve the easy version of C first and ensure myself the qualification...

The easy version of problem C is simple: The maximum number of candy pieces is 15, which means that you can try all 215 ways to split the candy in two parts, get the xor of each of them and then remember the one that gave Patrick the best outcome.

After that, I decided to take a look to D.

D
Now that was shocking, I thought to myself that they were really set to make the match interesting for those that would find the previous problems easy. This problem at first seemed impossible.

I tried a (wrong) approach. I thought that it was always optimal to pick pairs of elements to shuffle. And wait until they are sorted - To sort pair by pair. So, in fact, if you could find the minimum number of swaps and multiply by 2 that would be the result. This approach turned out to fail the small input. I decided to switch to C-large.

C (large)
Leaving that problem for a while was useful because I was able to see with a fresher head when opening it again:

Actually: We want two partitions of the original candy bag. The xor of the first partition must be equal to the xor of the second partition. We have something like:

Xor of Side A = Xor of Side B

The equal operator (x==y) can be seen as : (x^y)==0 . (Where ^ is the binary xor operation). Try it yourself. xor is 0 whenever both bits are equal.

So we have:

( (Xor of Side A) ^ (Xor of Side B) ) == 0

( (a1 ^ a2 ^ a3 ^ ...) ^ (b1 ^ b2 ^ b3 ^ ...) ) == 0

Now xor is associative and distributive. And the sets {a1,a2,...} {b1,b2,...} are both partitions of the original set (When uniting {a1,a2...} with {b1,b2,...} we get the original set, and they are disjoint). Which leads us to concluding:

C1 ^ C2 ^ C3 ^ ... C4 == 0

Yes, that's right, the xor of all the values in the bag must be 0 and it does not matter which candy goes to the little brother and which to the big brother. I was at first skeptical, then I noticed that in the second example, every partition will yield two equal Patrick values... 3^5 = 6. 5^6=3, 3^6 =5, 3^5^6 = 0. This means that as long as the xor of all the values in the bag is 0, every partition is valid. And if the xor is not 0, no partition is valid.

If the xor is 0, then we can just pick any partition. We want one that gives the big brother the best value, and the subset given to the little brother must be non-empty. There is no need to pick more than one element for the little brother, and it is convenient to keep the element we give to him as small as possible. - Just pick the minimum and give it to him. Give the rest to the big brother and this will maximize his loot.

// Contain the input after read from i/o:
int N;
int C[1000];

// Returns the maximum loot size or -1 if it is impossible
int solve() {
    int x= 0; //xor of all elements
    for (int i=0; i<N; i++) {
        x ^= C[i];
    }
    if ( x == 0) {
        // Every partition is always valid
        // Sum of all minus the smallest value:
        return accumulate(C,C+N,0) - *min_element(C,C+N);
    } else {
        // No partition is valid
        return -1;
    }
}

Funny anecdote: When I coded a solution very much like that code, I could not compile the accumulate. I wasn't sure what was going on, I re-wrote the pronunciation of accumulate a lot of times and I double checked the #includes in my template - <algorithm> was there all right. I ended up giving up and doing the sum manually. Later when my head was colder I noticed that my template c++ file did not #include <numeric>, and numeric and not algorithm is the #include file that has std::accumulate. (Which is not very intuitive, considering that accumulate is purely algorithmic and it works with strings and any class that overloads +, not just numbers).

Back to D
I went to dinner, and when I came back I started trying many different cases. I eventually learned something about the result. that something turned out to be true. I won't explain what because I don't want to spoil the problem for no reason and I right now cannot explain why it worked, so it would be unnecessary as an explanation.

I didn't really like this problem, rewarding not doing a proof is the opposite thing to what you want in a programming contest. At first I thought that maybe I was the only one that didn't bother proving it but after the match it was clear that most people just guessed the solution. Problems should punish those that don't prove stuff before implementing, not the other way around.