荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: selahx (宿醉未散,早梦半醒), 信区: ACMICPC
标  题: Teamwork in Programming Contests: 3 * 1 = 4
发信站: 荔园晨风BBS站 (2005年04月23日12:37:42 星期六), 站内信件

Teamwork in Programming Contests: 3 * 1 = 4
by Fabian Ernst
Jeroen Moelands, and Seppo Pieterse


Introduction
 Every year since 1977, the ACM has organized the ACM International Co
llegiate Programming Contest. This contest, which consists of a region
al qualifying contest and the Finals, provides college students with t
he opportunity to demonstrate and sharpen their programming skills. Du
ring this contest, teams consisting of three students and one computer
 are to solve as many of the given problems as possible within 5 hours
. The team with the most problems solved wins, where ``solved'' means
producing the right outputs for a set of (secret) test inputs. Though
the individual skills of the team members are important, in order to b
e a top team it is necessary to make use of synergy within the team. A
s participants in the 1995 Contest Finals (two of us also participated
 in the 1994 Finals), we have given a lot of thought to strategy and t
eamwork.

In this article we summarize our observations from various contests, a
nd we hope that if you ever participate in this contest (or any other)
 that this information will be valuable to you.


The Basics: Practice, Practice, Practice!
Because of the fact that only one computer is available for three peop
le, good teamwork is essential. However, to make full use of a strateg
y, it is also important that your individual skills are as honed as po
ssible. You do not have to be a genius as practicing can take you quit
e 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 appropriat
e algorithm 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. Nevertheles
s, there are some important considerations for improving your individu
al skills.
After analyzing previous contest programming problems, we noticed that
 the same kind of problems occurred over and over again. They can be c
lassified into five main categories:

1. Search problems. These involve checking a large number of situation
s in order to find the best way or the number of ways in which somethi
ng can be done. The difficulty is often the imposed execution time lim
it, so you should pay attention to the complexity of your algorithm.
2. Graph problems. The problems have a special structure so they can b
e represented as a graph-theoretical problem for which standard algori
thms are available.
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 documente
d in the literature, and you should program these algorithms beforehan
d and take the listings with you to the contest. In this way, you can
avoid making the same (small) mistakes repeatedly and you can concentr
ate on the difficult aspects 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 debuggin
g. 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 the first time with a minimum amount of debuggin
g, since debugging usually takes a lot of valuable time.

To become a team, it is important that you play a lot of training cont
ests under circumstances which are as close to the real contest as pos
sible: Five hours, one computer, a new set of problems each time, and
a jury to judge your programs.


Team Strategy: The Theory
When your algorithmic and programming skills have reached a level whic
h you cannot improve any further, refining your team strategy will giv
e you that extra edge you need to reach the top. We practiced programm
ing 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 the
ory about how an optimal team should behave during a contest. However,
 a refined strategy is not a must: The World Champions of 1995, Freibu
rg University, were a rookie team, and the winners of the 1994 Northwe
stern European Contest, Warsaw University, met only two weeks before t
hat 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 synergy that is always present within a team?

``Specialization'' is a good way of using the inherent synergy. If eac
h team member is an expert for a certain category of problem, they wil
l program this problem more robustly, and maybe more quickly than the
other two team members. Specialization in another sense is also possib
le. Maybe one of the team is a great programmer but has poor analytica
l skills, while another member can choose and create algorithms but ca
nnot write bug-free programs. Combining these skills will lead to bug-
free solutions for difficult problems!

Another way to use synergy is to have two people analyze the problem s
et. Four eyes see more than two, so it is harder for a single person t
o misjudge the difficulty of a problem. Forming a think-tank in the ea
rly stages of a contest might help to choose the best problems from th
e set and find correct algorithms for them. However, once the algorith
m is clear, more than one member working on a single program should be
 avoided.

It is our experience that the most efficient way to write a program is
 to write it alone. In that way you avoid communication overhead and t
he confusion caused by differing programming styles. These differences
 are unavoidable, though you should try to use the same style standard
s for function and variable 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
correctly solved, and (in the case of ties) on the sum of elapsed time
 for each problem, a team should adopt a strategy that maximizes the n
umber of solved problems at the end of the five hours, and view the to
tal elapsed time as a secondary 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 star
t. A 99% solved problem gives you no points. Analyze the problem set c
arefully at the beginning (for example, by using a ``think-tank'' appr
oach) to avoid spending more time than absolutely necessary on a probl
em that you will not finish anyway, and to avoid misjudging an easy pr
oblem as being too difficult. You need a good notion about the true di
fficulty of the various problems as this is the only way to be sure th
at you pick exactly those which you can finish within five hours.

Since you never have perfect information, you have to take risks. If y
ou follow a risky strategy by choosing to tackle a large number of pro
blems, you might end up in the bottom half of the score list when each
 is only 90% solved, or you might be the winner in the end. On the oth
er hand, choosing a smaller number of problems has the risk that you h
ave solved them correctly after four and a half hours, but the remaini
ng time is too short to start and finish a new problem, thus wasting t
en percent of the valuable contest time.

Time management should play a role in your strategy. If you are going
to work on a large problem, start with it immediately or you will not
finish it. Although this sounds trivial, there are a lot of teams whic
h start out with the small problems, finish them quickly, and end up w
ith only three problems solved because they did not finish the larger
ones. In our opinion, debugging should have the highest priority at th
e terminal after 3.5 hours. When you start with a new problem that lat
e 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 qui
te small (usually not exceeding one hundred lines of code), the termin
al is often a bottleneck: Everyone wants to use it at the same time. H
ow can this be avoided? 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 you have the time to consider all po
ssible exceptions without someone breathing down your neck, longing fo
r the terminal. Once you have finished writing, typing will take no mo
re than 15 minutes. Though you should avoid debugging (this IS possibl
e if you plan the program carefully on paper), when you really have to
 do it you should do it in a similar way: Collect as much data as poss
ible from your program, print it out and analyze it on paper together
with 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 wa
nt 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 pos
sible to try to minimize 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 picked in the same way and so on.

Advantages are that little practice is needed. Total elapsed time will
 be minimal, since the easiest problems are solved first. However, the
re are also severe disadvantages: Since the easiest problems usually h
ave the same level of difficulty, everyone will finish their problem a
t about the same time. Thus the terminal will not be used for the firs
t hour, since everyone is working on a problem on paper, and remains a
 bottleneck thereafter. Furthermore, only the easy problems will be so
lved, because no time will be left for the hard ones. The conclusion i
s that, provided your programming skills are adequate, you will solve
about three or four problems as a team. This will bring you, with a go
od total elapsed time, into the top ten, but probably not into 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 se
t, write down the algorithms and the (key parts) of the code, while th
e T makes the necessary 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 hel
ps the T to find it.

Advantages of this strategy are that the terminal is not a bottleneck
anymore, and the task of solving a problem is split over people who sp
ecialized in the different parts of the problem solving process. A dis
advantage is that no optimal use is made of the capacities of the T, w
ho is mainly a kind of secretary. If you only one of you is familiar w
ith the programming environment, this might be a good strategy. You ca
n write a lot of programs in the first part of the contest when your b
rain is still fresh, since the typing and debugging is done by someone
 else. It depends strongly on the composition of your team if this str
ategy is suitable for you.


3. Think Tank
The strategy we followed during the preparation and playing of the Con
test Finals of 1995 made use of the above-mentioned ``think tank'' (TT
). We felt that 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 analyzer
s form the TT and start reading the problems. Meanwhile the third memb
er, the ``programmer'', will type in some useful standard subroutines
and all the test data, which are checked carefully. After 15 minutes,
the TT discusses the problems briefly and picks the one most suitable
for the third team member. After explaining the key idea to the progra
mmer, they can start working on it. Then the TT discusses all problems
 thoroughly, and puts the main ideas of the algorithm down on paper. W
e found out that two people examining hard problems often lead to crea
tive solutions. After one hour the TT had a good overview over the pro
blem set, and all algorithms were found. The next decision is how many
 problems you want to solve. The easiest or shortest problems are hand
led by the programmer, while the TT divides the other ones among thems
elves.

The terminal is only used for typing in code from paper or gathering i
nformation from a buggy program. If a program is rejected by the jury
and no bug can be found, it is put aside until the last hour of the co
ntest. In principle, after three and a half hours no more new code is
typed. The team will briefly 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 tackl
e the programs which have a reasonable chance of being solved correctl
y, and the hard problems can be solved because the TT will start worki
ng on them in an early stage of the contest. A clear disadvantage is t
hat you will have a relatively slow start and your total time is not o
ptimal. So to win, you need to solve one problem more than the other t
eams. We feel that for a team consisting of partners with about equal
skills, this strategy will help you solve as many problems as possible
.


Some Other Tips
You can practice a lot for a programming contest, and your strategy ca
n be very good. However, luck always has its part in the contest and y
ou have to live with that. Do not be disturbed by it (or the lack of i
t). Play your own contest. Never look at other team's standing, except
 to see if some teams solved a problem rather quickly that you thought
 to be too hard. If a program gets rejected by the jury, don't panic.
Try to find the bug, there always is one. Consider especially the limi
ts of your program, and ask yourself under which circumstances these l
imits will be exceeded. You do not have to submit a correct program. I
t only has to produce the right output for the jury input. Therefore y
ou should program robustly and cleanly, and not write the shortest or
fastest code possible. And always remember: Programming contests are g
reat fun!


Concluding Remarks
In this article we have recorded some of our experiences with programm
ing contest strategies. Though these strategies are very dependent on
the individual qualities of the team members, the concepts apply equal
ly to all teams. We hope that the information contained in this articl
e will be useful to you, should you ever want to participate in the AC
M Programming Contest (we definitely recommend it!). More information
about the contest can be found on http://www.acm.org/~contest.A repor
t of our experiences at the Contest Finals, including more considerati
ons on team strategy, can be found at http://www.cs.vu.nl/~acmteam/.


About the authors:
Fabian Ernst is a 24-year old PhD-student at Delft University of Techn
ology, the Netherlands, in the field of Mathematical Physics, and also
 studies Administration Science in Delft. He competed once in the Cont
est Finals (for VU Amsterdam) in 1995. He can be reached at

ernst@math.tudelft.nl
Jeroen Moelands is a 22-year old computer science and business compute
r science student at Vrije Universiteit Amsterdam, the Netherlands. He
 competed in the Contest Finals both in 1994 and 1995. His email-addre
ss is:

jeroenm@cs.vu.nl
Seppo Pieterse is a 23-year old computer science and econometrics stud
ent at Vrije Universiteit Amsterdam, the Netherlands. He competed in t
he Contest Finals in 1994 and 1995, finishing 5th in 1994. He can be r
eached at

spieters@cs.vu.nl

--


※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.64.1]
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.39.3.80]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店