Shared publicly  - 
 
As a lark, I did the GCJ qualification round today. I was expecting to toy with it a bit and get bored (or, gulp, smoked), but it turned out to be surprisingly enthralling. I hadn't done much algorithmic programming in several years, and I'd forgotten how much fun it is. Scored 60, which ties me for 505th through 5418th out of ~18400. Not bad at all, if I may congratulate myself. :-)

I had a solution for D (the hard, ray-tracing problem) but ran out of time. (Although the contest was open for 25 hours, I only had about five to put in on it.) To console myself, I note that only 22 contestants solved all four problems in the time that I put in.

I had a little excitement while processing the "big" input for problem C. You only get one shot at the big input, and you have to upload your results within eight minutes. Well, I was working on my old laptop, which was already running dozens of CPU-sucking chromium tabs, and my solution was in Python, which turned out to be borderline in this case. I squeaked it in with mere seconds to spare.

One of the best bits is that once the contest closes, you can look at everyone else's entries. Looking at several winning entries for the ray-tracing problem was very humbling. Although I had the key insight (limiting the search angles using the problem diameter), their representations completely outclassed mine, and led to very brief solutions. (The winner completed all four problems in under two hours, which just astounds me.)

Interestingly, my solutions for problems A and B were quite different than those of the winner, and perhaps "better", depending on how one defines that. Roughly, my solutions were closer to "closed form". For B, he/she actually managed to recognize and implement dynamic programming, which impresses me. But, it also has worse complexity and is arguably harder to understand. The guy is definitely a monster coder, though; I sure wouldn't want to meet him in a dark alley armed only with a compiler...

Anyway, I'm sure I'll be crushed in the next round, but I'm looking forward to it anyway!
1
Gaye Hattem's profile photo
 
Great job Mike! I think these contests are a lot fun. It's always interesting to see the solutions people come up with.
Add a comment...