Contest Problems and Solutions

February 27, 2009

There were nine problems in the 2009 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:  How Long? (PDF)

A trip of known length has a desired average speed.  After completing part of the journey, the traveler desires to know how fast the remaining trip must proceed in order to meet the goal. 

Java solution to Problem 1: SecondHalf.java  

C++ solution to Problem 1: HowLong.cpp

Test data for Problem 1: data1

Problem 2:  What is the Area?  (PDF)   

A trapezoidal approximation to the area under the curve of a non-negative function must be computed.

Java solution to Problem 2: Area.java

C++ solution to Problem 2: Reimann.cpp

Test data for Problem 2: data2

Problem 3:  Satisfiability (PDF)

A sequence of disjunctions of boolean variables is presented.  What is a truth assignment for the variables that will satisfy all of the clauses?

Java solution to Problem 3: Satisfy.java  

C++ solution to Problem 3: Satisfiability.cpp

Test data for Problem 3: data3

Problem 4:  Squiggly Sudoku (PDF)   A CLASS BASED PROBLEM

A prospective solution to a Squiggly Sudoku problem is given.  Is that solution valid?

Java solution to Problem 4: SudokuChecker.java  

C++ solution to Problem 4: SquigglySudoku.cpp

Test data for Problem 4: data4

Java Files for the class: SudokuBoard.java  

        API for the class:  SudokuBoard.html 

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

Problem 5:  Job Scheduling  (PDF)

A number of jobs must be completed.  Jobs can be done in parallel, but some have pre-requisites.  If it is even possible to do them all, how long does it take?

Java solution to Problem 5: Scheduler.java  

C++ solution to Problem 5: JobScheduling.cpp

Test data for Problem 5: data5

Problem 6:  World Series  (PDF)  

Given the chance that your team will win any one game, what is the chance that it will win its playoff series?

Java solution to Problem 6: Winners.java  

C++ solution to Problem 6: WorldSeries.cpp

Test data for Problem 6: data6

Problem 7:  Component Testing (PDF)    A CLASS BASED PROBLEM

A group of prototypes for a new device have been produced.  Test the prototypes and determine the maximum stress that they can resist.  Both prototypes and time are a limited resource.

Java solution to Problem 7: Tester.java  

C++ solution to Problem 7: ManufacturingLot.cpp

Test data for Problem 7: data7

Java Files for the class: ComponentLot.java  

        API for the class:  ComponentLot.html 

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

Problem 8:  Undo Sequence    (PDF)   A TESTING PROBLEM

A series of actions, undos, actions, undos, etc. is undertaken.  Determine the net number of actions performed.

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: Undo Sequence Bug  

Actual contest web page: Undo Sequence Applet  (Not yet linked)

Problem 9:  Polygon Inclusion     (PDF)   A TESTING PROBLEM

Given a well-behaved polygon (no edge crossings, etc.), determine if a test point lies inside it.

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: Polygon Inclusion Bug  

Actual contest web page: Polygon Inclusion Applet (not yet linked)

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