2007 WPI High School Programming Contest

On a crisp, sunny morning on March 5 2007, 13 teams of high school students from central Massachusetts participated in the second WPI High School Programming Contest. The four-hour event attracted thirty-nine Junior and Senior students to compete in head-to-head competition.
 

The contest was held in the Civil Engineering programming laboratory (Kaven Hall 207) and the judging "Command Center" was down the hall where team advisors watched the contest unfold in real time as each student submission was judged by the contest judges.

The problems tested the programming ability of the students in different areas, such as prime numbers, mathematical series, Boolean logic, word problems, textual analysis, spatial computations, and polynomial arithmetic. Students were able to submit solutions written in programming languages such as C, C++, or Java. The contest was supported by an on-line submission system that allowed all participants to view the ongoing results of the competition in real-time.

The problem set contained seven problems of varying levels of difficulty, and students had to manage their time carefully as well as the number of their submissions; each failed submission received a small time penalty applicable towards the team score.

 

Ranking # Solved School Team

1st Place

 6 Acton-Boxborough Regional HS

2nd Place

 6 Mass Academy

3rd Place

 5 Westborough High School #1
  4 Saint John's High School
  4 King Philip Regional High School
  2 Shepherd Hill Regional High School
  1 St. Peter-Marian Jr/Sr High
  1 Wachusett Regional High School
  1 Pembroke High School #1
  1 Westborough High School #2

Contest Results
 

During the contest, the Acton-Boxborough Regional HS team built up a commanding lead by solving three problems within the first hour. After spending time solving one of the more complex problems in the contest, Mass Academy also solved three problems at the 2 hour mark. Soon after, the team from King Philip Regional High School moved into the same tier. Because the scoring system of the contest favors teams whose submissions are completed the earliest, the Acton-Boxborough Regional HS team was in the best position to win, but only if they continued their initial success and solve more problems.

With one hour to go in the contest, four teams had solved four problems: Acton-Boxborough Regional HS, Mass Academy, King Philip Regional High School, and Westborough High School Team #1. Suddenly, Westborough High school moved into first place, by solving five problems. A few minutes later, Mass Academy retaliated and moved into a first-place tie, with only 600 points separating the two front-leading teams. Where was Acton-Boxborough Regional HS? Had their initial success exhausted the team? With just 20 minutes to go in the contest, Action-Boxborough Regional HS gathered their energy and retook the lead, submitting two winning solutions in a 9 minute time period! As time ran out on the contest, Mass Academy submitted a final winning solution to problem P3, establishing themselves as the second place finisher.

After the conclusion of the contest, the winning teams were recognized, together with some of the more unusual contest submissions. One desperation submission, to remain anonymous, appears here:

public class Problem1 {
  public static void main( String[] args){
    System.out.println("24");
  }
}

Perhaps this anonymous team was graciously saluting the 2006 programming contest where the programming team from the Doherty Memorial High school submitted a similar solution which printed "42" instead. I would like to believe that the current submitters felt they were not worthy to submit a "42" submission, and in their own humble way, their submission captured the desperate finishing minutes of the competition.

The longest failed submission in the contest came to 214 lines of Java code. The longest successful entry was 129 lines from Acton-Boxborough Regional HS  for their solution to problem P3..

The team from Mass Academy owns the shortest successful solution at 35 lines, with comments! Here is their solution to P2, with slight reformatting.

import java.util.Scanner;
public class P2 {
  public static String process (String input) {
    String output="";
    for(int i=0;i<input.length();i++) {
      int endi=i;
      while (endi<input.length()-1) {
        if (input.charAt(endi+1)==input.charAt(i)) {
          endi++;
        } else {
          break;
        }
      }
      output=output+(endi-i+1)+input.charAt(i);
      i=endi;
    }
    return output;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String input=sc.nextLine();
    for(int l=0;l<5;l++) {
    input=process(input);
    System.out.println(input);
    }
  }
}

The Computer Science department would like to thank Mark Freitas (a member of the CS department's advisory board) for underwriting the costs of the contest, which allowed all students to participate for free and enabled us to give the students and advisors baseball hats and coffee mugs. We would like to thank the student volunteers who helped ensure a smooth running contest -- graduate students Daniel Yoo, Shivin Misra, and Tim Walsh. Professors Rob Lindeman and Micha Hofri were also on hand to support the contest director Prof. George Heineman. The Academic Technology Center (ATC) ensured the laboratories ran smoothly and Al Johannesen created the accounts for the contest. Thanks to Martha Cyr, the Director of the K-12 outreach program, and Kristen Tichenor, the Associate Vice President of Enrollment Management.

Contest Progress

There were a total of 31 successful problem submissions (from a total possible 91). The y-axis below shows the number of problems solved by each team, which appears as ever-increasing lines on the graph.

Problem Set

The full descriptions of the problems is available. Here are the summaries.

Problem Number & Name Description Sample Solution Solved by ... Failed by...
P1 Exponent This! An integer N is exponent unique if its prime decomposition contains no prime factor p that appears the same number of times as another prime factor q. Given a number N (in the range 1 < N ≤ 2147483647) determine whether N is exponent unique. You should observe that if N is a prime number, then it is also exponent unique. [full description] P1 4 teams 10 teams
P2 Sequence This! You are to write a program that takes as input a string of digits, S0, and then calculates the next five terms of the sequence (S1 through S5) where sequence term Sn+1 is derived by “describing” term Sn. For example, if S0 is “10444221” then S0 is described from left to right as “one 1, one 0, three 4’s, two 2’s, one 1” This string is converted into digits from left to right resulting in an S1 value of “1110342211”. [full description] P2 8 teams 3 teams
P3 Table This! You are to write a program that prints the truth table for a Boolean expression [full description] P3 3 teams 3 teams
P4 Climb This! A WORD LADDER is formed from an anchor word that is transformed, one letter at a time, to form a ladder of words that ultimately reaches a target word. Note that the order of the unaffected letters cannot change. A sample word ladder appears to the right. Your program must determine if a sequence of words forms a WORD LADDER. [full description] P4 7 teams 9 teams
P5 Histogram This! Given a set of lines of English text (including spaces and punctuation), you are to report the top ten most frequently used characters (regardless of capitalization) and their count totals. [full description] P5 4 teams 10 teams
P6 Box This! You are the operator of a fleet of unmanned drone spacecraft. You must track the movement of a set of drones moving in an imaginary two-dimensional plane divided into square unit regions. Each region is determined by an (x,y) label. Given a set of drones in the plane, we define the concept of a BoundingRectangle to be the smallest rectangle (with purely horizontal and vertical edges) that wholly contains all drones in the fleet. Your task is to project the movement of the fleet of drones 180 seconds into the future given their original locations and initial velocity. You must identify the earliest time (in seconds) when the BoundingRectangle of the fleet has the smallest area. [full description] P6 3 teams 1 team
P7 Compute This! You have been asked to write a program that computes the value of small polynomial functions. A polynomial is a mathematical expression involving a sum of powers for a variable multiplied by coefficients. [full description] P7 2 teams 5 teams

Test Cases

All submissions were graded electronically using custom contest software developed by Prof. George Heineman at WPI. The test cases for the above problems is included here.

Full Participation List

The following students participated in the contest.

Team School District Advisor Student1 Student2 Student3
11 Shepherd Hill Regional High School Deb Richard Matthew Netsch Adam Christian John Robert
08 Westborough High School #2 Paul Vital Max Klefstad Connor Hughes Gabrielle Ehrlich
13 Hopedale Jr/Sr High School Nancy Horan Brenda MacArthur Andrew Thompson Justin Vinueza
12 Wachusett Regional High School Nancy DiLeo Jon Brenner Andrew Keohane Christopher Scott
09 King Philip Regional High School Debora Myers Srujith Kudikala Partick Stetter Dan Tijerina
01 St. Peter-Marian Jr/Sr High Daniel Forhan Brendan Almonte Daniel Mott Andrew Cote
04 Pembroke High School #1 Bob Richard Steve Tressel Lauren Rappuci Brian Cote
03 Auburn High School Chris Lajoie Rocco Cataldo Josh Giangrande Jon Polaski
10 Saint John’s High School Gregory Blondin Kevin Cheetham Matthew Etre Nick Pellegrino
05 Mass Academy Karen Lang Luke Perkins Emily Ross Nate Williams
06 Acton-Boxborough Regional HS Kirk Marshall Scott Ames George Mossessian Prabhat Putchakayala
07 Westborough High School #1 Paul Vital Bhuvic Patel Josh Ehrlich Anil Vasireddi
02 Pembroke High School #2 Bob Richard Emillano Salazar Justin Porter Mike Ohrenberger