## 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;}