Walk the tree

Posted by Swaroop C H on March 12, 2005 Filed under: design, tech

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...


Avinash says:

We finally solved it without walking the tree using only for loops!

Chinmay says:

actually, this is a game called "Tower Of Hanoi" or something. Emacs even has it as a game.(Type "M-x hanoi"). Perhaps I can figure out how they do it if I see the source code. It's in emacs-lisp, but maybe I could translate it to C. Will post back soon.


There's no comment box, but please do email me or tweet me your thoughts and criticisms, and I will publish the relevant ones here.