Google Code Jam 2010 Large DataSets Take Too Long to Submit

Question

I'm participating in the 2010 code jam and I solved two of the problems for the small data sets, but I'm not even close to solving the large data sets in the 8 minute time frame.

I'm wondering if anyone out there has solved the large data set:

1. What hardware were you running on?
2. What language were you running on?
3. What performance tuning techniques did you do on your code to run as fast as possible?

I'm writing the solutions in Ruby, which is not my day to day language, and executing them on my Macbook Pro.

My solutions for problem A and problem C are on github at http://github.com/tjboudreaux/codejam2010.

I'd appreciate any suggestions that you may have.

FWIW, I have alot of experience in C++ from college, my primary language is PHP, and my "sandbox" language is Ruby.

Was I just a bit ambitious by taking a shot at this in Ruby, not knowing where the language struggles for performance, or does anyone see anything that's a redflag as to why I can't complete the large dataset in time to submit.

Answer 1

Usually the small data sets are designed to be solved with simple algorithms but the large data sets require some clever ideas to reduce the amount of time required to calculate. The language shouldn't be a big issue here if you have the right algorithm.