For GCJ, you need the right algorithm. In addition, I would say that it is much more important how quickly you can encode a program in a language than quickly, given the limited encoding time.
I used Python for GCJ and had no case when the language speed "failed" to me. We can say that Python is 2 times faster than Ruby (per lang.benchmarks shootout); and when I used Psyco (the JIT compiler module), I get about 5x acceleration - but it's a little beer, choosing a language can only lead to a linear increase in speed. Say 10 times, big cheers.
Problems in the GCJ, on the other hand, are designed to take into account a combinatorial explosion , and large inputs lead to a significant increase in time (or memory). Taking, for example, GCJ 2010-1C, "Creating Chess Boards." Assuming a square board for simplicity, a naive implementation has complexity O (n 4). The quick but complex implementation of the judge was described as O (n 2 log (n 2)). My simpler solution, which, unfortunately, came to me after the end of the round, was O (n 3). The difference between power 3 to power 4 may not seem very significant, but the 512x512 table was processed at a large input, for it 3 algorithms will have to iterate in the value
naive 68,719,476,736 mine 134,217,728 judge 4,718,592
Thus, my implementation at this input will be approximately 30x slower than the judge’s decision, and ~ 500 times faster than the naive code. On my old desktop (1.2 GHz Athlon), my Python code launches a large input just under 4 minutes. I can assume that an optimal solution would have passed in less than 10 seconds, but who cares as long as you fit under 8 minutes?
On the other hand, for the algorithm n ** 4 it will take ~ 500 * 4 min = 33 hours. This is very unacceptable, and an optimizing compiler or processor with an increased clock speed cannot save us from this swamp.
Of course, some optimizations are possible - just adding psyco.full () reduced my time from 5x to 46 seconds. In addition, running the code on my faster laptop (2 GHz dual-core processor) accelerated it up to 3 times. This is “only” 15 times - it doesn’t matter, let’s say that we accelerated it up to 50 times - it’s another 10 times too slow to be able to use the “naive” algorithm at a large input.
So, if you have a bad algorithm, optimizer / compiler / equipment will not help. On the other hand, if you have a better algorithm, you can use the computer 30 times slower than my nine year old PC, and still get results over time with the python / ruby scripting language. Which, by the way, is the main goal of the authors of the GCJ problems - the contestants stand out on the basis of programming skills, and not the compiler / hardware / network connection.