Google Code Jam 2010 Qualification Round

The Google Code Jam Qualification Round took place over the last weekend. This is the third time they have organized
this contest themselves – earlier iterations were hosted by TopCoder. This is my fourth GCJ, including my first one in 2006
that was hosted by TopCoder where I did not even get past the qual round. In the past two years I got eliminated in Round-2.
It is very likely that the same thing will happen again this year.

I could not wake up early enough to start at the beginning of the round, and was mostly away from the computer
most of the day. But this was a 24 hours round, and the problems were quite easy, so I managed to solve all
three in the end.

There is an official contest analysis already posted. I am posting my own
analysis here to explain my own train of thought and to basically act as sort of post-contest
review to organize my ideas.

The first problem asked for figuring out whether the lightbulb at the end of a series of ‘snappers’
would be on after K slaps.

Initially all Snappers are off, so we can see them as a list of 0′s:
[0,0,0,0,...,0,0]

At the first snap, only the leftmost one is turned on (all other have no power).
[0,0,0,0,...,0,1]

At the next snap, the second one is turned on while the first one is turned off.
[0,0,0,0,...,1,0]

At the third snap, the first one is again turned on, all other remain as they were.
[0,0,0,0,...,1,1]

We can see that for the n-th snap, the list looks exactly like the binary representation of n.

0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111

Ok, so we got a potential solution. We need to prove it before we can really be sure.

We can see that the binary representation is valid for 0 claps.

Say we have n snaps, and the binary representation is valid for that. Now to convert the list for n
to that for n+1 claps, we have to flip every snapper that has power. We start at the leftmost bit and flip it,
because it always has power. If the left most bit was a zero we stop there. If the left left most bit was a 1
(before flipping), we also flip the next bit – because it had power. We repeat this for every bit until we have
flipped a bit that was originally a 0.

Notice that this is exactly the same process that is used for binary addition by one:

1110100011111
+           1
--------------
1110100100000

Thus if for any n the binary representation gives us the state of the snappers, the binary representation of
n+1 will give us the state of the snappers after n+1 snaps. Since 0 gives a valid binary state representation, so will
1, and thus also 2,which also makes it valid for 3 and so on.

So the binary representation of K gives us the the state of the snappers after K snaps. To see if the bulb has power
after K snaps, we just need to check whether the lower N bits of K are all set (i.e. all N snappers are on).

You can do this any way you want. During the contest, what I did was to simply count the on bits in K%(2^).
For the bulb to be on all N bits must be set.

Another way is to add 1 to K and then check if K%(2^N) is 0. This works because, if all the lower N
bits of K are 1, adding 1 to it will make them all 0′s.

My contest code was in Basic for the small (meant to run in Spaghetti – my own interpreter) and Python for the large.
But I’m posting code in JavaScript(Rhino) which I wrote after the contest here.

#! /usr/bin/rhino

// import some useful Java packages
importPackage(java.io);
importPackage(java.lang);

// Use Java's Reader classes and System.in for input
var reader=BufferedReader(InputStreamReader(System['in']));

// T=number of cases
var T=parseInt(reader.readLine());

for (cas=1;cas<=T;cas++){
    //Each case consists of 2 integers: N and K
    var data=reader.readLine().split("\\s+");
    var N=parseInt(data[0]), K=parseInt(data[1]);

    // (K+1)%(1< k%(1< all ones => all on snappers
    if ((K+1)&(1<<N))
        print("Case #"+cas+": OFF");
    else
        print("Case #"+cas+": ON");
}

(More to come shortly)

Advertisement