The Regional Chief Judges are always happy to consider new contest problems for the ACM Mid-Central USA 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.

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. State any window dressing concisely.
   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.

Be careful if your problem requires case-insensitive string sorting. There are two reasonable ways to perform such a sort if the language does not provide case-insensitive comparisons (and not all do). One way is to sort based on the lowercased versions of each string, and the other is to sort based on the uppercased versions of each string. These two methods may give different results if the strings contain any of the characters ('[', '\', ']', '^', '_', '`'), whose ASCII codes are between those of the uppercase and lowercase letters. So either avoid those characters, or specify the exact sorting method to use.

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.

Writing "Portable" Problems

Teams may be using a different compiler and/or operating system than they're used to. To minimize potential errors, use the following guidelines.

1. Use only ASCII characters.
   In C/C++, characters are one byte long, can be signed (-128..127) or unsigned (0-255), and the character set is locale-dependent. Java uses Unicode and characters are two bytes long. Pascal characters are always unsigned. To avoid problems, only use printable ASCII characters in the range 32..126 (other than end-of-line character(s)).
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 use whitespace other than blanks.
   The only whitespace in input and output is blanks and newlines. The general rule is that only single blanks appear, and only after the beginning of a line and before the end of a line, and there are no blank lines. In some cases, for instance with output in columns, you may want to break this rule and allow multiple blanks and blanks at the beginning of some lines. In this case mention the rule change explicitly.
5. Don't require 32-bit unsigned integers.
   Java and Pascal only support signed 32-bit integers, i.e., they have no type analogous to C/C++'s unsigned long.
6. 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.
7. Make sure that all input lines have correct end-of-line character(s).
   This includes the last line of the file. In Windows lines in text files end with a CR/LF sequence (hex 0D/0A), in Unix they end with a single LF character, and in Mac OS they end with a single CR character.

Submitting a Problem

Before you start writing a problem, contact one of the Regional Chief Judges with your idea so that they can make sure it will blend well with the other problems. They will also arrange a way for you to send the problem securely. Never send an unencrypted problem via email!

A complete problem will include (1) the problem description in HTML, using our standard format (see the Contest Archives), (2) source code for a solution, written in C, 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.