Google Code Jam 2011 Qualification Round

This Saturday Google Code Jam 2011 Qualification Round took place. I didn't have much time to spend on the problems, but still have solved a couple and proceeded to Round 1.

The ones that I solved are Magicka and Candy Splitting.

Magicka

First I tried to solve it with some cunning string substitution involving regular expressions. But in the end the simple simulation did the trick. I actually was a little bit disappointed after the official solutions were announced, because I thought that there should be some trick in here.

#!/usr/bin/ruby

lines = ARGF.readlines

t = lines.first.to_i
(1..t).each do |test_id|
  arr = lines[test_id].split " "
  c = arr[0].to_i
  combines = arr[1..c].inject({}){|memo, e| memo[e[0..1]]=e[2]; memo[e[1]+e[0]]=e[2]; memo }
  d = arr[c+1].to_i
  opposed = arr[c+2..c+1+d]
  n = arr[c+2+d].to_i
  elems = arr[c+3+d] #.split("").collect {|i| i.to_sym }

  result = []
  elems.split("").each do |elem|
    result << elem
    if result.length > 1
      last2 = result[-2..-1].join
      if combines.key?(last2)
        result.pop(2)
        result = result << combines[last2]
      end
      opposed.each do |o|
        if result.include?(o[0]) && result.include?(o[1])
          result = []
          break
        end
      end
    end
  end

  puts "Case ##{test_id}: [#{result.join(", ")}]"
end

Candy Splitting

This one was a little bit more tricky and the author's solution is much more simpler and clear than mine. I made it using old school brute force, just like Goro (strength is my strength :) )

#!/usr/bin/ruby

def s( candies, pile1, pile2 )
 #p "c:#{candies}, 1:#{pile1}, 2:#{pile2}"
 if candies.empty?
  if !pile1.empty? && !pile2.empty? && pile1.inject(0){|memo, i| memo ^ i} == pile2.inject(0){|memo, i| memo ^ i}
   return pile1
  else
   return false
  end
 end
 x = candies.shift
 p1 = pile1.clone
 return s( candies, p1 << x, pile2) || s( candies, pile1, pile2 << x)
end

lines = ARGF.readlines

t = lines.first.to_i
(1..t).each do |test_id|
 n_candies = lines[test_id*2-1]
 candies = lines[test_id*2].split(" ").collect{|i| i.to_i }

 r = s( candies.sort.reverse, [], [] )
 r = !r ? "NO" : r.inject(:+)

 puts "Case ##{test_id}: #{r}"
end

Google Code Jam 2010 - Round 1

Sadly I didn't qualify into Round 2. But actually didn't have any chance, because at the time I posted my first solution to the A problem, the top scorers board was already full of 100s (That is maximum one could get for solving all 3 problems.) So as the qualifying round this one had 3 problems: A, B and C, with A being the simplest one and C the hardest one. As I participated in Round 1B, here are the thoughts on problems that I met there.

File Fix-It

(Problem Text)

This one is about creating the tree of folders and counting how many folders you have to create. The solution algorithm is simple.

1. We create a root node.
2. Read the next folder, we must create (with path).
3. Split the path.
4. Add folders one by one to the root node, counting how many of them we had to create.
5. Goto 2

Here is my c++ code.

#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Node{
public:
  string name;
  map<string, Node> children;

  Node(){}
  Node( string n ):name(n){}
};

vector<string> split( const string& s, const string& delimiter ){
  vector<string> result;
  string::size_type from = 0;
  string::size_type to = 0;

  while ( to != string::npos ){
    to = s.find( delimiter, from );
    if ( from < s.size() && from != to ){
      result.push_back( s.substr( from, to - from ) );
    }
    from = to + delimiter.size();
  }
  return result;
}

int add_to_node( Node* current, vector<string>& path ){
  int r = 0;
  for (int i=0; i<path.size(); i++){
    if (current->children.find(path[i]) == current->children.end()){
      r++;
      Node child(path[i]);
      current->children[path[i]] = child;
    }
    current = &( current->children[path[i]] );
  }
  return r;
}

int main(){
  int t;
  cin >> t;
  for (int i=1; i<=t; i++){
    int n, m;
    cin >> n >> m;
    Node root("");
    for (int j=0; j<n; j++){
      string s;
      cin >> s;
      vector<string> path = split( s, "/" );
      //cout << root.children.size();
      add_to_node( &root, path );
    }
    int total = 0;
    for (int j=0; j<m; j++){
      string s;
      cin >> s;
      vector<string> path = split( s, "/" );
      total += add_to_node( &root, path );
    }
    cout << "Case #" << i << ": " << total <<endl;
  }
}

Picking Up Chicks

(Problem Text)

This problem is about finding out how many (slow) chicks prevent one particular (fast) chick to get to the barn in time. (This solution is in ruby). My solution actually is not optimal, but it is still solving the problem.

#!/usr/bin/env ruby

c = ARGF.readline.to_i
(1..c).each do |i|
  n, k, b, t = ARGF.readline.split(" ").collect{|x| x.to_i }
  x = ARGF.readline.split(" ").collect{|y| y.to_i }
  v = ARGF.readline.split(" ").collect{|y| y.to_i }

  times = []
  x.each_index do |j|
    d = b-x[j]
    times << ( d % v[j] == 0 ? d / v[j] : d / v[j] + 1 )
  end

  chicks = 0
  max = 0
  swaps = 0

  times.reverse!
  times.each_index do |ti|
    max = times[ti] > max ? times[ti] : max
    if t >= max
      chicks += 1
    elsif t >= times[ti]
      chicks += 1
      #we need to swap only with those chicks that will arrive later and won't get in time
      swaps += times[0...ti].collect{|one| one > times[ti] && one > t ? one : nil }.compact.count
    end
    break if chicks >= k
  end

  print( "Case #", i,": ", (chicks >= k ? swaps : "IMPOSSIBLE"), "\n" )
end

Your Rank is Pure

(Problem Text)

I ran out of time before I even could understand what this problem was all about. So i cannot tell anything about it. I will try to solve it later though.

I have also checked out the official solutions for the first 2 problems, and they appear to be much cleaner and simpler than mine. My approach is too straightforward. Have to practice more...

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.