Okay, the D-Day has arrived. We get ready by 7:00 in the morning. On our way to the canteen, I spotted Prunthaban (and whose name Mahsheed can't pronounce properly even now :D ), and then later Ajay Somani and Nishant Redkar. These people are big time algorithm coders, and are one of the best in India, all of them work for Google and were obviously one of the problemsetters for the contest and the judges.
Had a filling breakfast and then proceeded towards the lab where the contest was supposed to begin. At 8:00 AM, we were let in, and soon the contest began. We started with looking at all the problems. Soon we saw that a lot of teams were solving problem F. So went for it. Meanwhile, Mahsheed and Anil were trying to solve problem C. In some time, was ready with a solution, which involved finding the unit vector from the point to the origin, checking if the unit vector was present in the set, if it was then the point is not visible else, the vector is inserted and the count is incremented. This sadly timed out. Mahsheed then asked me if it was possible to use some kind of sieving. This was a brilliant thought, was so silly not to think of that. This brought down the complexity of the solution to O(N^3). Another O(N^3) solution that I realized while writing the code was to check if the LCM of the points was 1, if it was, then the respective points were visible. Got accepted. Now we were in the top 15.
I then started with G. The brute-force solution is O(N^3). That would probably solve the problem, but after about 4 months of server-time :P . It is easy to see an O(N^2) solution. Find the sum from 1..N for every element in O(N). Then, for each pair of indices, i and j, the sum is Sum[i]^Sum[j]. Anyways, this still timed out. I kept cursing myself how there was an O(N) solution for a similar problem in Hitchiker's Guide to Programming Contests, which I used for preparing the 25-page reference document which we could carry to the lab.
In the meanwhile, Mahsheed suggested we move to problem B, which was also being solved a lot. I frankly hate this problem now. The reason being, we read rules number 2 and 3 in the problem, and frankly the only difficulty in the problem lies in interpreting these 2 rules. Now, I wrote a very diligent (though exponential :P) solution which would easily fit in time, but it gave a wrong answer. After about 30 minutes of racking our brains, we realized that there might be an ambiguity in those rules. We then asked the judges via Mooshak (the contest environment), 'If we choose only 1 copy of p1 to construct s1 and 1 copy of p2 to construct s2, the problem reduces to a very trivial one. Are we interpreting something wrong?'. We received a very cryptic reply 5 minutes later (they were usually replying within a minute or so, and replied to questions asked after ours).. 'You can re-read the problem and ask if you have any doubts'. WTF! This clearly meant 'some copies' was 1 or more than 1. We modified our solution a bit and got accepted. Though, I would admit it was a mistake on our part too, but it could have had been framed better, much better. May be the obscurity was intentional. We were now on 23rd position, and about half the time was over.
Now, I tried some more on the problem G, but to no avail. So, I asked Mahsheed and Anil to try their approach of problem C. They tried very hard but met with no success. Anil was so tired, he asked Ajay Somani was walking through the aisle, 'Dude, Paani le ke aa naa' :P , mistaking him to be a volunteer :P , this later led to him taking some ( > 1) breaks :D :D. All the solutions which we tried for C, kept giving WAs (Wrong Answers). Looked for other problems too, was not sure about H (in the hindsight, I think I should have gone for it). Somehow, I being my persistent self stuck to G kept racking my brain for that O(N) solution, and in the end.. the third balloon never came. We ended 24th, missed our target of a top 10 finish, and even the modest target of top 20 (courtesy unsuccessful submissions). Anyways, I was in a really irritable mood after that (sorry team-mates for the grumpy behaviour :( ).
There was this prize distribution ceremony later. Firstly there was a presentation made by this really cool guy called Linkesh Diwan on Global Warming and the effects of man's greed on the environment (especially the Pacific Gyre). He was selected to represent the Indian youth at the Copenhagen Summit. He had infact made this banner titled 'Seal the Deal at Copenhagen' to urge the world-leaders to finalize an climate-change agreement, we all signed the banner. We now know what happened there :( .
Later there was a presentation made by IBM, and then a really boring, exhausting, mindless, pointless, ridiculous talk by a TCS fellow. The drone went on for a millenium! Finally, they distributed the certificates later, and we went back to the Ashram and relaxed.
(To be contd.)
0 comments:
Post a Comment