Google Code Jam 2010 - Qualification round

Qualification round of Google Code Jam is over, I have managed to get only 53 points of 99 possible. Not a very good start, but nevertheless I proceeded to Round 1. Here is some of my code, that I solved the problems with.

Snapper Chain

It was the easiest problem to solve. (Problem Text) The key to the solution is that the chain shows number of snaps in binary (actually last n bits of it), and light is on when all snappers are in ON state (= the last n bits are all equal to 1).

#include <iostream>
#include <math.h>

using namespace std;

int main(){
  unsigned int t, n, k;
  cin >> t;
  for (unsigned int i=1; i<=t; i++){
    cin >> n >> k;
    unsigned int d = (1U << n ) - 1;

    cout << "Case #" << i << ": " <<
          (  (k & d) == d ? "ON" : "OFF" ) << endl;
  }
}

Provided code was successful with large input too.

Fair Warning

This one was a little bit harder. (Problem Text) The key is that the difference is time between any 2 events stays the same, no matter how big/small number of starboseconds we add to all of them. So we need a greatest common divisor of the differences.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef unsigned int uint;

uint gcd( uint a, uint b ){
  if ( b == 0 ) return a;
  return gcd( b, a % b );
}

uint op_minus( uint a, uint b){
  return a > b ? a - b : b - a;
}

int main(){
  uint c, n, tmp;
  cin >> c;
  for (uint i=1; i<=c; i++){
    cin >> n;
    vector<uint> t;
    for (uint j=0; j<n; j++){
      cin >> tmp;
      t.push_back( tmp );
    }
    //after first transformation t[i] will have the difference 
    //between former t[i] and t[i+1]. 
    //The last member t[n-1] remains - it will be needed at the end 
    //to find the required amount of seconds to add 
    transform( t.begin(), t.end()-1, t.begin()+1, t.begin(), op_minus );
    //after second transformation t[i] will have the gcd of t[i-1] and t[i]
    //I use the following feature of gcd: gcd(a,b,c) == gcd(gcd(a,b), c)
    //every time we are at t[i] there is alreaady a gcd(t[i-2], t[i-1]) in t[i-1]
    transform( t.begin(), t.end()-2, t.begin()+1, t.begin()+1, gcd );
    
    uint remainder =  t.back() % *(t.end()-2);
    cout << "Case #" << i << ": " <<
            (remainder > 0 ?  *(t.end()-2) - remainder : 0 )<< endl;
  }
}

This code does not solve the large input as there are integers up to 10⁵⁰, and we need to use a bigint class, which I didn't find/write myself.

Theme Park

This is the hardest one to solve, because small input can be solved with straight approach, but the large one needs some different. And I couldn't figure it out. (Problem Text) The code that solves the small input is pretty straightforward. We take the group at the beginning of the queue as soon as it can fit in roller coaster. And don't forget that 1 and the same group cannot be taken twice in 1 run (that may happen if number of seats in roller coaster is more than all the number of people in queue)

#include <iostream>
#include <vector>

using namespace std;

typedef unsigned int uint;

int main(){
  uint t, r, k, n, tmp, sum, total;
  cin >> t;
  for (uint i=1; i<=t; i++){
    cin >> r >> k >> n;
    vector<uint> g;
    total = 0;
    for (uint j=0; j<n; j++){
      cin >> tmp;
      g.push_back( tmp );
    }
    uint a=0;
    for (uint j=0; j<r; j++){
      uint sum = 0;
      for (uint b=0;  b<n && sum + g[a] <= k; a=(a+1)%n, b++ ){
        sum += g[a];
      }
      //cout << "sum: " << sum << " ";
      total += sum;
    }
    cout << "Case #" << i << ": " << total << endl;
  }
}

Pity, the same approach is too slow for large input.

The "official" solutions can be found here.