A Commentary on Problems Given During the ACM ICPC Philippines 2007

Last October 20, 2007 I directed the First Philippine National Inter-Collegiate Programming Competitition (ACM ICPC Philippines 2007). This contest is affiliated with the ACM ICPC Asia-Singapore Regional Site. I spearheaded the organization of the contest in my capacity as the ACM ICPC Philippines Representative and on behalf of the Computing Society of the Philippines. The contest was hosted by De La Salle Canlubang. ACM stands for Association for Computing Machinery.

The following is the composition of the ACM ICPC Philippines 2007 Board of Judges:

Dr. Rafael Saldaña (Ateneo de Manila University) - Chair
Dr. Henry Adorna (University of the Philippines -Diliman) - Member
Dr. Eliezer Albacea (University of the Philippines -Los Baños) - Member
Dr. Jaime Caro (University of the Philippines-Diliman)- Member
Dr. Caslon Chua (De La Salle University - Manila) -Member
Dr. Nelson Marcos (De La Salle University - Manila) -Member
Dr. Raymond Todd Melton (Ateneo de Manila University)- Member

The Board of Judges prepared six (6) problems to be solved by the contestants in three (3) hours. The problems ranged from 'easy' to 'difficult'. They are standard problems in computer science.

The following are the problems given during the ACM ICPC Philippines 2007:

1. Problem A: Forward and Backward
2. Problem B: Counting Corners
3. Problem C: "NBN"
4. Problem D: Longest Common Subsequence
5. Problem E: Factor Factory
6. Problem F: Full Binary Search Tree

The easiest among the six problems is Problem A (Forward and Backward) while the most difficult is Problem E (Factor Factory). Out of 50 teams that participated in the competition, 35 teams were able to solve Problem A while 15 teams did not. No team was able to solve Problem E.

I was the one who gave Problem A. I gave this problem to ensure that most teams will go home with a balloon after the contest. (Note: A trademark of ACM programming contests is the giving of color-coded balloons to teams that have solved a problem. For example, if one team was able to solve 6 problems then that team will receive 6 balloons).

Problem A deals with palindromes. As explained in the problem formulation, a palindrome is a "word, phrase, number or other sequence of units that has the property of reading the same in either direction." For example, the word tenet and the number 123321 are palindromes. A number that is a palindrome is called a palindromic number. [ Note: I made several blog entries on palindromes in my blog last August 2007 :) . I got fascinated with palindromes when I found out that my phone number is a palindromic number. See http://raffysaldana.blogspot.com/2007/08/palindromes-and-palindromic-numbers.html]

The solution to Problem A involves comparing the first element of a string with the last element, the second element with the second to the last element, etc. until there are (N/2) comparisons done, where N (an integer) is the size of the given string. If all comparisons are successful then the given string is a palindrome.

The solution to Problem A is quite trivial. This makes me wonder why 15 out of 50 teams who joined the competition were not able to solve it.

What are the factors why a team gets zero in an ACM programming competition?

Here are my guesses:

1. Lack of preparation/experience/team work
2. Nervousness
3. Not reading the problem formulation carefully
4. Not fit for competition

I would like to encourage schools (offering bachelors' degree in computer science, computer engineering, information science, information technology, or related courses) to join ACM programming contests such as the Philippine National Inter-Collegiate Programming Competition to benchmark their students' aptitude in computer programming and problem solving.

Dr. Rafael P. Saldaña
Director
ACM ICPC Philippines
10/30/07