Walk the tree

In the second round of Google India Code Jam 2005, there were 3 problems to be solved in 1 hour. The first question was easy. The second question was also kind of easy, but I mucked up due to bad handling of corner cases, however I finally managed to get all the 5 examples working. I didn’t have enough time to solve the third problem.

My second solution failed in the system testing. I was kind of irritated about that but was too lazy to find out where it went wrong. One of my colleagues did a post-mortem for me and told me that in one of the loops, I had  i < 10 instead of i <= 10 … Arrrggggh….

Anyway, the third problem was kind of baffling for me: “Given a sequence, figure out the minimum number of moves required to convert it into an arithmetic progression” (this is a simplification of the longer original problem).

I first thought of using differences between consecutive numbers and so on, but quickly realized that wasn’t the solution. Then, I thought this problem must have something to do with dynamic programming or some sort of tree-walking to compute the proper sequences. However, I was too lazy to try it myself and got caught up in work anyway. So, I sent the problem to few of my colleagues and got them to scratch their heads.

When I bumped into Avinash in the evening, I told him about this problem, he immediately said that this has got to do with game theory and all you have to do is tree walking. I didn’t understand his solution at first. So, he said “I’ll write it in Python and send it to you in half an hour”, and he did! Next thing I know, Gopal and Avinash are optimizing it – the time taken came down from 1 min 15 seconds to about 7.8 seconds! Avinash explains it in more detail in his writeup about it. As expected, after seeing his solution, I have that ‘Duh’ kind of feeling…