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

 
 

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.

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.

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.

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.

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.

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.

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.

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.

Updated November 18, 1996 - DTJ