codejam 2010, round 1

I end up participating all 3 subrounds, and the reason is simple, I didn't qualify the first two subrounds.

round 1A is the perfect time, 6pm PST. I gave up problem A because it is too long, although it turns out anyone solve A in one hour gets to top 1000. problem B is a DP for sure, but for some reason I just can't figure out how insertion works. problem C I had every piece correct, even sensed fibonacci numbers. However my submission for small problem is incorrect, while after the match the same code was determined to be correct!

round 1B is another disaster. Solved only problem A, which is far from enough. problem B is not difficult but I am confused on the way swap is done. Failing problem B and looking at problem C. It is even more interesting. I solved small input but forgot to mod 100003, and made 4 failed attempts! God. After the match the moment I looked at one of the top scorer's solution, I figured out the DP recurrence immediately. As later practice attempts show, getting problem C is still tricky because integer overflow issue. Moreover I forgot to remember previous computation to make it a DP.

round 1C, finally I solved problem A and B. This time my analysis made hits and went as far as to make two correct submissions. problem C is still hard for me, I have solved rectangle version but just didn't recognize the same idea for squares. Also the way remove cells is handled is a bit hard to figure out and I basically gave up after 15min, with about 1hour left. It was 3:30am and I have been working on those codejam problems for two days. Having observed I was ranked around 500, I thought I am safe to advance, so went to sleep.

In a way, google codejam is a very nice programming event. The problem sets and testcases are clever and exhaustive. You also get a chance to read top coders's code for free. The analysis is not easy but you will certainly appreciate it once you figure out what is going on. The difference between programming competition and algorithm textbook is that you have to be able to analyze the problem and realize the constraints. Also, you have to be able to code a DP solution.