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