USACO FALL 2001 PROGRAMMING CONTEST
*********************************** NEWS **********************************
For this contest, all contestants will use the web-based submission
The "window" for the contest has been reduced to four days. Few
used the other days.
Contestants should devote three hours in a row (no breaks) to the contest.
If you haven't read the rules below completely, you should! They
almost as brief as possible.
Don't read the problems (after the rules, below) until you are ready
start your three hour contest/coding time.
****************** SPECIFIC INFORMATION FOR THIS CONTEST ******************
NAME: USACO FALL 2001 Contest
DATES: 0800 MT Friday November 2 - 0800 MT Tuesday November 6, 2001
TIMELIMIT: Three hours in a row to solve all problems.
DIRECTOR: Rob Kolstad (<email@example.com>)
QUESTIONDUDE: Rob Kolstad (<firstname.lastname@example.org>)
GRADER: Rob Kolstad (<email@example.com>)
HOTLINE: In the USA and Canada,
call the USACO Contest Hotline at
+1 877-753-3567 toll-free with problems during the
contest (0700-2300 MST only, please). This service will
not be available during mid-day Friday.
RUNTIMELIMIT: 1.000 second max per test case (unless otherwise stated)
JUDGECOMP: 700 MHz Duron
COMPILERS: gcc version 2.96 20000731 (Red Hat
Free Pascal Compiler version 1.0.4 [2001/01/22] for i386
GRADING_OS: Linux version 2.2.16-22smp
PROCTORING: Not required for any division.
ASSISTANCE: Books, websites, old files, and any other
assistance is OK. Add an explanatory comment to any code
that is copied from a book.
DIVISIONS: Participants in this contest choose one of two divisions:
* A GREEN division for the experts and those vying for
participation at the USACO and IOI.
* An ORANGE division for our newer members who are still
working their way up to more difficult problems. You may
not enter the ORANGE division if you have completed
section 1.2 of the USACO training pages (the training
pages are found at http://train.usaco.org). The top few
placers in the ORANGE contest will be required to move up
in future contests to the GREEN division.
Choose your division by submitting solutions for that
division. Do a good job picking your division. Challenge
yourself! You might be disqualified if you enter both
**************** GENERAL INFORMATION FOR ALL USACO CONTESTS ***************
WHAT: This USA Computer Olympiad 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 USA delegates to the USA training
camp and potentially to the IOI. Winners in each division will
WHO: All pre-college students are eligible.
This is an individual
contest, not a team contest. Visitors/observers/"for fun" entries
will be scored and reported separately.
WHEN: See the schedule above for the contest dates.
All work must
be performed in a single session.
WHERE: For non-proctored contests: Students can work on
solutions anywhere they wish. Proctored contests require
supervision by the proctor, of course.
HOW: Solutions must be written in GNU C, GNU C++,
or FreePascal and
must be returned submitted web before the contest completion
deadline. As soon as the grading machine receives your program,
it will compile the program and run it against a small number of
very simple test cases. 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.
Be sure to send in questions if you think the compilers are
PRIZES: Each winner will receive a handsome certificate and be immortalized
on the USACO Web Pages.
FEES: No entry fees are charged.
RULES: Consultation with people other than the contest director
Work by yourself, not in a team environment.
Submit questions (one question
per email, please) to the
QUESTIONDUDE (see above) who will try to fathom an appropriate
answer for you (and post it to the hs-computing or the web page
message-of-the-day if required).
Unless otherwise stated,
your program must run no longer than the
default time limit for any test case on the judge's computer.
Unless otherwise specified,
it is NOT guaranteed that all possible
legal datasets will be solvable within the time limit.
The judges reserve the right
to increase time limits during
Decision of the judges is final.
Do not cheat; it's no fun
for anyone. Cheaters are often
disqualified and banned.
Do not use inline assembler statements.
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.
Do not use `temporary' data files.
Do not submit programs you
wrote in the past in collaboration with
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
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.
All problem statements are
intended to be straightforward (yet
challenging); no problems are intended to have `hidden tricks' in
the problem statement.
Legal but complex datasets are fair game for testing.
If you find a problem has
poor wording or an ambiguity, document
your assumptions carefully and move on. Send e-mail; we'll reply
if we can.
NOTES: Submit your solutions via the web at the address listed
Register for the contest at the website, as well. If you have ever
registered before, your registration should still be valid. You
can ask the web site to send you your old id and password.
The registration information
at the front of each solution should
be in precisely the format as requested below.
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.
Make sure you exit (0); when your program has
The grading program wants
your program to compile error-free. You
must remove all errors for your program to be graded. You do not
need to remove all compiler warnings.
Submitters of programs that
attempt to thwart grading procedures
will be forever disqualified from USACO contests. Do not join this
All programs read their input
from a file named in the problem
statement (e.g., `cow.in'). Do not specify a complete path name
in your `open' statement, just `cow.in'. Note that filenames are
case-sensitive. If the problem says `cow.in' then you must use
`cow.in' since `CoW.In' and '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.
Virtually every program's
output is in the form of "lines". A line
ends with newline character ('\n' in C; use writeln in pascal).
If your output does not contain a newline at the end of every line,
it will be graded as incorrect.
Small amounts of output you
write to stdout or stderr are ignored
by the judging procedure. They are returned to you during the
initial compile/test phase, though, if errors occur.
Note that test data run by
the judges for grading will surely be
more challenging than both the example data supplied with each
problem and the data used to check that your program is submitted
The scorer will assess scoring
penalties when certain rules are
Your programs will be limited
to 16MB of total memory use: 15MB
of global data plus 1MB of stack space. That means you can't put
really large data structures on the stack, which is where all local
variables are allocated.
Note that all the examples
are intended to be correct and helpful.
If you find an apparent error, please contact the `QUESTIONDUDE'
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
C programmers: #include <math.h>
if you use math functions
#include <stdlib.h> for srandom/random
#include <sys/types.h> for srandom/random
#include <unistd.h> 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.
there is no way to find out the program's
ongoing execution time for this contest. Happily, you won't
If, over time, you submit
more than one solution for a single
problem, only the last one submitted 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 this
way so the server is available to everyone.
Every submission is acknowledged
almost instantly by an automated
************************* NOTES ON WEB SUBMISSION *************************
Add identification lines to beginning of your program's source file
the explanations shown on the right in parentheses):
For C, C++:
PROG: cowfun (whatever the problem name is)
LANG: C++ (Choose one: C, C++)
Don't use //-style comments in C++ for these headers; they won't work.
PROG: cowfun (whatever the problem name is)
Then, type the filename into the obvious browser form and click "Send
In". Your results will be displayed shortly thereafter.
You can submit solutions before the contest in order to ensure that
mechanisms work. The program name is `test' and the files are `test.in'
and `test.out'. The input file contains two integers on a single line.
Sum them and print them to a single line in `test.out'.