荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: selahx (宿醉未散，早梦半醒), 信区: ACMICPC
标 题: Guidelines for Producing a Programming-Contest
发信站: 荔园晨风BBS站 (2005年04月23日12:42:45 星期六), 站内信件
Guidelines for Producing a Programming-Contest Problem Set
Tom Verhoeff
Faculty of Mathematics and Computing Science
Eindhoven University of Technology
P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands
E-mail: Tom.Verhoeff@acm.org
October 1988, Revised and expanded July 1990
Abstract
In this note we give some guidelines to produce a problem set for ``AC
M-style'' programming contests, in particular for the European Regiona
l Programming Contest. The reader is assumed to be familiar with the o
peration of such programming contests. Where possible, we also explain
the motivation behind the guidelines.
The first two sections deal with aspects related to the problem set as
a whole, viz. requirements and production schedule. They are especial
ly intended for the Head Judge. The remaining sections cover the follo
wing aspects concerning individual problems in the problem set: select
ion, specification, solution, and testing. These sections are more dir
ected towards the Problem Creators.
------------------------------------------------------------------------------
--
A good problem set is the key to a successful programming contest. The
production of such a problem set should be taken very seriously and r
equires a major effort by a number of people. The guidelines presented
in this note should enable you to do a good and enjoyable job.
Problem set requirements
The Head Judge is responsible for the timely production of a suitable
problem set. In the contest, each team should be provided with two (2)
copies of the problem set.
The problem set consists of at least six (6) problems. There should be
sufficient variation in both the difficulty and the computational asp
ects of the problems. Two (2) easy problems and one (1) more difficult
problem should be included. All problems should be original in some r
espect. For example, a problem can be new as such, or its embedding in
to a context can be new, or its boundary conditions can be new.
The reason for having at least six problems is that we prefer to measu
re the strength of teams by number of problems solved and not by amoun
t of time spent on solving them. (Recall that ranking is done first on
account of number of problems solved and, in case of a tie, on accoun
t of time spent.) To provide sufficient resolution, the problem set sh
ould be so large that the strongest team can solve (almost) all proble
ms just in time. Of course, the number of competing teams, the difficu
lty of the problems, and the duration of the contest are also importan
t factors. At the Finals (a six-hour contest with 24 teams; five hours
since 1990, and over 50 teams in 1998.) typically eight problems were
posed with satisfactory results. The reasons to include at least two
easy problems are the following.
Easy problems can serve as starters and allow early usage of the PC (t
his requires that the teams make the right judgment about difficulty;
hence, assessment of problem difficulty is an important aspect of the
contest).
Weak teams should have some fun too; therefore, they should be enabled
to solve---not just work on---some problems.
Strong teams should be able to solve easy problems quickly (say, in ha
lf an hour), which acts as an incentive for themselves and others (inc
luding judges etc.).
Teams solving no problems cannot be differentiated in the final rankin
g, whereas teams that solved at least one problem can be ranked accord
ing to time spent.
The presence of one or two more difficult problems serves to different
iate the strongest teams on account of the number of problems solved a
nd not just on account of time spent. Furthermore, difficult problems
make the contest more interesting: we would not want the contest to de
grade to mere implementation jobs.
We know from experience that it is unlikely that an interesting proble
m is too easy. (Keep in mind that teams usually read all problems firs
t and need to decide on an appropriate order to solve them, before the
y start programming. Hence, it unlikely that a problem is solved withi
n 15 minutes.) Moreover a problem can readily be made more difficult;
making it easier is often painful. Also note that it hardly makes sens
e to include problems that are too difficult. The only thing that the
presence of a too difficult problem can measure is the ability of the
teams to recognize and then ignore the problem. This is not worthwhile
the trouble of including such a problem.
The reason to cover various computational aspects are the following.
If one aspect (say, juggling with dates or numerical approximation) ap
pears in many of the problems, then ``specialists'' in that field have
an advantage.
Variation allows teams to work on those types of problem they like mos
t (only strong teams will have little choice: they should solve all pr
oblems). On the other hand, a nice thing about two problems with a com
mon aspect is that a team recognizing this fact may benefit by writing
a combined solution.
The reasons for having original problems are
to make the contest interesting for the contestants and the organizers,
to avoid giving unfair advantage to teams familiar with particular pro
blems, and
to attract some attention from the Computing Science community.
Each problem must have a short and unambiguous identifier, for instanc
e, a letter. This identifier will also be used on the Run Envelopes, C
larification Requests, and Standings. The cover page of the problem se
t mentions the date, the number of problems, their identifiers, and th
e number of pages. For example,
This is the problem set for the
1990--91 European Regional Programming Contest
held on Saturday November 3, 1990.
It contains 7 problems labeled A through G
printed on 10 numbered pages.
Production schedule
The following phases can be distinguished in the production of a problem set.
Generate ideas for problems, making explicit what the crucial computat
ional aspect is of each problem.
Select initial set, taking into account the need for originality and v
ariation in difficulty and computational aspects, and eliminating too
difficult problems.
Specify problems in detail.
Write complete programs for problems (including alternative solutions
where necessary).
Write input validator and output verifier.
Produce test input data files (and test output data files where necessary).
Validate examples, validate test data, check spelling.
Print a sufficient number of copies of the problem set.
Each phase should take no more than one week to complete. We suggest t
hat you have a review meeting at the end of each phase.
The Head Judge needs to take into account that only afterwards a probl
em may turn out to be unsuitable. Initially, aim at eight or even nine
problems. In the 1989--90 European Regional we posed all nine problem
s that we had prepared (none had to be abandoned) and, contrary to our
expectations, one team was able to solve all nine of them!
See to it that for each problem there is one person taking full respon
sibility for all aspects (this would usually include judging as well).
Of course, it is also a good idea to have Problem Creators read each
other's specifications and possibly even attempt solutions.
Problem selection
Here are some facts to keep in mind when creating a problem.
Each team consists of up to four (4) programmers (usually computing sc
ience students at undergraduate or graduate level). They have one (1)
personal computer with Turbo Pascal 5.5 at their disposal and they may
consult non-computer-readable literature and non-programmable calcula
tors. The contest lasts six (6) hours. However, for the Finals that wi
ll now be five hours. By the way, they reduced the length of the Final
s so that
there would be more excitement at the end of the contest.
it would be less likely that the winners be known prior to the Banquet.
teams not making much progress would feel less frustrated.
judges would not feel compelled to increase the number of problems (co
mpensating for the increased power of modern software development envi
ronments).
judges would be less tired and less likely to err.
five hours fits nicely between 1pm and 6pm.
Judging is done by running the submitted program for some test cases a
nd subsequently checking its output. A program is either accepted or r
ejected. In the latter case, the team is given a 20 minutes' penalty f
or the problem and one of the following reasons for rejection is indic
ated:
Syntax Error
Run-Time Error
Time-Limit Exceeded
Wrong Answer
Failed Test Case
Inaccurate Answer
Too Little/Much Output
Bad Output Format
Check Clarifications
The run-time limit is three (3) minutes unless otherwise indicated in
the problem specification. There is still some controversy over these
messages. We will come back to them in the section on testing.
A problem may be interesting for several reasons. Important aspects can be
clever algorithm
efficiency (time and/or space)
preprocessing
complicated case analysis
irregularities
internal data representation
input parsing
output format
tricky issues (going beyond maxint, end-of-file detection)
common subproblems
Problem specification
Problems will be posed in English. Each problem prescribes the names o
f the program source file and the data input and output files. Since j
udges recompile the program there is no need to mention the name of an
executable file. A problem may require more than one input and/or out
put file. An execution time-limit is mentioned if it deviates from the
standard amount (see above).
The problem specification will usually start with a story and the intr
oduction of some concepts, possibly accompanied by instructive example
s. This is followed by a short informal description of the programming
task and then a more precise specification of input and output format
and their desired relation. Finally, an example input set with corres
ponding output is given.
Of course, the aim is to specify a problem completely and unambiguousl
y. Although teams may make clarification requests, it is better to obv
iate these by a careful problem specification. Keep in mind that Engli
sh is a second language for most of the teams. Also keep in mind that
long specifications tend to be more controversial than concise ones.
The following example was adapted from the 1989--90 Finals held in Was
hington D.C., USA.
Problem A Rare Order
Source ORDER.PAS
Input ORDER.DAT
Output ORDER.OUT
A rare book collector recently discovered a book written in an unfamil
iar language that used the same characters as the English language. Th
e book contained a short index, but the ordering of the items in the i
ndex was different from what one would expect if the characters were o
rdered the same way as in the English alphabet. The collector tried to
use the index to determine the ordering of characters (i.e., the coll
ating sequence) of the strange alphabet, then gave up with frustration
at the tedium of the task. You are to write a program to complete the
collector's work. In particular, your program will take a set of stri
ngs that has been sorted according to a particular collating sequence
and determine what that sequence is.
Input The input consists of an ordered list of strings of uppercase le
tters, one string per line. Each string contains at most 20 characters
. The end of the list is signalled by a line that is the single charac
ter '#'. Not all letters are necessarily used, but the list will imply
a complete ordering among those letters that are used. A sample input
file is shown below.
XWY
ZX
ZXY
ZXW
YWWX
#
Output Your output should be a single line containing uppercase letter
s in the order that specifies the collating sequence used to produce t
he input data file. Correct output for the input data file above is sh
own below.
XZYW
End of Problem A
This is a nice and inviting problem with a concise specification. Howe
ver, it might not be completely clear to the contestants whether the i
nput file may contain empty strings (at the very beginning only, since
it is sorted) and whether the file may consist of the end-of-list mar
ker '#' only. As a Problem Creator you should be aware of these extrem
es.
The Problem Creator should summarize the crucial computational aspects
of the problem for the Head Judge. In this summary, tricky issues, bo
undary cases, and required efficiency considerations may be mentioned.
Of course, the summary should not be revealed to the contestants unti
l after the contest. For the above sample problem the following summar
y might be produced.
Problem A (Rare Order): Summary of computational aspects.
Let R be the total order induced by the collating sequence that was us
ed to sort the input file. It is R that has to be reconstructed from t
he input.
Algorithm For two strings s and t, the following holds: either (a) one
string is a prefix of the other, or (b) for some index k we have s[i]
=t[i] for all i<k and s[k] <> t[k]. Which of (a) or (b) holds and, if
(b) holds, what the index k is, can be determined independent of R. Th
e required procedure is a variant to determining the lexicographic ord
er of two strings.
Therefore, each pair of strings s and t, where s precedes t in the inp
ut file and s is not a prefix of t, contributes to our knowledge about
R, viz. s[k] R t[k] (because precedence in the input file is based on
the lexicographic order). One needs to consider only neighboring stri
ngs in the input file, since other pairs will not provide new informat
ion about R.
The input can be scanned once sequentially to collect all information
about R, for example, in a NxN-matrix, where N is the number of letter
s in the alphabet (N=26 always works). For the sample input provided i
n the specification this matrix might look like
R W X Y Z
W
X 1
Y 3
Z 4
where the number n at entry (a,b) indicates that a R b holds on accoun
t of input lines n and n+1. This matrix must completely determine R (a
s promised in the specification). The collating sequence can now be ex
tracted in several ways (e.g. repeatedly find minimal element and remo
ve it; the example matrix above is atypical in that each column has at
most one non-blank entry). Of course, one should consider only letter
s that occur in the input. Keeping track of some additional informatio
n (e.g. the number of non-blank entries per column) may speed things u
p.
Special cases Duplicate strings and empty strings may be present in th
e input file. Their presence may slightly complicate the determination
of index k mentioned above, but otherwise has no consequences. The in
put file may consists of the `end-of-list' marker only, in which case
the output should be an empty collating sequence.
Input and output format are straightforward. No special efficiency con
siderations are required (other than noticing that to try out all coll
ating sequences is hopelessly inefficient).
Problem solution
Once a problem has been specified it is necessary to obtain a better e
stimate of its suitability for the contest. This can be done by writin
g a complete program for the problem. That way one may encounter some
trouble spots that otherwise would remain unnoticed.
It should take the Problem Creator, who is intimately familiar with th
e problem after specifying it, no more than a couple of hours to imple
ment a working solution. That solution should be more or less along th
e lines of an ``intended'' solution and should not make use of impleme
ntation specific extensions to Pascal. It is not necessary to come up
with a very neat and fully annotated solution (in case you still think
that would be a waste of time). From this solution one can also deter
mine some limits on run-time and memory utilization, which are useful
when putting together test cases (discussed in the next section).
If it is the intention to rule out some straightforward solutions on a
ccount of their inefficiency (e.g. O(N3) instead of O(N)), then it is
necessary to implement ``unintended'' alternative solutions as well. T
he alternative solutions must fail the tests (see below) even if they
were otherwise cleverly coded, possibly using some implementation spec
ific extensions to Pascal! You may sometimes be surprised how ``good''
unintended solutions turn out to be.
Apart from the bare ``intended'' solution it is also necessary to writ
e another program. Input validation is not part of the contestants' pr
ogramming task. That is, teams may assume that input supplied to their
programs is in agreement with the specification. The Problem Creator,
however, has to see to it that examples and test input data are valid
. It is strongly recommended that input validation is done by a progra
m. The input validator may be implemented as a separate program or may
be incorporated in an ``embellished'' solution. N.B. The embellished
solution need no longer be suitable for run-time and memory utilizatio
n assessment, so keep a copy of the original ``bare'' solution!
For Problem A (Rare Order) above, the input validator must check that
each line but the last contains a string of at most 20 upper case lett
ers and that the last line consists of a single '#'. Moreover it must
determine that the input file is sorted according to a unique collatin
g sequence. That is, leaving out the first string XWY should be detect
ed as invalid (collating sequence not unique), as is the insertion of
ZXZ after the first string (input not sorted). For Problem A it is con
venient to incorporate the input validator in a solution.
Testing
Although we are interested in formally correct programs for the proble
ms, judgment is based on testing. Hence, testability is an important i
ssue.
If there is not much variety in the required output of a problem (e.g.
only yes/no), then a program might ``unrightfully'' be accepted when
it correctly ``guesses'' the output. Try to avoid this.
The test cases that are applied to exercise a program must allow a goo
d assessment of the program's correctness. It may therefore be necessa
ry to run more than one test case. Often it is convenient to specify t
he problem such that one input file actually allows a sequence of test
s to be applied (this is not the case for Problem A above). Don't forg
et, however, that an execution time-limit must be set for the entire r
un (default unless otherwise stated).
Include both ``normal'' and special (boundary) cases in the test data.
Determine the typical run-time of each test and mention it in your re
port to the Head Judge. For Problem A above, one would include the fol
lowing input files among the tests: containing no strings (i.e., only
the end-of-list marker '#'); in which all letters are the same; in whi
ch all 26 upper case letters appear; in which duplicate strings appear
; in which strings that are prefixes of other strings appear; in which
the directly deducible ordering relation is not a linear graph (e.g.,
by prepending the string XZ to the sample input: this directly implie
s the ordering Z R W, which is also obtained by transitivity from the
other strings); containing strings of minimal and/or maximal length, d
iffering only in certain positions; where both X R Z and Y R Z can be
deduced before X and Y can be ordered; etc.
In order to generate test cases it is desirable to have a programmed s
olution for your problem. In order to judge a program it is convenient
to have an output verification program. This verifier takes the outpu
t of the submitted program and checks it, e.g., against the output of
a known correct program or/and with the aid of the input file. It may
be convenient to specify the problem such that each input file produce
s a unique output file, in which case the evaluator can simply compare
two files character by character (this is the case for Problem A abov
e). Note, however, that in this case the output must be completely spe
cified, taking into account such oddities as trailing blanks, leading
zeroes, empty lines, etc. ``Normalization'' of output text files befor
e doing the output verification partly solves this problem (also see m
y note Additional Contest Information).
Of course, a simple file comparator cannot distinguish between such er
rors as Wrong Answer and Bad Output Format (but for the time being we
do not mind). Currently, the error messages issued by the judges in th
e Finals when they reject a program are not sufficiently well-defined
to be useful for automated judging. In particular, the messages Failed
Test Case, Inaccurate Answer, Too Little/Much Output, Bad Output Form
at, and Check Clarifications are controversial. My suggestion is to ig
nore these possibilities. The teams will be told that these messages w
ill not be issued. Hence, Wrong Answer covers any error not covered by
Syntax Error, Run-Time Error, and Time-Limit Exceeded.
To get a good insight into the severity of the test cases it may be ne
cessary to write yet another program that collects some statistics (to
determine which situations occur how often). [Good example to be prov
ided.] Like the input validator, this program could be a separate prog
ram or it could be incorporated in an ``embellished'' solution. It is
sometimes also advisable to write a program that generates (possibly r
andom) test cases with certain predetermined characteristics.
Summary
Aim at eight or nine original problems. Include two easy problems and
one or two more difficult problems. Avoid too difficult problems. Cove
r various computational aspects. The best team should be able to solve
(almost) all problems in the available time.
Each problem should fall under the responsibility of one person. For e
ach problem the Head Judge needs to receive the following items from i
ts Problem Creator:
a specification,
a short description of the crucial computational aspects,
a programmed solution (possibly also alternative solutions),
an input validation program,
an output verification program (the verifier could be a simple file co
mparator for deterministic problems, in which case a test output data
file must be provided), and
a set of test input data files (preferably just one), including their
typical run-time and some motivation for their discriminating power.
Items 1 and 2 are discussed in the section on Problem Specification, i
tems 3 and 4 in section Problem Solution, items 5 and 6 in section Tes
ting.
It would be nice if the Head Judge prepares solution suggestions to ha
nd out after the contest. These could, for instance, be based on the `
`description of crucial computational aspects'' as provided by the Pro
blem Creators.
In case you want to organize contests more often, it is advisable to d
o an evaluation afterwards, in which you attempt to find out how well
the objectives have been met. For instance, how difficult did the prob
lems turn out to be, how many and which Clarification Requests were ma
de, how well were the test cases, were any programs accepted unrightfu
lly, were there any programs that got rejected because they failed on
a single test case only, etc.
--
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 210.39.3.80]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店