Friday, April 7, 2006

Google India Code Jam 2006 Day 2, The Contest Begins!!

We headed to the Reliance WebWorld (an Internet Cafe) to compete for the Championship Round.

Using bus (just like last year), we went to the Reliance WebWorld internet cafe.

The TopCoder admin, known as TheFaxman, introduced the rules and the extended duration for the Final Round.

This is the computers preconfigured for contest.
Only 5 applications can and allowed to run in this computer: The Arena, STL Doc, JavaDoc, VIM, Emacs.

The Coding Phase!

Now the contest begins!! We have to solve 3 problems of different points (250, 500, and 1000 points). For you who're curious what's the contest problems look like? Click on the problem name to see the problem statement (but remember not to copy it for other use!). Below is my discussion for each problem:

  1. Problem 300: InverseLca

    This problem is about Tree Data Structure. We are given a matrix that represents the Least Common Ancestor for all pairs of nodes and we should return the parent of each node. This problem takes me a lot of time to code! I submitted after 30 minutes I opened the problem, that was very slow coding!

    After I opened the 500 point problem and submitted it, I go back to this problem since I'm not sure that my code was free of bug... so I made a testcase with 10 nodes, create the LCA matrix and input it to the Arena's test case then run it... Jebret... whatt.. -2 -2 -2 ??? The value -2 was not supposed to be returned! I realized that my code Indeed has bugs in it... but it's too late, It's only 4 minutes remaining. I never know where was my bug.

    After the Coding Phase has ended, there's a Challenge Phase. Where you can view your competitor's source codes and challenge it using your testcase to make the program return incorrect result. Since I already got my testcase with 10 nodes, and I have faith that there are people out there that was as careless as I was, so I challenged any code that is too long or too simple or too suspicious with my 10 nodes testcase :D. It appeared that I made 7 successfull challenges out of 20 challenges (YUP! 20 Challenges! I'm a brute-force challenger at that time). In the end, I only got +25 points. I really dissapointed that I didn't challenge and look at the standings simultaneously. If only I looked at the standings, I would've stopped challenging after I got 4 straight successfull challenges (this will bring me to the TOP 10).

  2. Problem 500: ColoredDominoes

    This problem is about eficient brute force. You were given a list of dominoes and their colors on both of the halves. You wanted to re-color the dominoes so that all dominoes has the same color. (for the detailed problem statement, click on the link above)

    The trick to solve this problem is to do a brute force only for the unique colors. If we count it carefully, the input parameters implicitly restrict the number of different colors to be 1000, not 10000. So an O(n^2) algorithm is sufficient. This problem is a lot easier than the Problem 300 since the solution quite easy to be found : Brute Force + Greedy.

  3. Problem 1000: InterestingStrings

    I read the problem statement, then I look at the time... 30 minutes left... Ahh.. just forget this problem, I'll never make it on time. This is the time when I opened back my 300 points problem and make a testcase of 10 nodes and realized that my 300 points was wrong :( and didn't have time to fix it.

The Challenge Phase

I don't remember how stressed I was when I knew that my 300 points will gone. Thinking of it, it burns me with and idea: I have the test-case that failed on me, why don't I use it to challenge the others? :D HeHeHeh! Here it goes, my Brute-Force Challenges! I opened every 300 points problems that were available and immediately challenge it if I found it too long or too short or suspicious :D. During that time, probably because I was too excited opening and closing the Source code, My Arena went TIMEOUT. It happened several times... reducing my opportunity to challenge! I only (yeah only!) made 20 challenges. If only there wasn't any Timeout (and I didn't have to relogin), probably I can made 25 challenges! (and probably my points would be minus... ahahahah).

And so the contest has ended, we were allowed to take home the Google Mouse Pad and Google Pen :D How generous Google was!

We then went back to the Park Hotel to get some rest.

Yo yo yo in the bus.. we take pictures again.

In the Park Hotel, all Indonesian participants assembled in Prima Chairunnanda's Room (106) and order some dessert.

Next : Le Meridien and Google Tech Talk

Back to Home

No comments:

Post a Comment