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

Replacing Text In Html (Outside Html Tags)

private const string OUTSIDE_TAG_LOOKAHEAD = "(?![^<]+>)";

public static string HighlightWordsInHtmlText( string htmlText, params string[] words ){
  if (words == null || string.IsNullOrEmpty(htmlText) ) return htmlText;
  Regex regex = new Regex(OUTSIDE_TAG_LOOKAHEAD + "("+ string.Join("|", words) +")", RegexOptions.IgnoreCase);
  return regex.Replace(htmlText, "<span class=\"highlight\">$&</span>" );
}

OUTSIDE_TAG_LOOKAHEAD - uses regular expression magic, that matches text inside tags, but as it is negated, the text matched is really outside of html tags.
$& - refers to the current match. We cannot put here any word as we don't precisely know what of them was found and in what case.
This example matches also tron in strong, if you need an exact match add word boundaries like that:

OUTSIDE_TAG_LOOKAHEAD + "\\b("+ string.Join("|", words) +")\\b"

Try Ruby Online

Interactive ruby console is available at http://tryruby.org/. It is not very convenient to delete wrong entered character there (you should put a cursor on it, not after it, and press backspace), but it works! :)

[Almost] Universal Makefile

#compiler
CC=g++
#compiler options
OPTS=-c -Wall
#source files
SOURCES=$(wildcard *.cc SomePath/*.cc )
#object files
OBJECTS=$(SOURCES:.cc=.o)
#sdl-config or any other library here. 
#``- ensures that the command between them is executed, and the result is put into LIBS
LIBS=`sdl-config --cflags --libs`
#executable filename
EXECUTABLE=Main.run
#Special symbols used:
#$^ - is all the dependencies (in this case =$(OBJECTS) )
#$@ - is the result name (in this case =$(EXECUTABLE) )

all: $(EXECUTABLE)

$(EXECUTABLE): $(OBJECTS)
 $(LINK.o) $^ -o $@ $(LIBS)

clean:
 rm $(EXECUTABLE) $(OBJECTS)

It is hard to say why it works, but it works. "Make" uses hidden rules to compile object files from sources.

See there for more (in Russian): http://abuse.edu.ioffe.ru/cluster/makeman or read the manual :)

Clean Code

The "cleanest" code I have ever seen.

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.

Escaping Curly Bracket in String.Format()

If you need to print a curly bracket in string, when using string format, just put it twice in a row.

string.Format("{{ hello world }}")//{ hello world };
string.Format("{{0}}", 45);//{0}
string.Format("{{{0}}}", 45);//{45}
string.Format("{0:N}", 45);//45.00
string.Format("{{{0:N}}}", 45);//{N}

The last one is not `{45.00}`, because the parser when reading `}}}` first prints the escaped `}`, and only then closes the formatting section. And as `N}` number format does not mean anything to it, it just prints it out.