2001 ACM Programming Contest
Mid-Central Region
Call for Problems
We are now accepting contest problems for the 2001 ACM Mid-Central
Regional Programming Contest. If you have a good problem fermenting in
your brain, or you have been dissatisfied with the problems in previous
contests, now is your chance! Using problems from different authors
keeps our problem set fresh and interesting for the teams. Our biggest
need is for easy problems. Instructions for submitting a problem are at
the end of this page. Please read this announcement completely before
you submit a problem.
Note!
We cannot accept a problem unless you will be available (by phone, fax, or
email) to answer questions about your problem during the contest.
(Just in case a problem arises.) If you are the sponsor for your
programming teams, then you will be present at a local site during the
contest and will automatically be available.
The regional programming contest has two primary goals: to select the two
strongest teams to represent our region in the international finals, and
to provide a valuable educational experience for all teams. To ensure
that these primary goals are met, we have the following requirements.
- All teams can solve at least one problem, but few teams can solve them all.
- All problem specifications are clear and unambiguous.
- All problems can be graded quickly by machine.
- No problems favor the use of one programming language over another.
The rest of this announcement provides some guidelines for meeting
these requirements.
1. Writing Solvable Problems
Several years ago, all the problems were generally hard. Many teams
failed to solve even one and no teams solved them all. Our goal is to
have a mix of easy and hard problems, but none that are impossible.
We don't have an exact definition of a solvable problem, but here
are two useful guidelines. First, try to fit the problem description
(including sample input and output) on a single page. Second, make sure
that there is only one nontrivial problem to solve; eliminate
all other details. For example, if you write a maze-search problem,
then you're testing a team's ability to implement a search algorithm.
That's the essence of the problem. If, in addition, you require elaborate
input and output formats, then you're also testing a team's ability to
parse complex input and generate complex output. In effect, you're
writing three problems. Decide what the essence of the problem is,
and simplify the remaining details as much as possible.
2. Writing Clear and Unambiguous Problems
Problems must be clear, concise, and unambiguous. We will not
accept ambiguous problems. All necessary information must either be stated
explicitly in the problem, or must be inferrable from what is
stated.
Here are some things to keep in mind.
- Define limits.
How big can the maze be? Are negative numbers allowed? What
happens when the string is empty? How large can the result of that
calculation be? Are characters case-sensitive?
- Don't write 'one-shot' problems.
The 1992 contest included a problem called Puttin' on the Hex that
defined a large hexagonal maze and required teams to write a
program to find a path through the maze. There was no input (teams
had to hard-code the maze in their program) and there was only a single
output. Problems like this make it tempting for teams to try to solve
the problem by hand and then simply write a program that outputs the answer
without performing any computations. Even if the problem seems too
difficult to solve by hand, some team might get lucky. We want to avoid
this situation, so in general we will not accept such problems.
- If the obvious solution won't work, say so.
A classic problem is coin changing, in which you are supposed to
calculate the fewest number of coins necessary to make a certain amount
of change. For example, the minimum number of U.S. coins needed to make
87 cents is 6 (3 quarters, 1 dime, and 2 pennies). It's easy to
calculate this using a greedy strategy; use as many quarters as
possible, then as many dimes as possible, then as many nickels as
possible, and then as many pennies as possible. The trick is that the
value of the coins is part of the input. If quarters are worth
23 cents, dimes are worth 11 cents, nickels are worth 4 cents, and
pennies are worth 1 cent, then the greedy strategy will not work; it will
use 5 coins to make 33 cents (23+4+4+1+1), but the actual minimum needed
is 3 coins (11+11+11). One of us has used this problem in practice sessions, and most
students fail to realize that the greedy strategy won't work in general.
Moral: if you write a seemingly simple problem in which
the obvious strategy will not work, say so, and provide sample
input and output to illustrate it. (Of course, you shouldn't give them
the correct strategy.)
- If the obvious solution is too slow, say so.
One of us once wrote a problem that, given n, required students to find all
integers x and y such that (1) x - y = n, and (2)
x and y together used all ten digits once each. An efficient
solution must use the magnitude of n to constrain x
and y. For example, if n < 1000 then x and
y must both be 5-digit numbers whose first digits differ by 1.
Some students tried to solve this problem by brute force, in effect
trying all possible values of x (from 0 to 987654321). This
example is extreme, but there are many problems that have simple but
wildly inefficient solutions. If yours is one of them, explicitly state
that the obvious brute-force solution is too slow.
- Don't provide irrelevant information.
It is traditional to 'dress up' a problem to make it interesting, and we
heartily approve of this. We don't want all the problems to sound like
exercises from a data structures textbook. While you have unlimited
artistic license, don't let problem descriptions drag on too long, and
don't provide irrelevant facts if they may mislead a team.
3. Writing Machine-Gradable Problems
To ensure that programs can be graded
quickly and accurately, all problems must be machine gradable.
Specifically,
- output must be unique, so that it can be compared to the correct
output using a file-comparison utility,
- programs must not require excessive amounts of time, and
- programs must be gradable using a single input file.
To ensure that output is unique, you must pay
particular attention to spacing, spelling, punctuation, and format of
floating-point output. For some problems you may need to require that
output be sorted in some fashion. If you require output in the form of
sentences, pay attention to plurals: will you require Barney needs 4
bandersnatches but Barney needs 1 bandersnatch, or
will you use a neutral Barney needs 1 bandersnatch(es)?
In general, select output formats that make
life easy for the programmer. Avoid elaborate tabular formats that
require programmers to count spaces.
Ensure that correct programs require less than 1 minute to process all
of the judge's input data.
Problems should be designed to work with a single input file that
may contain any number of test cases. We will not accept problems that
require each test case to be in a separate file.
4. Writing Language-Independent Problems
Teams can use C, C++, Java, or Turbo Pascal, and these languages
have different strengths and weaknesses. Use the following guidelines
to ensure that you don't inadvertently write problems that provide a
significant advantage for one language over the other.
- Use only ASCII characters.
In C/C++, characters can be signed (-128..127) or unsigned (0-255). Turbo
Pascal characters are always unsigned. To avoid problems, only use printable
ASCII characters in the range 32..126 (other than the CR/LF at the end of
each line, of course).
- Use simple formatting.
C and C++ support fairly sophisticated features for formatted I/O. (C has
printf/scanf and C++ has the iostream library.) Java and Pascal are
more limited; you can specify a field width, left or right justification,
and a precision for floating-point output (but no scientific notation),
and that's about it.
- Use sentinels to signal the end of the input
End-of-file handling differs between languages and sometimes between
different compilers for the same language. It can cause problems for teams
using tools that they're not used to.
- Don't require strings longer than 255 characters.
Turbo Pascal strings have a maximum length of 255 characters. This
limit also applies to lines in input files (not including the CR/LF
end-of-line marker).
- Don't use whitespace other than blanks.
Since the 1997 contest, the only whitespace that appeared in either
input or output was single blanks within a line. (No blanks appeared
at the beginning or end of lines, and there were never two consecutive
blanks.) We strongly prefer that you adhere to this convention.
- Don't use 32-bit unsigned integers
Java and Turbo Pascal only support signed 32-bit integers, i.e.,
they have no type analogous to C's unsigned long.
- Don't use NaNs and infinities.
The floating-point units in modern processors support NaNs (Not-a-Number) and
infinities. These are wonderful but are only directly supported by Java.
(Support for the other languages is compiler-dependent.)
Don't use them.
- Don't require data structures larger than 64K.
Using the standard memory models, DOS C/C++ and Turbo Pascal compilers
do not allow more than 64K of global static data, and do not allow a
single object larger than 64K to be allocated from the heap.
(Technically, the limit is 64K-16 = 65520 bytes.)
- Make sure that all input lines end with CR/LF.
In MS-DOS, lines in text files end with a CR/LF sequence (hex 0D/0A).
This includes the last line of the file. Many years ago, text files also
had a Ctrl-Z character to mark the end of the file, but this convention
is no longer used. Normally issues like these are transparent to the
programmer, but a few years ago during the regional contest one line in
an input file was missing the CR from the CR/LF sequence. C/C++
programs still worked OK, but Pascal programs treated it as end-of-file
and didn't process all the test cases. Be careful if you prepare a
problem on a UNIX system, because UNIX uses LF instead of CR/LF as the
end-of-line marker.
Submitting a Problem
Before you start working on a problem, call one of us with your idea
so that we can make sure it will blend well with the other problems.
We will also arrange a way for you to send the problem securely.
Never send an unencrypted problem via email!
When you submit a problem, we will need: (1) the problem description
(which must include sample input and output), (2) source code for a
solution, written in any language supported by the contest but preferably
C++ or Java, and (3) the input file to be used for judging. We will
use your program to generate the correct output to be used for judging.
Addresses
Feel free to contact any of the Regional Chief Judges listed below.
John Cigas (Editor)
Rockhurst University
816-501-4534
Andy Harrington (Toolsmith)
Loyola University Chicago
773-508-3569
Eric Shade (Webmaster)
Southwest Missouri State University
417-836-4944