Several hours ago was the 2009 ACM-ICPC Asia Regionals Manila Site hosted by the Ateneo de Manila University. ACM-ICPC is a programming contest 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 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. 
======================================
Related posts:
Woot, congrats! Great experience to!
Can you give me the problem set link?
Hi mik, congratulations! We were very happy finally made it to the top as the regional champ for the first time, SOGo NI E.T fröm UP diliman. Congrats 2 u as well. Hope 2 c u next year! Sabi ko sa mga cntestants ko may 2nd year jan sa up frm philsci davao, hahaha, gus2 ka sana nila mameet, pero wla talagang chance.ù hahaha
Happy na rin ako kasi, we got d best team in mindanao, and we have improved a lot with our standing as one of d best performing schools in the Philippines and we entered the top 10 best performing schools overall in d competition.ù
Nakita kita ata Mikko!
) I think team 48 kayo. Tama?
4 problems out of 10 lang nasolve namin.
And teams doesn’t really need a real mathematician, but it is super benefit. Kasi one team from ours di nasolve yung problem A which involves parabola. And no one from DLSU solve it, so, no green balloon for the green teams.
) Siguro, experience lang kaya na isolve ang mga math problems. Kulang lang tayo dun sa experience na yun.
Sayang nga kami nakasolve kami ng 4 problems in 2 hours. Then we ended up solving only 4 problems. So, may nonsense time kami ng 3 hours. Dahil naubusan kami ng energy. Nakalaban namin ang pagod. Which is after 2 hours ay tuyo na utak namin. Di na nag wowork. Still, we managed to passed to problems after that, but too bad, wrong answers sila.
Nice experience Mikko!
And by the way, may isang BS Math dun sa team na minention ko.
@Exan: Sayang nga eh. Bobo rin ako magrecognize ng mukha.
@Jolo: Yup, team 48 kami. Bitter talaga ako dun sa A(H1N1) kasi isang line lang ang mali sa BFS. Dun din sa Summation kasi maraming nakasolve tas ang amin TLE. Well, meron pa tayo ilang years.
Congrats, Mikko! Ang galing! Keep it up.
Wala! BIGATIN KA PA DIN!
haha. elibs ako sayooo!
Congrats!!.. ok lang yan… winner ka pa rin sa mata ni GOD.. better luck next time na lang… ^_^ God bless..