COMMON MISTAKES IN ONLINE
A ND REAL-TIME CONTESTS
by Shahriar Manzoor
Each year the Association for Computing Machinery (ACM) arranges a worldwide programming con-
test. This contest has two rounds: the regional contests and the World Final. The teams with the
best results in the regional contests advance to the World Final. The contest showcases the best
programmers in the world to representatives of large companies who are looking for talent. When prac-
ticing for programming competitions, remember that all your efforts should be directed at improving
your programming skills. No matter what your performance is in a contest, do not be disappointed. Suc-
cess in programming contests is affected by factors other than skill, most importantly, adrenaline, luck,
and the problem set of the contest. One way of getting immediate feedback on your efforts is to join the
Valladolid Online Programming Practice/Contest or the online judge hosted by Ural State University
(USU). Successfully solving problems increases your online ranking in the respective competitions.
This article is for beginning programmers who are new to programming contests. I will discuss the common problems faced in contests,
the University of Valladolid online judge, and the USU online judge.
The suggestions are divided into three parts: General Suggestions,
Online Contest Suggestions, and Valladolid-Specific Suggestions.
Throughout this paper, please note that in real-time contests, the
judges are human and in online contests, the judges are computer programs, unless otherwise noted.
Different Types of Programming Contests
Many programming contests take place throughout the year, such as ACM
regional contests, International Olympiad in Informatics (IOI), Centrinës Europos Informatikos Olimpiados (CEOI), and Programmer of the
Month (POTM) contest. The most prestigious live programming contest
is the ACM International Collegiate Programming Contest (ICPC), and
the most prestigious online contest is the Internet Problem Solving Contest (IPSC). In this section, I will discuss some of the contests.
ACM International Collegiate Programming Contest (ICPC)
ICPC, first held in 1977, is now held yearly [ 4]. The contest lasts five
hours and generally contains eight problems. (However, the 2001
World Finals contained nine problems.) Three person teams are allotted a single computer. The teams submit their solutions to a judging
software named PC2 developed at California State University, Sacramento (CSUS). The permitted programming languages are C/C++,
Pascal, and Java.
Online contests require no travel and are often less tense [ 1]. The submission rules for the online contests at the Valladolid site and the
USU online judge site are the same: the contestants must mail their solutions to a certain e-mail address. The IPSC rules are quite different.
The IPSC Contest Organizer provides inputs for the problems. Instead
of e-mailing their solutions, the contestants have to e-mail their outputs.
Some Tips for Contestants
A good team is essential to succeeding in a programming contest. A
good programming team must have knowledge of standard algorithms
and the ability to find an appropriate algorithm for every problem in
the set. Furthermore, teams should be able to code algorithms into a
working program and work well together.
The problems presented in programming contests often fall into
one of five categories including search, graph theoretic, geometric,
dynamic programming, trivial, and non-standard. Search problems
usually require implementing breadth-first search or depth-first search.
Graph theoretic problems commonly include shortest path, maximum
flow, minimum spanning tree, etc. Geometric problems are based on
general and computational geometry. Dynamic programming problems
are to be solved with tabular methods. Trivial problems include easy
problems or problems that can be solved without much knowledge of
algorithms, such as prime number related problems. Non-standard
problems are those that do not fall into any of these classes, such as
simulated annealing, mathematically plotting n-queens, or even problems based on research papers. To learn more about how problems are
set in a contest you can read Tom Verhoeff’s paper [ 6].
What You Should Do to Become a Good Team
There is no magic recipe to becoming a good team, however, by observing the points below (some of which were taken from Ernst et al. [ 3])
you can certainly improve. When training, make sure that every member
of the team is proficient in the basics, such as writing procedures, debugging, and compiling. An effective team will have members with specialties so the team as a whole has expertise in search, graph traversal,
dynamic programming, and mathematics. All team members should
know each other’s strengths and weaknesses and communicate effectively with each other. This is important, for deciding which member
should solve each problem. Always think about the welfare of the team.
Solving problems together can also be helpful. This strategy works when
the problem set is hard. This strategy is also good for teams whose aim