WHAT: The USA 2001 Computer Olympiad Fall Contest is a computer programming contest open to all pre-college students throughout the world. Several problems are presented for solution in each of two divisions. Results of this contest and other contests will be among the data used to choose delegates to the USA training camp and potentially to the IOI. Winners of both divisions will receive awards at the end of the season.

Solutions must be written in GNU C/C++ or FreePascal and must be returned via e-mail by the contest completion deadline. As soon as the grading machine receives your program, it will be compiled and run against a very simple test case. The results will be returned to you very quickly. This should enable you to fix incompatibilities, misspelled filenames, and the like. This means that the judges will rarely, if ever, make changes to your program during grading.

WHO: All pre-college students are eligible. This is an individual contest, not a team contest.

WHERE: Students can work on problem solutions anywhere they wish.

WHEN: Problems will be posted to the mailing list between during the morning US Mountain Standard Time (0730-0800 or so) on Wednesday, Nov 8. All results are due one week later, Nov.15, by 0800 am US Mountain Standard Time (1400 GMT). There is a five hour time limit and a three session limit for working on problems during the week.

PRIZES: Winners will receive a  certificate and have their names immortalized on the USACO Web Pages

FEES: No entry fees are charged.


  1. Consultation with people other than the contest director is prohibited.
  2. Do not work in a team environment.
  3. Submit questions (one per email, please) to <> who will try to fathom an appropriate answer for you (and post it to the hs-computing list, if appropriate). Many times, the reply will often be a suggestion to read the problem more carefully.
  4. Be sure to check your e-mail occasionally for contest updates, should there be any.
  5. Any amount of consultation with written materials (such as programming books) is allowed (this doesn't mean you can ask someone to write an article on how to solve a problem, of course). Do not ask someone where to look up an answer.
  6. Spend no more than three sessions solving problems (i.e., if you work one hour in a session, take a one hour break, and then work another hour, you have worked for two sessions).
  7. Spend no more than a total of five hours solving problems. Really.
  8. Submit source code for the problems to the contest coordinators via e-mail to <> (see below for format).
  9. An automatic grading system will check your solutions for correctness grader by running them against several (usually 5-15) different sets of input data. Points are accrued for correct solutions. Some datasets for a problem will be worth more points than others. Solutions to some problems will be worth more points. Judging will be performed expeditiously, hopefully far quicker than previously.
  10. Unless otherwise stated, your program must run no longer than
    5 seconds for any test case on the judge's computer (approximately 400 MHz Pentium II).
  11. Unless otherwise specified, it is NOT guaranteed that all possible legal datasets will be solvable within the time limit.
  12. The judges reserve the right to increase time limits during
  13. Decision of the judges is final.
  14. Do not cheat; it's no fun for anyone. Cheaters are often disqualified and banned.
  15. Do not use inline assembler statements.
  16. Do not submit programs that use data files that aren't supplied by the contest coordinators. Read only the specified input files and write only the specified output files.
  17. Do not submit programs you wrote in collaboration with others.
  18. Do not use `temporary' data files.
  19. Keep in mind that this is neither a `tricky input' nor a `tricky output' contest, in general. Input and output formats are straightforward, though the input values may cause your program difficulty.
  20. Problems are intended to be algorithmic in nature, thus clever algorithms and/or data structures might be necessary to solve all test cases correctly and within the time limits.
  21. All problem statements are intended to be straightforward (yet challenging); no problems are intended to have `hidden tricks' in them.
  22. Legal but complex datasets are fair game for testing.
  23. If you find a problem with poor wording or an ambiguity, document your assumptions carefully and move on. Send e-mail; we'll reply if we can.

  The registration information at the front of each solution should be in precisely the format as requested below.

  •  Be sure that each program you submit has identically the same registration information. Otherwise, you might be considered to be multiple contestants.
  •  Programs that consist of essentially nothing more than print statements will not be graded. Programs must compute the requested answers. Do not use precomputation to solve these problems.
  • The C/C++ compiler uses 32 bits for an int. Yay.
  • The grading program wants your program to compile both error- and warning-free. You must remove all errors and warnings for your program to be graded.
  • Submitters of programs that attempt to thwart grading procedures will be forever disqualified from USACO contests. Do not join this elite club!
  • Rob Kolstad <> is this contest's director, question-answerer, and grader.
  • All programs read their input from a file named in the problem statement (e.g., `'). Do not specify a complete path name in your `open' statement, just `'. Note that filenames are case-sensitive. If the problem says `' then you must use `' since `CoW.In' will not work.
  • All programs write their output to a file named in the problem statement (e.g., `cow.out'); do not specify a path name in your `open' statement, just `cow.out'. Like the input filenames, output filenames are case-sensitive.
  • Small amounts of output you write to stdout or stderr is ignored by the judging procedure. It is returned to you during the initial compile/test phase, though.
  • Note that test data run by the judges for grading will surely be more challenging than the example data supplied with each problem and, similarly, the data used to check that your program is submitted correctly.
  • The scorer will assess scoring penalties when certain rules are abused.
  • Your programs will be limited to 16MB of total memory use.
  • Note that all the examples are intended to be correct and helpful. If you find an apparent error, please contact <> so he can correct the problem. Some of the examples have only been double-checked, not triple-checked.
  • The scorer will compile your program with optimization turned on. For C/C++ programmers, the #pragma -fhandle-exceptions is handled correctly.
  • C programmers: #include if you use math functions
                             #include for srandom/random
                             #include for srandom/random
                             #include for srandom/random

              which are called like this:
                        srandom(seed);   /* use getpid() for a random seed */
                        randominteger = random();
              where the randominteger will be between 0..2^31-1.  Note that
              random()%N will be a random integer in the range 0..N-1.
  • No additional special registration form is required. Each problem solution has, within its submission, an entry form (see below). You enter when you send in your solution.


Submit your answers to problems via e-mail to <>. Please send precisely one problem's solution program per e-mail (i.e., send three separate e-mails for three problems, etc.). If you send in more than one solution for a single problem (e.g., on subsequent e-mails), only the last one RECEIVED by our automatic mail reader will be graded. That means if you find a bug after your submission, you can re-submit. There is no penalty for re-submitting -- in fact, you can use the technique to make sure our compiler likes your program(s) or even to run timing tests. Try not to submit more than 25 solutions per day.

Every e-mail is acknowledged almost instantly by an automated mail reader. If you do not receive an acknowledgment, double-check the e-mail destination address. Note that some networks connect to the Internet only occasionally.

Submissions must have special comments separating sections of the mail; you must insert the three `#'s and the word that follows them. Here is the exact format for submitting solutions so the grading programs can read them (be sure you note that those ### things are important -- they are actual text that belongs in your file!):


... [header comments -- see below for format] ...

... [text of program in C or Pascal] ...

### END

NOTES: * Put comments precisely like the ones below at the front of each and every solution (after the `### PROGRAM' marker).
* These messages are read by a program; do not change the forma.
* Do not add blanks or other characters to make the comments look nice. Use them just as they are shown.
* Be sure your email address and name are always spelled precisely the same way. We use the combination of email address and name as a unique identifier for you. Capitalization counts!
* Data after the `### END' line are ignored (e.g., signatures)
* All registration lines (below) are required; your program won't be graded until they are filled in.
* If you insist on using them, put compiler directives just before the header (as shown below) but nevertheless after the `### PROGRAM' marker. Choose your directives based on your own experience. Almost every program will run perfectly well with no other directives. Optimization is already set for -O2 for both compilers.


Here is the standard C/C++ header filled in for a youthful Rob Kolstad (my explanatory comments on far right -- do not include them). You should include a header with your own data for each problem (save it in a file on your computer for easy inclusion on subsequent submissions):


/* (This goes on a separate line)

Problem: 1 (problem number)
Name: Rob Kolstad (First name then last name)
Email: (Email address)
School: Norman High School
Grade: 2002 (Year you will graduate from high school)
Age: 17
CityState: Norman, OK (Non-USA people might not have a `State')
Country: USA (Three letters: CAN, COL, DEU, ROM, USA, etc.)

*/ (This goes on a separate line)


Here is the PASCAL header filled in for a youthful Rob Kolstad (my
comments on far right -- do not include them). You should include a
header with your own data for each problem (save it in a file on your
computer for easy inclusion on subsequent submissions):


{ (on a line by itself, please)
Problem: 1 (problem number)
Name: Rob Kolstad (first name then last name)
Email: (email address)
School: Norman High School
Grade: 2002 (year you will graduate from high school) Age: 17
CityState: Norman, OK (Non-USA people might not have a `State') Country: USA (three letters: CAN, COL, DEU, ROM, USA, etc.)


If you live somewhere that has a city but no state, please omit the state (for example, CityState: Amsterdam).

Watch your mailbox for a quick (automatically-generated) reply. If you don't see one fairly soon (i.e., 15 minutes) after sending in your solution, send another e-mail to <> explaining the situation (including which problem you submitted, when you sent it).

About mailers:

Many mailers wrap lines at around 70 or 80 characters. Even if your mailer doesn't, some mailer between yours and might. This usually doesn't cause problems except in a few cases. One is when a variable name gets chopped in half. For example,

... foobar[baz]

might become

... foo bar[baz]

which doesn't parse the same (if at all).

Another big problem with line wrap is C++ style // comments. Many people write comments that go off the end of the line boundary and are then "fixed" by mailers:

// this is a really long comment that got chopped into pieces

To fix problems like these, just avoid having lines in your program that are longer than about 70 characters. It will make things easier for you during the contest as well, since you'll actually be able to read your whole program.

A final note: the program that reads the incoming mail and grades the programs comprises 1,000 lines of brand new shiny code. Like fine wine, maybe a bit of maturity would help the code. If you see something going wrong, please let me know as soon as possible so that we minimize inconvenience for our competitors.