Bitwise fiasco

Yesterday was one of the worst day. It was the day of Bitwise 2007 . I participated in this contest with Pranjal as my team mate. I had really high hopes and a bit of arrogance as I could claim 26th rank in this prestigious contest last time amongst 2700 participating teams. Bitwise 2006 was my first official participation in a programming contest. Having done so well in my debut, I was dreaming to climb further up the ladder with Pranjal ( who secured 8th rank in Bitwise 2006 ) along the side.

The arrogance had fogged the part of the brain which does rational thinking, and I ended up starting my day without any kind of warm up practice for the contest. I had not even revised any relevant material.

Bitwise 2k7 started a little late than the announced time of 1300hrs. And as usual, I thought to attempt the "easier" problems ( 100 points ) first. It was based on graph theory where one was required to find out the vertice(s) having the minimum distance to all other vertices in a given tree. Initially, I started with an O(n^3) implementation and when I found the response of the system to be "Time Limit Exceeded" ( which was kind of obvious with such a naive approach to the problem ), I improved it to O(n^2). Even though, I tried harder I could neither change the complexity nor the response of the system. After 2-3 failed attempts I decided to concentrate on some other problem and come back to this one at a later time.

Problem 4, had two parts, the initial part was to decide whether a certain door k out of n will be open or closed having gone through a certain toggling scheme. It was kind of easy. The next part was a variation of the classical Tower of Hanoi problem. No matter how hard I tried, my algorithm was not matching the given sample input/output. I asked the admins to look at the problem again for any possible mistake in the statement or sample input/output. But this time they were not as quick in response as they were for the last event. After around 10-15 questions fired by different teams, they answered only one. The overall contest also had attained height of mismanagement with problem statements being updated several times after the contest timer was started. Having tried for 2-3 hours on Problem 4, to my utter surprise, I found out that many other teams were cribbing about the correctness of its problem statement. I checked the rankings and was shocked to see that none of the teams ( not even those who were sitting at Top 10 ) could solve that problem. So I gave up on this problem too.

Then, I started yet another problem having to do with dynamic programming, coins and denominations. It was a variation of the classic denomination problem. Not that it was too hard to do it, I was kind of getting low because of failures and hunger. We went out to have a dinner at a small restaurant just opposite to IIT where we discussed yet another problem involving prime number and modular arithmetic. I thought to give it a shot after coming back, but that damn "Time Limit Exceeded" was not getting out of my sight.

Finally, we decided to give up as we were still sitting at zero where other Top 50 teams begged more than 800 points. I had never been so dejected in a long time. I was literally ashamed of myself.

Today morning I read a couple of articles on Modular Arithmetic and
Fermat's little theorem and realized why my implementation was not fast enough to defeat that "Time Limit Exceeded" demon. For Problem 1 ( The one with the vertices ) I learned that the middle vertice(s) of the longest path in the tree always have minimum sum of distance to all other vertices. How to find the longest path in a tree? Well, start from any vertex A and find out the furthest vertex B from it. Now start with B and find out the furthest vertex C from B. Path B to C is the longest path and its middle vertice(s) are the ones that we needed to find out. Running time?? O(n)

The bottom line is that I have got rusty. My programming skills and algorithm designing skills have fallen down. It seems I have not been doing much brain stimulating work for a long time. May be this failure is an indication for me to start honing my skills and in addition to giving exercise to my body I should give enough exercise to my brain as well.