Felix Halim .NET

Saturday, March 26, 2005

Google India Code Jam 2005 Day 2, Google Tech Talk & Awards

The intense 2 hours contest has ended. We were moved to the Googleplex, the Google India Office in Bangalore.

The office is located in Prestige Sigma (1st and 2nd level)

In the Googleplex, we have a lunch. The waiter keep asking me to have more food on my plate! Damn... I barely emptied my plate!! The only food over there that I like is the kerupuk and the chicken :P

In this Googleplex, we have a lunch

Shortly after lunch, google then start talking (Google Tech Talk). Here Google explains why helding this competition event (you can guess, to recruit more people). They explains about Google Technology (I really impressed when they talk about the Distributed Computing, that is separating the jobs when doing a search). A single search of google, actually involving thousands of computer of cluster. This is very interesting! I wish I had a video camera...

The left pic is Lars? the one who accompany me during contest
The right pic is the waiters!! They keep adding foods to my plateee!!!

"Most people avoid problems... but we, programmers, like to solve problems :)" Google Presenter (what's his name?)

The presenter said something about Google motto. When Google develop something, they don't think: "Where is the Money?". When they know what they're developing makes the user happy, they know there's money in it :) Coolll! I think this is statement is quite true as I see many google software really2 easy to use and useful but I don't see how it relates to money... (they really2 focus on users need).

The Google Technical Talks begins
They cover interesting topics behind the Google Technology

The left pic is Krishna Bharat. He explains why Google arrange this contest & the history of Google
The right pic is ... He explains the Google Technology in big picture (distributed sytem)
Some body please give me their names!! (email me: felix.halim@gmail.com)

After the Google Tech Talk, here comes the winner announcement!

The left pic is the one who turn on the ranklist of the winners on the projector.
The right pic is Sreeram Ramachandran (Indian in Singapore), the fifth place.

First and Second winners, from Indonesiaa!! Yeeaaa!
The left pic is Ardian KP. The right pic is Pascal Alfadian

Lets see in bigger pic, our Indonesian programmers berjaya di India.
Left to right: Pascal Alfadian (2nd winner), Ardian KP (1st Winner)

The first to the fifth winner then were interviewed by local reporter! Waw

Ardian KP being questioned by local reporters: "how do you feel?" :)

This is the winners, from left to right is the fifth place to the first place.
This picture is taken from Prima C's Camera

As usual, we are all "keganjenan". Then take photo together...
This is a pic of all of 7 Indonesians (except Lars)

The winners list can be looked here. We then going back to the Park Hotel by bus again :)

Next : Take a walk and dinner party

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

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:

Problem 250: WebSpider

This is the easiest problem among the three (you can click on the WebSpider link above to view the problem statements). This problem is about google engine crawling a website (google banget sih). You have to build a program to determine the number of unique files in the website that the google engine had crawled! For example, Google engine crawl a website and finished crawling and travels three levels deep. So now google engine has 3 passes (3 pages of the website that has been crawled). The first pass would be the home-page of the website. The second pass would be the page that linked from the home-page. The third pass would be the page that linked from the second pass. (just like DFS..).

Now you have the three pages that google engine has crawled: the page from the first pass, second pass, third pass. In each pages there are links in it, right? Now, you have to write a program that receive input of lists of all the links found in the first pass, in the second pass, and in the third pass and determine the number of unique "files" found... got the idea of the problem now?

The difficulties that arise from this problem is that... There could be a link that refer back to the same page/file. So? eventhough google found a thousand links when crawling a site that does not necessary mean that there is a thousand unique file linked... probably there's only 50 unique file (since many of the links refer to the same file/page). A "file" in this case is a page in a link (for example: a link support/login.jsp in this case, login.jsp is the file or the page). You have to determine the number of unique file from the three passes done by the google engine!

I solve this problem within 1 hour... I just use java.util.HashSet and string manipulation. I convert all the links into an ABSOLUTE path-link then add it to the HashSet, if it turns out to be in the set, the HashSet will ignore it. Therefore the answer is the size of the HashSet :) The examples given by the problem statement was plenty and very clear! I think this problem really2 was a bonus problem!
Problem 500: TripMapper

This problem, TripMapper, I should have known that it's a TrapMapper!! (I mean it's a Trap). A trap for Time Limit! Damn... I thought it was output time oriented... Anyway, you can look at the problem statement by clicking the link of the problem name above.

The second problem worth twice points from the first problem, but?? No One solves this problem during the contest! Most of the submitted code was successfuly challenged by Pascal AN... (including mine). He knew exactly that BFS/DFS/BruteForce will fail on the time :) (Damn... I thought my Iterative Deepening was impeccable :P)

Ok, let me say something about the problem. The problem is just a regular Shorthest Path problem but what made it different from the regular shortest path is that its DATA STRUCTURE!!! (damn.. they play on the data structure). It's quite hard to translate the "map" to a collections of nodes and edges. I hate intersections!! They present the map with grids 550 x 550. Guess what? I multiplied it again by two to avoid short-circuit for adjacent node. I guess this was the culprit of my TLE. You can look at the problem statement to get the idea of the map.

Conclusion: I should've never touched this problem!

Sindux feels that problem 500 is similar with the previous TopCoder contest: http://www.topcoder.com/stat?c=problem_statement&pm=2979&rd=5877
Problem 1000: Conquest

Guess what? I didn't even have time to read this problem statement! (not enough time). But our number one winner, Ardian KP, brilliantly leaves the 500 problem intact and head directly to attack this problem (which he thought was easier, DP -> his specialty... gimana gak easier?).

Comment: No comment... Ardian, maybe you want to comment on this one? drop me an email : felix.halim@gmail.com

Next : Google Tech Talk & Awards

Google India Code Jam 2005 Day 2, Breakfast, Briefing and go to the Cafe!?

Early in the morning I woke up do all necessary things people do in the morning then put Google T-Shirt on.

The left pic is me in Google T-Shirt. The right pic is the morning view :)

I'm was still too excited with mirrors... so whenever I see "me" on the mirror, I can't resist the temptation to take a picture of me... :P

Me in Google T-Shirt. The left pic is the mirror in front of the bath room.
The right pic is the mirror in front of the lift.

I then headed to the Oak Room for Breakfast. The room is still in the Park Hotel.

I came early to the Oak Room, so the picture wasn't crowded.

After the others assembled in the Oak Room we take pictures and have chat with one of the Google staffs.

Picture of us, contestants of the same plane.

After finish our breakfast, we are introduced to the competition that we're going to do. We asked questions for the competition, the rules for the competition, etc...

George is the one that explains the rules. He's the TopCoder admin

After we are briefed about the competition rules. The contestant was splitted in to 2 groups going to 2 different places. I with Ardian and Renald was set to go to the Cunningham Road and compete in the Reliance - WebWorld internet cafe. We went there by bus.

The left pic is the agent checking the contestants.
The right pic is me sitting with Ardian KP.

This is the Reliance - WebWorld internet cafe.
TopCoder Competition doesn't need a special place.
Internet Cafe is a Great Place!

The internet cafe was set up for the competition. The Contest Arena Web Start Application was downloaded and run. The JavaDoc, SGI STL, Emacs, GMVI are all installed and available.

The left pic is the outside of the contest room, its for guest.
The right pic is in the contest room, its for competition.

This is the computer that I'm going to use for the contest. Cool isn't it?

I took these pictures around me.

These are the peripherals around me. The mouse is cute and big.
The seat was quite good and comforting
There's a gas and brake under the table for car gaming :o

Next : The Contest Begins!!

Friday, March 25, 2005

Google India Code Jam 2005 Day 1, Take off to Bangalore, India

At 9:30 AM, I was heading to the Soekarno-Hatta airport and meet with my friends from Universitas Parahyangan, Bandung: Pascal Alfadian Nugroho and Renald.

From left to right: Me (Felix Halim), Pascal AN, Renald

There wasn't any difficulties going to Singapore. During the transit, we met the other Indonesian friends: Ardian KP, Bramandia R, and Prima C. Also we met other contestants that appeared to be on the same flight.

Singapore Airlines... each seats has a monitor and a "controller".
When you flip the controller, it could be used as a phone.
It can call to any seats on the plane or call outside plane using card.

We then arrive at Bangalore International Airport after 4 hours flying.

Bangalore International Airport (Arrival). We are the last persons queuing.
At the right is the picture of Bramandia, Prima, and Ardian queueing.

There are 10 contestants in the plane. We assembled at the outside of the Bangalore International Airport waiting to be picked up by the agent.

Missing 2 people here (me tacking the picture and 1 other was phoning Mr. Tapas)

After phoning Mr. Tapas approximately 10 minutes we were escorted to the Park Hotel. The hotel is near the airport only 15 minutes distance by car.

We were checking in to the Park Hotel

I was assigned to room 104. Google is generous... each person was assigned to a double room (two persons). In the hotel, there was so many mirrors. I really loved it, I could take a picture of my self easily. Here you will find many picture of me reflected by the mirrors.

The left pic is me in room 104 posing.
The right pic is me in front of the hotel's lift posing :P

After putting our stuffs in our room and rest a bit, we were heading to the "Blue Box Room" (still in the Park Hotel) to get our Google T-Shirt. In fact we got not only Google T-Shirt but also Google Bag! (the inside of the bag was two Google Pen, a Google Bottle, and a Google Hat!). That's very nice gifts from Google India :)