1996 ACM Mid-Atlantic Programming Contest Problems
1996 ACM
Mid-Atlantic
Programming Contest Problems
Welcome
Hi. I created this page as a service to the contestants and to
others interested
in the programming contest. I hope "going public" with this information
does not result in arguments about problem interpretations and requests
to reconsider problem solutions. Please
remember that the contest is over and the results are final.
For each problem I'm including a short note, a link to a text based
description of the problem similar to that distributed during the
contest (minus figures and cartoons), a link to a description of the
test input used during the contest and the expected output, and a link
to a Java based solution to the problem (an application, not an applet).
The problems were originally written using WordPerfect. The versions
included here are text files, so some information (graphics, special
symbols, cartoons) has been lost.
I used Java to
solve the problems because I am teaching myself that language and
wanted some problems to practice on. Since I am a Java novice I
expect that some of the solutions are neither elegant nor efficient.
Additionally, the programs are not commented satisfactorily since
I was just writing them as a learning exercise.
Since performing input in the Java base language can be tedious I
created a package called common (since it would hold code common
to all my problem solutions) into which I placed two functions,
nextint() and nextsubstring() that simplify input. They use the
stringTokenizer Library package. To use them, the file
doinput.java and its associated class file should be placed in
a subdirectory "common" of the directory holding the problem solution
files.
The Problems
There were eight problems in the contest. There were 97 teams.
Here is a synopsis of how the teams as a whole did on the problems:
| # |
Name |
# Correct Solutions |
# Teams Tried Solution |
Minutes Until 1st Correct Solution |
| 1 | Cowculations |
34 | 43 | 54 |
| 2 | Intersecting Lines |
57 | 73 | 36 |
| 3 | Hi-Q |
13 | 17 | 85 |
| 4 | Call Forwarding |
16 | 31 | 65 |
| 5 | Making the Grade |
20 | 27 | 57 |
| 6 | Perfection |
76 | 84 | 10 |
| 7 | Shipping Routes |
14 | 15 | 58 |
| 8 | Slurpys |
35 | 58 | 26 |
Click here
to see more information about the contest, including
the complete contest results.
Problem 1: Cowculations
Based on number of correct solutions, this was the 5th hardest problem
in the contest. 34 teams solved it correctly.
Hidden in the description of this problem is the fact that the cows
used base 4 arithmetic! After all, they have four hooves and the problem
does state that they "are able to think on their feet." If you carefully
study the addition table you will realize that V can be replaced by 0,
U by 1, C by 2, and D by 3. Therefore, to solve the problem you can
just create a function that transforms cow numbers into integers. Of
course the shift right operation is integer division by 4 and the shift
left operation is multiplication by 4.
Problem 2: Intersecting Lines
Based on number of correct solutions, this was the 2nd easiest problem
in the contest. 57 teams solved it correctly.
Some contestants appeared to confuse the concepts of line segment
and line in this problem. Remember that when we say two points
on the XY plane determine a line, the line in question is of infinite
length, not bounded by the two points.
Programs had to handle several special
cases ... vertical lines, parallel lines, etc.
Problem 3: Hi-Q
Based on number of correct solutions, this was the hardest problem
in the contest, although problems 4 and 7 were almost just as "hard".
13 teams solved it correctly.
The problem requires modeling the classic Hi-Q solitaire game.
Even though Hi-Q only has 7 rows and 7 columns,
in my solution I used a 9X9 two dimensional array, initializing
the border and the 2X2 squares in each corner with a value that
indicated it was not an actual hole. This saved me from having to
do lots of testing to keep me from going off the end of the array.
Instead, I could just test the array value.
Problem 4: Call Forwarding
Based on number of correct solutions, this was the 3rd hardest problem
in the contest, although it was almost just as "hard" as the two considered
"harder".
16 teams solved it correctly.
A few teams got confused because they interpreted the "duration" of
a call forwarding as the end time of the call forwarding.
When I solved this problem I realized I did not have to directly
identify cycles in the call forwarding graph in order to recognize
degenerate situations. An inelegant, yet easier way to discover these
situations is to count how many forwardings have been used so far when
trying to determine the final destination of a specific call. Since there
can be at most 100 forwardings set, if more than 100 forwardings are used
it indicates a loop in the forwarding set. Again, not very elegant, but
it works and its certainly an appropriate approach during a programming
contest.
Problem 5: Making the Grade
Based on number of correct solutions, this was the 4th hardest problem
in the contest. 20 teams solved it correctly. I don't think this
problem was particularly hard except it was "busy", i.e. there
was a lot of information in the spec.
Several teams asked during the contest when they should round
results to the nearest tenth. The problem statement says that
Mr. Chips does this "during his computations." I told those
teams they should do it at the end of each "step" in the
calculations, i.e., after calculating averages, class averages,
standard deviations and the average grade points, although I
don't know if this was crucial in terms of getting past the test
input.
Another question asked by a few teams was how could someone get an
F grade, since a D seems like the lowest grade that can be earned based
on a student's average. That is true ... the only way to get an F is
due to poor attendance.
Problem 6: Perfection
Based on number of correct solutions, this was by far
the easiest problem
in the contest. 76 teams solved it correctly.
The first correct solution was judged a mere 10 minutes into the
contest.
Seems like the main thing that gave some teams trouble with this problem
was recognizing that 1 is not a perfect number. While it is true
that 1 is a proper divisor of all integers greater than one, it is
not a propoer divisor of itself (no number is a propoer divisor of
itself), therefore it is deficient.
Problem 7: Shipping Routes
Based on number of correct solutions, this was the 2nd hardest problem
in the contest. 14 teams solved it correctly.
Solving this problem requires building a graph representing which
warehouses are directly connected to which other warehouses and then
determining the "shortest path" between two warehouses. Since the paths
are not weighted, the shortest path can be discovered by a simple
breadth-first search.
Problem 8: Slurpys
Based on number of correct solutions, this was the 3rd easiest problem
in the contest. 35 teams solved it correctly.
The finite state acceptors described in this problem can be created
using recursion. Note that the problem description handed out during
the contest included graphical depictions of Slimps and Slumps.
Send comments to:
joyce@monet.vill.edu
Updated November 18, 1996 - DTJ