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)