USACO Fall Championship
December 3-5, 1996
Introduction
WHAT: The USA Computer Olympiad Fall Championship is a computer programming
contest open to all pre-college students on the hs-computing@delos.com
mailing list. Four problems are presented for solution.
WHO: All pre-college students who are members of the hs-computing mailing
list are eligible. This is an individual contest, not a team contest.
WHEN: Problems will be posted between 0750 and 0800 a.m. US Mountain
Standard Time (1450-1500 GMT) on Tuesday, December 3, 1996. All
results are due by 0800 am US Mountain Standard Time (1500 GMT)
Thursday, December 5, 1996.
WHERE: Students can work on problem solutions anywhere they wish, including
school and home.
HOW: Problems will be posted to the hs-computing mailing list. Solutions
must be written in Borland C, C++, or Pascal and must be returned
via e-mail by the contest completion deadline along with answers to
test data supplied with the problems.
PRIZES: Winners will receive a handsome plaque, have their names immortalized
on the USACO Web Pages, and be the subject of a press release.
FEES: No entry fees are charged.
RULES: * No consultation with people is allowed.
* Any amount of consultation with written materials is allowed
(but this doesn't mean you can ask someone to write an article on
how to solve a problem, of course).
* Problems are intended to be solved in five hours
* Spend no more than eight hours solving problems
* Spend no more than two sessions solving problems (i.e., don't work
one hour in a session, take a one hour break, work another hour,
take another break...)
* Submit source code for the problems to the contest coordinators
via e-mail to fall96@delos.com (see below).
* Submit answers to supplied test data to the contest coordinators
via e-mail to fall96@delos.com (see below).
* Solutions will be judged for correctness by running them against
several (5-10) different datasets. Points are accrued for correct
solutions. Some datasets might be worth more points than other
solutions. Some problem solutions might be worth more points than
other solutions. Judging could easily take a week.
* Unless otherwise stated, no one solution can run longer than 15
seconds on the judge's computer (a medium speed Pentium).
* Judges will not test all datasets against a program that crashes
for easy datasets
* Judges will not test all datasets against a program whose author
submits erroneous solutions for the supplied test data.
* Make sure your program has any special compiler options
listed near its first line so our graders can get them right.
* Decision of the judges is final.
* Do not cheat; it's no fun for anyone.
* Do not use inline assembler statements.
* Do not use data files not supplied by the contest coordinators.
* Keep in mind that this is not a `tricky input' contest, in general.
* All problems are intended to be straightforward; no problems
are intended to have `tricks' in them.
* If you find a problem or ambiguity, document your assumptions
carefully and move on. Send e-mail; we'll reply if we can.
Rob Kolstad is this contest's director. During the contest, feel free to
send questions (one per e-mail please!) to him at kolstad@bsdi.com. He will
reply by e-mail when he is available. Questions judged to be germane to the
entire hs-computing list will be summarized and posted there, also. Be sure
to check your e-mail occasionally for contest updates, should there be any.
Thanks to Hal Burch for problem checking.
----------------------------------------------------------------------
No special registration form is required. Each problem solution has,
within it, an entry form to be completed (see below).
----------------------------------------------------------------------
Submit your answers to problems via e-mail to fall96@delos.com. Please send
precisely one problem's solution per e-mail (i.e., send four separate e-mails
if you solve all four problems). Submit only one solution per problem. If
you submit more than one solution, only the last one received will be graded.
Each solution should have the following in comments at the top of the program
(example for C shown here; PASCAL users use PASCAL-style comments):
/*
* PROBLEM NUMBER n
*
* compiler options
*
* Name:
* Email address:
* School:
* Grade in school:
* Age:
* Country:
*/
Then include the source program.
After the source program, include the answers you get when running the program
on the supplied test data sets. Please label each of the answer sets
very clearly!
If possible, just include all these pieces as text, no special MIME encoding
or other mail formats; it will save the graders a lot of time.
Watch your mailbox for a quick (automatically-generated) reply. If you don't
see one fairly soon, send another e-mail to kolstad@bsdi.com explaining the
situation (which problem you submitted, when you sent it).
Good luck!
Problems
PROBLEM 1: The Errant Physicist [New Zealand Contest, 1989]
The well-known physicist Alfred E Neuman is working on problems that involve
multiplying polynomials of x and y. For example, he may need to calculate
8 3 5 3
(-x y + 9x - 1 + y) * (x y + 1 + x )
yielding the answer
13 2 11 8 6 5 5 2 3 3
-x y - x y + 8x y + 9x - x y + x y + 8x + x y - 1 + y
Unfortunately, such problems are so trivial that the great man's mind keeps
drifting off the job, and he gets the wrong answers. As a consequence,
several nuclear warheads that he has designed have detonated prematurely,
wiping out five major cities and a couple of rain forests.
Write a program to perform such multiplications and save the world.
The file of input data will contain pairs of lines, none longer than 80
characters. Stop your program when no more input is available. Each input
line contains a polynomial written without spaces and without any explicit
exponentiation operator. Exponents are positive non-zero unsigned integers.
Coefficients are also integers, but may be negative. Both exponents and
coefficients are less than or equal to 100 in magnitude. Each term contains
at most one factor in x and one in y (i.e., at most one term of x to a power
and likewise for y). For example, an input file for the above problem might
be:
-x8y+9x3-1+y
x5y+1+x3
#
Your program must multiply each pair of polynomials in the input and print
each product on a pair of lines, the first line containing all the exponents,
suitably positioned with respect to the rest of the information, which is in
the line below. See the representation above.
The following rules control the output format:
* Terms in the output line must be sorted in decreasing order of powers of
x and, for a given power of x, in increasing order of powers of y.
* Factors of similar terms must be combined into a single term. For example,
2 3 2 3 2 3
42x y - 40x y should be shown as 2x y .
* Terms with a zero coefficient must not be displayed.
* Coefficients equal to 1 are not to printed, except for the case of a constant
term equal to 1.
* When the exponent is 1 (e.g., x to the first power), do not print
the exponent
* Binary pluses and minuses (that is the pluses and minuses connecting terms
in the output) have a single blank column both before and after.
* If the coefficient of the first output term is negative, it is preceded by
a unary minus in the first column, with no intervening blank column.
Otherwise, the coefficient itself begins in the first output column.
* The output can be assumed to fit into a single line of at most 80
characters in length.
* There are no blank lines printed between each pair of output lines.
* There are no blank space on the end of input lines
* There should be no blank spaces on the end of output lines.
The above example conforms to all those requirements.
Input file: INPUT.DAT
Example input file:
-x8y+9x3-1+y
x5y+1+x3
Output to screen: the product of the polynomials, as described above
Example output:
13 2 11 8 6 5 5 2 3 3
-x y - x y + 8x y + 9x - x y + x y + 8x + x y - 1 + y
Self Test Data #1:
-x8y+9x3-1+y
x5y+1+x3
x+y
x+y
45x4y3+-3x6
7y1++3y8-x+7x2
x+3x4--65x5
7y4-78y6+x3y3
x67y34+y67
x34+37y87x3+7
PROBLEM 2: Hamming Codes [Traditional, Kolstad]
Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length
B bits (1 <= B <= 8), such that each of the codewords is at least Hamming
distance of D (1 <= D <= 7) away from each of the other codewords. The
Hamming distance between a pair of codewords is the number of binary bits
that differ in their binary notation. Consider the two codewords 0x554 and
0x234 and their differences (0x554 means the hexadecimal number with hex
digits 5, 5, and 4):
0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
Bit differences: xxx xx
Since five bits were different, the Hamming distance is 5.
Input file: INPUT.DAT
Format: N, B, D on a single line
Example input file:
16 7 3
Output to screen: N c