Contest Problems and Solutions

February 15, 2008

There were nine problems in the 2008 Programming Contest.  The first seven were programming problems and the last two were the new Challenge Problems.

Below you will find a brief description of each of the problems. By following the link for the problem you will find a more complete description of the problem including a specification of the requirements and effects of the program and examples.  For the programming problems, a Java solution, a C++ solution, and the test data that were used to test submitted programs to each problem are available as well.  For the class-based problems, the source files for the (supplied) compiled classes are also provided.  For the Challenge Problems, links to a description of the bug and to the web page used during the test are also available.

Dr. David Levine of the Computer Science Department drafted the problem statements and wrote the various solutions that we have made available.

Problem 1:  What?  It cannot be that cold!!! (PDF)

As the use of Celsius temperatures becomes more prevalent, many folks will need to learn to convert from Celsius to the more familiar Fahrenheit scale.  This problem compares an approximation to the exact computation.

Java solution to Problem 1: Cold.java  

C++ solution to Problem 1: temperature.cpp

Test data for Problem 1: data1

Problem 2:  Land Of Sweets  (PDF)    A CLASS BASED PROBLEM

A number of people play a simplified version of the game of CandyLand.  Who wins?

Java solution to Problem 2: LandOfSweets.java

C++ solution to Problem 2: CandyLand.cpp

Test data for Problem 2: data2

Java Files for the class: CandyGame.java  

        API for the class:  CandyGame.html 

C++ Files for the class: CandyGame.h  CandyGame.cpp 

Problem 3:  Tumor Detection (PDF)

A slice of an MRI scan is given, along with a tumor profile.  Where are the tumors, if any?

Java solution to Problem 3: Tumor.java  

C++ solution to Problem 3: Tumor.cpp

Test data for Problem 3: data3

Problem 4:  Find Disk (PDF)

A bunch of circular windows on a desktop are displayed.  Given a mouse click, which window is selected.

Java solution to Problem 4: CircleChoice.java  

C++ solution to Problem 4: FindDisk.cpp

Test data for Problem 4: data4

Problem 5:  Benford's Distribution  (PDF)

How often does each digit appear as a first digit within a data set?

Java solution to Problem 5: FirstDigits.java  

C++ solution to Problem 5: Benford.cpp

Test data for Problem 5: data5

Problem 6:  Bomb Defusal  (PDF)   A CLASS BASED PROBLEM

James Bond can always defuse his bombs before they detonate.  With the appropriate gadgets, determine the code to defuse this one.

Java solution to Problem 6: Decrypt.java  

C++ solution to Problem 6: Defuse.cpp

Test data for Problem 6: data6

Java Files for the class: BombMeter.java  

        API for the class:  BombMeter.html 

C++ Files for the class: bombMeter.h  bombMeter.cpp 

Problem 7:  Data Compression (PDF)

Given a bit string, perform a simple run-length encoding to (hopefully) compress it.

Java solution to Problem 7: Compress.java  

C++ solution to Problem 7: Compress.cpp

Test data for Problem 7: data7

Problem 8:  Number Theory    (PDF)   A TESTING PROBLEM

In number theory, the function sigma(n) is defined to be the sum of the divisors of n.  Compute this function.

Note that since this is a testing problem, the real challenge is to determine the bug in the judge's code - which is available as an applet on a web page only.

Description of the bug: Sigma Function Bug  

Actual contest web page: Sigma Function Applet

Problem 9:  State Machines     (PDF)   A TESTING PROBLEM

Given a description of a state machine, an input string and an initial state, determine in which state the machine terminates.

Note that since this is a testing problem, the real challenge is to determine the bug in the judge's code - which is available as an applet on a web page only.

Description of the bug: State Machine Bug  

Actual contest web page: State Machine Applet

We are now aware of an error in the applet that was used during the contest.  Problem 9 has been removed from the results and will not be counted.  We anticipate fixing the bug for the applet and posting it soon.

For additional information, please contact:

                  Dr. Steven K. Andrianoff, Contest Director
                  Department of Computer Science
                  St. Bonaventure University
                  St. Bonaventure, NY   14778
                  Phone: (716) 375-2053
                  FAX: (716) 375-7618