Tuesday, November 18, 2008

Everyone Is Doing It!

So I figured why not make a blog to pontificate upon the various things that interest me, so here goes.

I have been doing a lot of competitive programming practice lately (getting ready for ACM world finals) and I have noticed one of the biggest differences between individual and team contests. Obviously keyboard time is a big difference, but an offshoot from that I didn't recognize until later was using the computer to solve the problems algorithmically not just for writing code.

For example the last problem I worked on (over at stack overflow) was much easier to solve once I quickly coded up a brute force solver. The brute force solution took just a few minutes to write, and it gave me the insight that eventually allowed me to solve the problem.

The number one ranked TopCoder is Petr. He posts videos of his monitor as he competes in TopCoder SRMs. Quite frequently he writes a brute force solver to the problem and tests his own solution against it. An especially awesome case of this was when he used the brute force solver to find a test case that his code failed on and saved that test case for someone elses code in the challenge phase.

Another example of this was during ACM practice. We had solved all but two problems and were having a hard time coming up with anything on the last two. We wrote a brute force solver for one (the game of nim but with the winning player on end states reversed) and were quickly able to deduce the answer.

Writing a brute force solver only works in some cases. There have been times when it gives me no insight, but in general when you are stuck on a problem where a brute force solver is just a few minutes to code it is probably worth it.