The Geek Brewery

Several hours ago was the 2009 ACM-ICPC Asia Regionals Manila Site hosted by the Ateneo de Manila University. ACM-ICPC is a programming contests in which college students are to solve a certain number of problems in a limited number of time, in yesterday’s contest ten problems in five hours.

UP Diliman had ten teams in total, seven SOGO teams from the University of the Philippines Programming Guild and three teams from the UPD Department of Computer Science. I was a member of one of the SOGO teams, the SOGO Virgins.

Results, results and results!!

Our team only ranked 26th out of the 55 teams, which was quite disappointing. Among the 10 problems given, we only had three accepted solutions out of the five problems we attempted.

The champion was from our guild (UPPG), the Mga SOGO ni E.T.. They solved all 10 problems in 1 hour and 59 minutes. They will be competing for the World Finals this February 1 to 6, 2009 at Harbin University in China. Other teams who solved all 10 problems sorted by time were teams from Ho Chi Minh City University of Science, National University of Singapore, Hong Kong University of Science and Technology and another team from UP Programming Guild, SOGOng Long Ong Moy Poso. The freshie team (2 Young 2 SOGO) from our guild beat us as they solved 5 problems in all. Woot! For more detailed results, you may check out the contest director’s blog.

Problems encountered!

Experience is the best teacher. We encountered problems on some problems.

Problem A. Given three points on a parabola, get the maximum height of the parabola. Since we don’t have a mathematician in the team, we had a hard time finding an equation with degree one for all variables. We had to force one of our teammate (out of 3) to squeeze all his knowledge on parabolas. When he found one, I immediately coded Gaussian Elimination Method for two variables and two equations. Gladly, our solution was correct thus accepted by the judges.

On the summation problem, we got correct answers for the sample inputs but it was too slow that testing it on borderline cases (worst case scenarios) won’t yield a result in a reasonable amount of time. Since no one in our team was a mathematician, we had trouble limiting our search space. Our program was so inefficient but right that we were not able to have our solution accepted.

The other problem we attempted was the A(H1N1) problem. Given a set of N people in a community with their locations and radius of contact and a person infected by A(H1N1), we had to compute the number of levels of transmission until the virus is contained. We recognized that it was a graph problem; people as nodes then connect an edge to nodes within the radius of contact of an infected person. We just have to perform a BFS (Breadth-First Search) on the graph and find the  level distance from the root to find the maximum level of transmission.

The algorithm above was correct but I made a mistake in coding BFS. I colored the node after dequeuing it from the queue instead of coloring it while putting it on the queue as seen in my code below.

Damn. I admit that it was my fault, not anyone else’s. Hmmmmf. Waaaaaa. What a shame. On the other side, it still yielded the correct answer for the sample input.

Lessons Learned

• Never spend too much time on a single problem. We spent too much time debugging the A(H1N1) problem.
• A team needs a mathematician. There were quite a number of Math problems. We were only able to solve one out of all the Math problems.

Random Stuff

Even though we did not rank well, I was still happy of the outcome. Because of this contest, I will never forget BFS anymore! Hahahaha.

I am looking forward to joining the same contest for the next years if fate will permit.

I admit that I am bitter with the results of the Mensa IQ Challenge I took sometime last month. It was a BIG slap on my face, after self-proclaiming myself as a geek. I don’t believe you have to pass Mensa to be a full-pledged full-fledged (as corrected by Aldrin, point well taken) geek. Hahaha. Here’s something geekier than Mensa.

After two sessions of training on our new “programming guild”, I’ve encountered tons of intellectually challenging programming problems. The spectrum of problems were very wide; from counting descendants of a person in a family tree, to beating a greedy opponent on a game, to getting the height of a rocket model using three ground observers using a theodolite, and the list goes on and on.

I admit those problems were new to me and I think it was the best answer for my hunger for knowledge. Those problems squeezed my neurons to the highest level, thus greasing up my brain. Those were the problems that made me realize I still have a lot lot lot more to learn. I mean, A LOT!

To all other geeks out there who have a background on any programming language (preferably C or Java), I dare you to solve the problems on real ACM International Collegiate Programming Competition (ACM-ICPC). There are a lot of problems available there from ACM-ICPC contests around the globe.

So far, I have only solved four ACM-ICPC problems. My goal is to solve at least one per night. Good luck to me and have fun with those problems.