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