Introduction
Every year since 1977, the ACM has organized the ACM International Collegia
te Programming Contest. This contest, which consists of a regional qualifyin
g contest and the Finals, provides college students with the opportunity to
demonstrate and sharpen their programming skills. During this contest, teams
consisting of three students and one computer are to solve as many of the g
iven problems as possible within 5 hours. The team with the most problems so
lved wins, where ``solved'' means producing the right outputs for a set of (
secret) test inputs. Though the individual skills of the team members are im
portant, in order to be a top team it is necessary to make use of synergy wi
thin the team. As participants in the 1995 Contest Finals (two of us also pa
rticipated in the 1994 Finals), we have given a lot of thought to strategy a
nd teamwork.
In this article we summarize our observations from various contests, and we
hope that if you ever participate in this contest (or any other) that this i
nformation will be valuable to you.
The Basics: Practice, Practice, Practice!
Because of the fact that only one computer is available for three people, go
od teamwork is essential. However, to make full use of a strategy, it is als
o important that your individual skills are as honed as possible. You do not
have to be a genius as practicing can take you quite far. In our philosophy
, there are three factors crucial for being a good programming team:
Knowledge of standard algorithms and the ability to find an appropriate algo
rithm for every problem in the set;
Ability to code an algorithm into a working program; and
Having a strategy of cooperation with your teammates.
Team strategy will be the core discussion of this article. Nevertheless, the
re are some important considerations for improving your individual skills.
After analyzing previous contest programming problems, we noticed that the s
ame kind of problems occurred over and over again. They can be classified in
to five main categories:
1. Search problems. These involve checking a large number of situations in o
rder to find the best way or the number of ways in which something can be do
ne. The difficulty is often the imposed execution time limit, so you should
pay attention to the complexity of your algorithm.
2. Graph problems. The problems have a special structure so they can be repr
esented as a graph-theoretical problem for which standard algorithms are ava
ilable.
3. Geometrical problems. These involve geometrical shapes, lines, and angles
.
4. Trivial problems. The choice of appropriate algorithm is clear, but these
usually take quite a long time to program carefully.
5. Non-standard problems.
For the first three categories, standard algorithms are well documented in t
he literature, and you should program these algorithms beforehand and take t
he listings with you to the contest. In this way, you can avoid making the s
ame (small) mistakes repeatedly and you can concentrate on the difficult asp
ects of the problem.
Another angle of practice is efficient programming. This does not mean type
as fast as you can and subsequently spend a lot of time debugging. Instead,
think carefully about the problem and all the cases which might occur. Then
program your algorithm, and take the time to ensure that you get it right th
e first time with a minimum amount of debugging, since debugging usually tak
es a lot of valuable time.
To become a team, it is important that you play a lot of training contests u
nder circumstances which are as close to the real contest as possible: Five
hours, one computer, a new set of problems each time, and a jury to judge yo
ur programs.
Team Strategy: The Theory
When your algorithmic and programming skills have reached a level which you
cannot improve any further, refining your team strategy will give you that e
xtra edge you need to reach the top. We practiced programming contests with
different team members and strategies for many years, and saw a lot of other
teams do so too. From this we developed a theory about how an optimal team
should behave during a contest. However, a refined strategy is not a must: T
he World Champions of 1995, Freiburg University, were a rookie team, and the
winners of the 1994 Northwestern European Contest, Warsaw University, met o
nly two weeks before that contest.
Why is team strategy important? There is only one computer, so it has to be
shared. The problems have to be distributed in some way. Why not use the syn
ergy that is always present within a team?
``Specialization'' is a good way of using the inherent synergy. If each team
member is an expert for a certain category of problem, they will program th
is problem more robustly, and maybe more quickly than the other two team mem
bers. Specialization in another sense is also possible. Maybe one of the tea
m is a great programmer but has poor analytical skills, while another member
can choose and create algorithms but cannot write bug-free programs. Combin
ing these skills will lead to bug-free solutions for difficult problems!
Another way to use synergy is to have two people analyze the problem set. Fo
ur eyes see more than two, so it is harder for a single person to misjudge t
he difficulty of a problem. Forming a think-tank in the early stages of a co
ntest might help to choose the best problems from the set and find correct a
lgorithms for them. However, once the algorithm is clear, more than one memb
er working on a single program should be avoided.
It is our experience that the most efficient way to write a program is to wr
ite it alone. In that way you avoid communication overhead and the confusion
caused by differing programming styles. These differences are unavoidable,
though you should try to use the same style standards for function and varia
ble names. In this way you can really make 3*1 equal to four!
Other Considerations
Since the contest final standings are based on the number of problems correc
tly solved, and (in the case of ties) on the sum of elapsed time for each pr
oblem, a team should adopt a strategy that maximizes the number of solved pr
oblems at the end of the five hours, and view the total elapsed time as a se
condary objective. In every contest there are some teams in the ``top six''
after three hours, that are not even in the ``top ten'' after the total five
hours. The reverse also occurs. A long term strategy is therefore important
: Try to optimize the 15 man hours and 5 hours of computer time, and do not                                             
worry about your total time or how quickly you solve the first two problems.

To optimize this scarce time, try to finish all problems that you start. A 9
9% solved problem gives you no points. Analyze the problem set carefully at
the beginning (for example, by using a ``think-tank'' approach) to avoid spe
nding more time than absolutely necessary on a problem that you will not fin
ish anyway, and to avoid misjudging an easy problem as being too difficult.
You need a good notion about the true difficulty of the various problems as
this is the only way to be sure that you pick exactly those which you can fi
nish within five hours.
Since you never have perfect information, you have to take risks. If you fol
low a risky strategy by choosing to tackle a large number of problems, you m
ight end up in the bottom half of the score list when each is only 90% solve
d, or you might be the winner in the end. On the other hand, choosing a smal
ler number of problems has the risk that you have solved them correctly afte
r four and a half hours, but the remaining time is too short to start and fi
nish a new problem, thus wasting ten percent of the valuable contest time.
Time management should play a role in your strategy. If you are going to wor
k on a large problem, start with it immediately or you will not finish it. A
lthough this sounds trivial, there are a lot of teams which start out with t
he small problems, finish them quickly, and end up with only three problems
solved because they did not finish the larger ones. In our opinion, debuggin
g should have the highest priority at the terminal after 3.5 hours. When you
start with a new problem that late in a contest, the terminal will become a
bottleneck for the rest of the contest.
Of course terminal management is crucial. Though most programs are quite sma
ll (usually not exceeding one hundred lines of code), the terminal is often
a bottleneck: Everyone wants to use it at the same time. How can this be avo
ided? The first thing to remember is: Use the chair in front of the terminal
only for typing, not for thinking. Write your program on paper, down to the
last semicolon. In this way you usually have a much better overview, and yo
u have the time to consider all possible exceptions without someone breathin
g down your neck, longing for the terminal. Once you have finished writing,
typing will take no more than 15 minutes. Though you should avoid debugging
(this IS possible if you plan the program carefully on paper), when you real
ly have to do it you should do it in a similar way: Collect as much data as
possible from your program, print it out and analyze it on paper together wi
th your code listing. Real- time tracing is THE ULTIMATE SIN.
Some Example Strategies
1. The Simple Strategy
This strategy is quite useful for novice teams, or those who do not want to
get into a lot of practice and strategy tuning, and, therefore, is in no way
optimal. The basic idea is to work as individually as possible to try to mi
nimize overhead. Everyone reads a couple of problems, takes the one he likes
most and starts working on it. When a problem is finished, a new one is pic
ked in the same way and so on.
Advantages are that little practice is needed. Total elapsed time will be mi
nimal, since the easiest problems are solved first. However, there are also
severe disadvantages: Since the easiest problems usually have the same level
of difficulty, everyone will finish their problem at about the same time. T
hus the terminal will not be used for the first hour, since everyone is work
ing on a problem on paper, and remains a bottleneck thereafter. Furthermore,
only the easy problems will be solved, because no time will be left for the
hard ones. The conclusion is that, provided your programming skills are ade
quate, you will solve about three or four problems as a team. This will brin
g you, with a good total elapsed time, into the top ten, but probably not in
to the top three.
2. Terminal Man
In the terminal man (TM) strategy, only one of the team members, the T, uses
the computer. The other two team members analyze the problem set, write dow
n the algorithms and the (key parts) of the code, while the T makes the nece
ssary I/O-routines. After an algorithm is finished, the T starts typing and,
if necessary, does some simple debugging. If the bug is difficult to find,
the original author of the algorithm helps the T to find it.
Advantages of this strategy are that the terminal is not a bottleneck anymor
e, and the task of solving a problem is split over people who specialized in
the different parts of the problem solving process. A disadvantage is that
no optimal use is made of the capacities of the T, who is mainly a kind of s
ecretary. If you only one of you is familiar with the programming environmen
t, this might be a good strategy. You can write a lot of programs in the fir
st part of the contest when your brain is still fresh, since the typing and
debugging is done by someone else. It depends strongly on the composition of
your team if this strategy is suitable for you.
3. Think Tank
The strategy we followed during the preparation and playing of the Contest F
inals of 1995 made use of the above-mentioned ``think tank'' (TT). We felt t
hat choosing and analyzing the problems was such a crucial task in the early
stages of a contest that it should not be left to a single person. The two
team members who are the best problem analyzers form the TT and start readin
g the problems. Meanwhile the third member, the ``programmer'', will type in
some useful standard subroutines and all the test data, which are checked c
arefully. After 15 minutes, the TT discusses the problems briefly and picks
the one most suitable for the third team member. After explaining the key id
ea to the programmer, they can start working on it. Then the TT discusses al
l problems thoroughly, and puts the main ideas of the algorithm down on pape
r. We found out that two people examining hard problems often lead to creati
ve solutions. After one hour the TT had a good overview over the problem set
, and all algorithms were found. The next decision is how many problems you
want to solve. The easiest or shortest problems are handled by the programme
r, while the TT divides the other ones among themselves.
The terminal is only used for typing in code from paper or gathering informa
tion from a buggy program. If a program is rejected by the jury and no bug c
an be found, it is put aside until the last hour of the contest. In principl
e, after three and a half hours no more new code is typed. The team will bri
efly discuss the situation, and a plan is made for how to solve the problems
which have yet to be debugged.
Some advantages of this approach are that you will almost always tackle the
programs which have a reasonable chance of being solved correctly, and the h
ard problems can be solved because the TT will start working on them in an e
arly stage of the contest. A clear disadvantage is that you will have a rela
tively slow start and your total time is not optimal. So to win, you need to
solve one problem more than the other teams. We feel that for a team consis
ting of partners with about equal skills, this strategy will help you solve
as many problems as possible.