2002 ACM Programming Contest
Mid-Central Region
Call for Problems

We are now accepting contest problems for the 2002 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.

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.

1. All teams can solve at least one problem, but few teams can solve them all.
2. All problem specifications are clear and unambiguous.
3. All problems can be graded quickly by machine.
4. 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.

1. 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?
2. 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.
3. 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.)
4. 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.
5. 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,

1. output must be unique, so that it can be compared to the correct output using a file-comparison utility,
2. programs must not require excessive amounts of time, and
3. 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.

1. 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).
2. 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.
3. 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.
4. 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).
5. 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.
6. 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.
7. 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.
8. 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.)
9. 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.