For many in central Massachusetts, March 3rd was just another day in their busy work schedule. But look deeper and you will see the ebb and flow of cars on the surrounding highways, converging inevitably towards WPI. For a select set of high school students, today was the high school programming contest, a chance to test their mettle against their peers. In total 17 teams of students from fourteen different high schools in central Massachusetts (and one team from Connecticut) participated in the third WPI High School Programming Contest.
The four-hour 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. Each student team had a single computer on which to work, and so they had to manage their time (and typing ability!) efficiently to be able to place well in the contest. The problems tested the programming ability of the students in different areas, such as random number generation, word problems, data compression, geometric analysis, chemical compound analysis, dice probability, path computation and computation of election voting results. 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 eight 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.
| Score | Team | School | |
|
8
|
19809 | team.20 | Worcester Academy |
|
8
|
21605 | team.16 | Algonquin Regional High School |
|
8
|
33956 | team.06 | Acton-Boxborough Regional HS |
|
8
|
37006 | team.08 | Auburn High School |
|
8
|
43423 | team.10 | Wachusett Regional High School |
|
8
|
44548 | team.13 | Westborough High School |
|
8
|
48318 | team.18 | Mass Academy |
|
8
|
59220 | team.03 | Saint John's High |
|
7
|
57080 | team.22 | Quabbin Regional High School |
|
6
|
49058 | team.07 | Norwich Free Academy |
|
5
|
52070 | team.05 | St. John’s High |
|
4
|
14862 | team.11 | Grafton High School |
|
3
|
22899 | team.12 | Wachusett Regional High School |
|
3
|
26246 | team.15 | Doherty High School |
|
2
|
18317 | team.09 | Leicester High School |
|
1
|
6531 | team.17 | Shepherd Hill Regional High School |
Team.20 (Worcester Academy) came out of the gate at bullet speed. They solved their first problem in 4 minutes and 8 seconds, and their second within 15 minutes. Quite rapidly, however team.16 (Algonquin Regional High School) overtook them for the lead, which was short lived. As these two teams battled it out for first place, team.06 (Acton-Boxborough) and team.08 (Auburn High School) rapidly moved into second place. One small misstep by either set of teams, and the frontrunners would find themselves behind. Then it happened. Team.20 (Worcester Academy) submitted a problem and, in doing so, uncovered a defect in the test cases used to judge the contest. The organizers rapidly fixed the problem, but during the delay team.16 (Algonquin Regional High School) raced ahead to complete all eight problems by 1 hour and five minutes. The judging room was amazed at the rapidity of the solution. Then within fifteen minutes, team.20 (Worcester Academy) came through and solved the final problems. Because the scoring system favors teams who submit early and often (without error) the two teams were separated by only 243 points. When the judges fixed the testing defect and (only fairly) awarded team.20 (Worcester Academy) the points they should have had, then it was clear that team.20 (Worcester Academy) had actually won the contest. Team.16 (Algonquin Regional High School) accepted the judge's decision with magnanimity.
This was the first time (in the three years of this contest) that any team has completed all problems in the contest. But the event was far from over. At the two hour mark, team.08 (Auburn High School) hit an unexpected snag, allowing team.06 (Acton-Boxborough) to place third for the contest. In total, eight teams solved all eight problems in the contest, with team.03 (Saint John's High) completing the final problem with just minutes remaining in the contest. A fine performance by all teams in working under pressure.
With the top three positions locked up by the 3rd hour, the remaining contestants worked steadily to complete as many problems as they could. In total, eleven student teams ended up solving more than half of the contest problems, a fine accomplishment! 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("ALL YOUR BASE ARE BELONG TO US!"); } } |
Perhaps this anonymous team was unwilling to go down without a fight. One of the more entertaining submissions came from team.05 (Saint John's High School) where they had a winning submission for a problem to determine the type of a triangle, even though their code had a serious defect:
if (sizesEqual == 0) {
System.out.println("SCALAR");
}
if (sizesEqual == 1) {
System.out.println("ISOSCELES");
}
if (sizesEqual == 3) {
System.out.println("SCALAR");
}
|
The third (and final) case should have output "EQUILATERAL" as the answer. However, their code worked because of the little known fact that triangles formed on the Cartesian plane from integer coordinates cannot be Equilateral. They were saved by Mathematics! Some of the shortest entries came in at 15 lines. Here is the solution from team.20 (Worcester Academy) for problem 1:
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
int main(int argc, char *argv[]){
int x,i,tmp;
cin >> x;
for(i=1;i<=10;i++){
tmp =
((x*x)%1000000)/100;
cout << tmp
<< endl;
x = tmp;
}
return 0;
}
|
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 a set of trophies and certificates to mark their attendance in the contest. We would like to thank the student volunteers who helped ensure a smooth running contest -- graduate students Daniel Yoo and Cliff Lindsay. The contest director was Prof. George Heineman. The Academic Technology Center (ATC) ensured the laboratories ran smoothly and Al Johannesen created the accounts for the contest. Thanks also to Martha Cyr, the Director of the K-12 outreach program, and Kristen Tichenor, the Associate Vice President of Enrollment Management.
All submissions were graded electronically using custom contest software developed by Prof. George Heineman at WPI.
There were a total of 95 successful problem submissions (from a total possible 159 submissions). The y-axis below shows the number of problems solved by each team, which appears as ever-increasing lines on the graph. The x-axis shows the progress of the contest in seconds (with hour divisions clearly identified):
The full descriptions of the problems is available. Here are the summaries.
| Problem Number & Name | Description | Sample Solution |
Solved by ... |
| P1 Pay it Forward |
The middle-square method can be used to generate pseudo-random numbers. The method was first suggested by John Von Neumann in 1946. Given a four-digit number 0 £ xi £ 9999, compute xi * xi and extract the middle four digits to compute xi+1. |
P1 | 16 teams |
| P2 Spider-man |
The block of letters below is an example of a “Word Web”.
You will note that the words reading across (RAIN, ACRE, etc…) from top to bottom are the same as the words reading down, from left to right, when considering the 1st letter of each row, then the 2nd letter of each row, etc…You are to write a program that receives a value N, where 3 £ N £ 10 and a block of letters of size N x N. You must determine if the block contains a valid word web. [full description] |
P2 | 13 teams |
| P3 Marathon Man | You are given a string of 16 letters using As and Bs. You must output a compressed Run Length Encoding (RLE) of the string. Using RLE, two or more consecutive letters of the same value represented by a count followed by the letter, otherwise the letter is unchanged. | P3 | 12 teams |
| P4 My Big Fat Greek Wedding |
You are given three points in the plane using integer coordinates. These three points define a triangle. Your job is to classify the triangle by considering the length of its sides. [full description] |
P4 | 15 teams |
| P5 The Nutty Professor |
You are asked to report on the number of atoms given a chemical compound, that is, a substance consisting of two or more different elements chemically bonded together. A compound is described using a molecular formula, which is a string that supplies information about the types and spatial arrangement of the elements. [full description] |
P5 | 10 teams |
| P6 The Gambler |
You are given two dice from the popular word game "Boggle"™ . Each die has six sides, with a letter from A to Z on each side (there may be duplicates on the same die).You will be told the letters that appear on the first die and the letters that appear on the second die. Your goal is to state the odds that when you roll the pair of dice, the top two letters will be identical. [full description] |
P6 | 12 teams |
| P7 Pan's Labyrinth |
You are given a puzzle to solve consisting of a 5x5 square of 25 different capital letters from A-Z. You must determine if there is an unbroken path from the letter A to the letter Y only by moving between neighboring squares. No letter appears twice. [full description] |
P7 | 8 teams |
| P8 Election |
You are responsible for determining election results for a mayoral race with up to 50 precincts and no more than 10 candidates running for office. Each precinct reports on a single line its results by listing each candidate’s last name with the votes received; candidates are listed in decreasing order of votes received and candidates receiving no votes are not listed. You can assume there are at least 2 candidates running! |
P8 | 8 teams |
