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...