Monday, May 10, 2010

Google code jam qualification rounds.

I've participated in google code jam since the 2008 version. Considering how the 2009 one went and seeing the problems in 2010's qualification round, I can predict with 95% confidence that in the 2012 google code jam:
- There will be 5 advancers to on site finals.
- The world champion will win 100 dollars.
- Rounds will last for four hours.
- Problems will be 350% more about implementation than they are now.
- Problems will be 10% as interesting as they are now.
- Filtering scoreboard by country will still be impossible.


Anyway, the positive thing about this round was that I finally learned my lesson. Nope, python is not the answer when there are bignum problems. Just because the contest organizer's don't feel like you should use C++ to solve a problem does not mean you shouldn't. In fact, after some time in chat I finally saw the light. GMP !.

Instead of spending 30 minutes of the following GCJ rounds trying to remember how to use python's bizare standard i/o (which for some reason is not as simple as cin >> n or n = sys.stdin.readInt()) (I am guessing all GCJ rounds from now on will use bignums). I can just use the GMP library. Because:

- It is free software!.
- It works.
- The c++ binding makes clever use of operator overloading - It is easier to use than Java's bignums...

Anyway, so here is what I learned.

Installing GMP
In ubuntu: sudo apt-get install libgmp3-dev libgmpxx4ldbl

Using GMP in your code jam c++ template

Well, it is easy, after #include "gmpxx.h" , simply use the mpz_class just as you would use a number type... Do not forget to change your compile command to link to this new library (I added -lgmpxx -lgmp to my g++ command inside the script that runs gcj code).

After installing and preparing GMP I gave it a try and coded problem B in c++ using GMP, it was very easy. Granted, I am no fan of large non-sense names as mpz_class so I used a typedef to call it big.

What follows is the elegant resulting c++ code I have fallen in love with:

#include <iostream>
#include "gmpxx.h"
typedef mpz_class big;

using namespace std;

//=========================================================
// program:
//
int N;
big t[1000];

big gcd(big A , big B) {
while (B != 0) {
big C = B;
B = A%B;
A = C;
}
return A;
}

big solve() {
big T = t[0] - t[1];
for (int i=0; i<N; i++) {
for (int j=i+1; j<N; j++) {
T = gcd(T, t[i] - t[j] );
}
}
T = abs(T);
return (T - t[0] % T) % T;
}


inline void init(){}
//=========================================================
// I/O:
//
int main()
{
init();
int C; cin>>C;
for (int i=1;i<=C;i++)
{
cerr<<"["<<i<<" / "<<C<<"]"<<endl;
cin >> N;
for (int j=0; j<N; j++){
cin >> t[j];
}
cout<<"Case #"<<i<<": " << solve() << endl;
}
return 0;
}