ACMSolver :: Art of Programming Contest, Tips and Tricks for C, C++, Java

by Chua Hock-Chuan (ehchua@ntu.edu.sg)

To know more about ICPC, read the ICPC mother site (@ http://icpc.baylor.edu/icpc/) or Wiki “ICPC”. To summarize, ICPC is the programming contest for the university students (just like the IOI – International Olympiad in Informatics – is the programming contest for high school students). The ICPC contest rules are:

• Each team consists of THREE students
• Each team is given only ONE computer
• Each team is given 5 hours to solve 8-10 problems (in C, C++, Java and possibly Pascal)
• The team who solves the most number of questions in the shortest time is the winner
• There are two stages for the contest: Regional’s and the Grand Final. Winners of each regional contest proceed to the Grand Final

PREPARATION…

Step 0.1 – Read, Read, Read: on programming, data structures, algorithms, and object-oriented programming.

Step 0.2 – Pick your Language: Pick a programming language that you are comfortable, either C++ or Java or both (but not C nor Pascal as they lack advanced libraries).

Step 0.3 – Gather Programming Resources: Gather programming books and materials, especially online references and resources.

Step 0.4 – Setup your Programming Workbench: If you can afford a laptop, get one (so that you can program at the Starbucks and in the train).

Depending on the host, the contest could be run on Linux (most likely) or Windows or any other exotic machines.

For Java programmers
Use JDK 1.5 and above, which greatly simplifies the IO processing. The Java IDE of choice is certainly eclipse – an open-source IDE supported by IBM (the official sponsor of the contest), and it runs on both Linux and Windows. For newcomers, read “How to install Eclipse“, “writing your first Java program in Eclipse“, and “debugging Java program in Eclipse“.

For C/C++ programmers
It is harder to decide because you have a few options:

• In Windows, you could practice on Microsoft Visual C++ 2005 (an Express version can be freely downloaded from Microsoft). For newcomers on VC++, read “Write a C++ program in Visual C++“, and “Debugging C++ program in Visual C++“.
• In both Linux and Windows, you could use the open-source Eclipse C/C++ Development Tool (CDT) IDE combined with Cygwin’s GCC/G++ compiler. For newcomers, read “How to install Cygwin“, “How to install Eclipse CDT“, “Writing first C++ program in Eclipse CDT“, and “Debugging C++ program in Eclipse CDT“.
• [TODO] Linux’s IDE.

Important for All Programmers

• You should be familiar with the use of graphical debugger to improve your programming efficiency and productivity.
• You should be familiar with the libraries, such as Java’s API and C++ STL.
• [TODO] more

Step 0.5 – Online Judges and Training Sites: There are many “online practice sites” called online judge, that archive hundreds (or even thousands) of past contest problems. You could try the problems at your own time and own target, and submit your solutions online. You program will be automatically compiled and run with a carefully-designed set of test inputs. The status of the run, such as “accepted”, “wrong answer”,”compile error”, “presentation error”, “time limit exceeded”, “memory limited exceed”, “output limit exceed” will then be shown to you. In the case of compilation error, some of the sites may also show you the compilation error messages.

These are the sites that I frequently used (google or wiki “icpc”, “online judge” to get the full list).

• Peking University Online Judge (PKU): This site support many languages, including Java (JDK 1.5), GNU’s GCC/G++ (for C/C++) and Visual C/C++ version 6.
• Universidad de Valladolid Online Judge (UVA): This is the most reputable site, with a good forum (equipped with search). The support for C++ is excellent, however, the support for Java is mediocre (no JDK 1.5).
• USA Computing Olympiad (USACO) Training Program: This is the training site for IOI (International Olympiad in Informatics for high school students) instead of ICPC. However, it provides a very systematic training on the algorithms frequently encountered in contests, e.g., shortest path, greedy, dynamic programming, heuristic search, minimum spanning tree, and etc. It supports C, C++ and JDK 1.5.

[...]

By Ahmed Shamsul Arefin

Hello programmers, after “A Virtual Meeting with Worlds ACM-ICPC Programmers” [1] again I am back to the readers with the stories of a few people who are dedicatedly working for the development of ACM/ICPC spirit around the world. Some of us have already met with following people, so I guess I can take an opportunity to tell a brief story about these wonderful people whose enthusiasm have made a prestigious class of people called “ACM Programmers”.

Dr. William B. Poucher

Dr. Poucher is an ACM Fellow and Professor of Computer Science, Baylor University. He has got his Ph. D in from Mathematics of Computing (Combinatorics), Auburn University, M.S. in Mathematics and B.S. in Mathematics Music, Auburn University.

[...]

Though Bangladesh is a third world country, we have many limitations here but we are doing well in programming contest the majestic competition of wit and wisdom. We have done well not only in online contests but also in the ICPC or real-time contests. But it is centralized (conceptually and geometrically (in the map)) in one area – *Dhaka*. Only few university students from capital city are doing well. All are renowned Public or Private Institutes (especially BUET, DU, NSU, EWU, AIUB, SEU) and under extreme facilities than the other universities all over Bangladesh. Good teachers, rich library, better students from all over the country are the main factors of doing well in contests. What about the institutions or universities situated in a rural area and about miles away from the main town. You may wonder! In many public universities outside the towns do not have adequate internet connection for its computer science students. Some of our students come to town and browse in the cyber-cafes and submit problems. Don’t think that it is cheap; it is costly for the students. The students from outside the town don’t get extra money from their parents to do programming contest like extra curriculum. They do these things by saving money by working as a private tutor in the town. No coach, no good new books, no internet or communication facilities are making this meritorious students just a lay man! But recently some universities out-side of Dhaka (like SUST, CUET,RU-one/two teams) are doing better, it is only because of their students’ own effort.

[...]

The content of the article that I am about to write is triggered by (a) my semi recent visit to USA to attend and Judge in ACM International Collegiate Programming Contest 2006, World Finals (b) an email from a former contestant of Bangladesh (now studying in Stony Brook University, USA) and (c) something more. The title of this article is Independent Paragraphs (II) because in 2004 I wrote an article titled “Independent Paragraphs”. Like that previous article, the different parts of this article may or may not be related to one another.

My visit to US:

Like Mr. T of the popular movie of the 80’s “The A Team” I am very afraid of flying. So when I came to realize that I have to go to USA, I was afraid thinking how I would fly such a long distance safely? I like probability and statistics so I browsed the internet to find out which air lines is statistically the safest and found out that it was the costliest British Airways. I also searched the internet and learnt the difference between Boeing and Airbus engines and after a lot of study became convinced that Boeing is slightly safer than Airbus in turbulent weather condition. The fact that concerned me is that a Boeing has only two engines and but an Airbus has four Engines which gives the Airbus a plus point in my book. I remembered the math I taught my students in the course “Probability and Queuing Theory”… “A engine has independent probability 1-p of failing during a flight. For what value of p is a four engine plane better than a two engine plane…”. I studied about air speed, ground speed, air sickness, parachute diving etc too. But in the end I went for Boeing (It wouldn’t be great to go down in turbulent weather) and also I went for British Airways (Statistically Safest). Although for making this choice I had to fly 2000 miles more.

[...]

by Ahmed Shamsul Arefin

1. Preface

Hello ACM-ICPC Programmers! I hope everyone is passing happy programming days. Today my purpose of this article is to introduce you few ACM-ICPC programmers. As a creator of ACM-ICPC Programming Contest Training Site ACMSolver (http://www.acmsolver.org), I met several programmers worldwide from some renowned universities over the Internet (and on Dhaka site event from 2000-2006), I could share knowledge and thinking with them and it became a pleasure for me, here goes some interviews of some of them. I think it will encourage new programmers to enter into the world of programming contest.

One thing I must tell, these interviews were taken over a time period from 2003-2004 (over E-mail), some of the programmers here may have left “problem solving”, but still I think these interviews are very much distinctive and appropriate for all time and all programmers. I wish many new programmers will come out time to time and I wish to take *a chance to talk with them* and try to bring them under lime light. May be that’s the beauty of ACM-ICPC!

2. A Meeting with Steven Halim, National University of Singapore

Arefin : Hello Steven! How is life? Would you please give us a brief introduction about you, your current works and activities?

Steven : Hello I’m an Indonesian, currently 21 years old at the time this page is written (Please visit : http://www.comp.nus.edu.sg/~stevenha/ for steven’s current status). I’m studying Computer Science in National University of Singapore, NUS. My Honors Year Project (thesis) regarding human guided Tabu Search (a local search algorithm). I’m currently active in Christian campus ministry and my church. I have been interested in programming since 7 years ago. My first programming language is Visual Basic 4. Amazed with the ability to create ‘windows’ similar to other programs in Win 95, I become interested to explore more about visual programming. However, my competitive programming experience started 4 years ago when I joined local programming competition. That is the first time I realized the importance of “algorithm” underlying our codes. Switching from visual programming to learn basic algorithm and data structures leads me to be able to compete in several other programming competitions, including International School Software Competition 1999 @ NUS, Singapore and ACM International Collegiate Programming Contest 2001 @ NTU, also in Singapore.

I’ve never won a programming contest anyway, but I managed to get valuable experience from those several contests. Now programming and solving problems has become my hobby and when I have free time, sometimes you can see me thinking in front of my computer solving one or two problems from UVA website.

[...]