Monday, February 12, 2007

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.

Thursday, February 01, 2007

Parzania : A distorted reflection of Gujarat Riots

So I am back to the blogs after a long break. Life is going on as routine and events happening not worth mentioning. But something happened that forced me to write today, something that evoked memories of gujarat riots. Yes, I am referring to movie "Parzania".

Last sunday evening me and pranjal went to see a movie at PVR Saket. Though the movie has been praised by critics, I did not like it much. It seems to be a fashion to make movies on "sensitive" issues and show that you ( producer / director and the whole league ) are "concerned" about those who suffered those horrific series of events.

The thing I did not like most about the movie is that they depicted the police force as an evil spectator and accomplice. I am not saying that police was acting like an angel during the events and may be some incidents might have happened which caused the notoriety the police has gained. Bollywood keeps on depicting our police force as a demon and then we all yell that police does not perform its duties very well. If someone who has done good deeds is always been criticized for his/her wrongdoing, will there be any motivation to keep on doing good? Isn't it the case that lack of appreciation cultivates a tendency not to take pain in doing something right ( because no body would care/mention/appreciate )?

I had been there in gujarat. I am born and brought up in gujarat itself. And I must say that the biggest villain was media. Stating baseless rumors as facts, presenting events in a sensitized form, showing provoking clips/statements this is all media has done. Should not they act responsibly? But who is to blame, after all, we like things presented in this manner. We always try to hide our irresponsible behavior by criticizing someone.

So called "Top class" reporter barkha dutt was standing on a lonely highway and screaming there is no security force there? What should I say about that asinine woman? Gujarat has thousands of kilometers of highway, what did she want? A policeman at every 50 meter on the highway and leave the burning cities unattended?

Army batallions were air lifted from Jodhpur to get them as fast to gujarat as possible. Those army men did not took a rest. But did we appreciate? My friends were stuck in vidyanagar because of curfew. No mess, no shops and no food. It was the police who came to the rescue, searching for such caged souls and escorting them to Anand railway station. They did not ask whether the students that they are helping is hindu or muslim, the just performed their duties. Alas! it all goes unnoticed. When the mob came to our place and burned shops at the ground floor, police did came. What do you think a group of four people, three carrying a lathi each and one carrying a vintage pistol could have done against a mob of 3000 people? I have seen police officers begging the mob to keep cool. And the way they depict in the movie is that police watched the entire scene taking satanic pleasure in whatever was happening.

Is it police' fault that we do not have enough policemen? Is it police' fault that it is not well equipped and poorly paid? At the time of riots, they were staying in tents in a sensitive areas so that people could feel safe, but no body cared asking them even for a glass of drinking water.

Well, may be I had a lot to write but my anger towards the movie was subdued because of the delay in this writing. And even from a movie point of view, having english as a language while you are filming on a lower class background???

Besides, I still don't understand what was the point of making this movie after years of those horrific past. Did they want to revive the wounds of victims? It is such kind of distorted and exaggerated representation which had damaged gujarat's reputation irrevocably. Gujarat was pushed to a sixth place in industrial investment, because they say gujarat is an "unsafe" place.

For me, gujarat is much much safer than any other place in india where girls can stroll at almost midnight without worries. May the peace prevail!!!