WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

2012 WPI High School Programming Contest

The WPI Computer Science department hosted the seventh annual High School Programming contest on an crisp Spring day in Worcester, Massachusetts. Forty teams from twenty-six school districts registered for the event, representing the most number of teams and students ever to participate in the contest. The teams primarily came from school districts from central Massachusetts, although some teams made the trip to WPI from Connecticut and New Hampshire.


View 2012 WPI High School Programming Contest in a larger map

Because of the increased number of students, the four-hour contest was held in three computing laboratories on campus (two in Kaven Hall and one in Salisbury Hall) and the judging "Command Center" was in KH 116 where team advisors watched the contest unfold in real time as each student submission was judged by the contest judge. 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 financial computation, permutations, graph series, symbolic evaluation and string compression. 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 9 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.

The final results of the contest appear in the following table:

NumSolvedScoreTeamSchool
94229213Westborough High School
95803730Mass Academy
84810539Wachusett Regional High School
74035819Mass Academy
74247517Greater Hartford Academy of Math and Science
74667614Algonquin Regional High School
74834526Minnechaug Regional High School
75147521Saint John's High School
75287520Needham High School
75814212Wellesley High School
7659726Milford High School
5230402Acton-Boxborough Regional High School
5277081Academy of Aerospace and Engineering
52961735Phillips Exeter Academy
5303659Tantasqua Regional High School
53458824The Bromfield School
53870833Needham High School
5420514Algonquin Regional High School
54327436Saint John's High School
43025410Wachusett Regional High School
4319378Sharon High School
31516629Marlborough High School
32428940Wayland High School
33055418Marlborough High School
3369935Grafton High School
21051334Norwich Free Academy
2203413Advanced Math and Science Academy Charter School
22296337Shepherd Hill High School
1194228Greater Hartford Academy of Math and Science
1583816Framingham High School
11094025Wellesley High School
1115797Quabbin Regional High School
11159032Nashoba Regional High School

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:

  • Adrian Boteanu
  • Theophilos Giannakopolous
  • Kenneth Loomis
  • Abhishek Mukherji
  • Sarah Schults
  • Francis Usher
  • Danny Yoo
This year the volunteers were especially necessary because of the dramatic increase in student participation. The contest director was Prof. George Heineman. The Academic Technology Center (ATC) ensured the laboratories ran smoothly and the Help Desk created the accounts for the contest. WPI NetOps helped set up the wireless guest accounts for the teacher coaches.

Contest Progress

All submissions were graded electronically using custom contest software developed by Prof. George Heineman at WPI. All students were assigned to their respective stations in the computer labs in Kaven Hall and the contest began just after 9:13 AM. The first submission was completed after 720 seconds and during the first hour there was a flurry of activity as the judge tried to keep up with the submissions from the students. The first hiccup came when the first team to code in C++ submitted their solution. It turned out that there was an unexpected access problem to core C++ libraries and the judge had to call on system administrators Michael Voorhis and Jesse Banning to rapidly update some key Unix directories; fortunately within minutes the problem was solved.

Because of the scoring used for the contest, it is not sufficient to simply solve all problems first, one must compute the accumulated scores of the times it took to solve each individual problem. Because of this, positions on the “leader board” for the contest were up for grabs. In particular, there were two problems (P2 and P3) that were considered to be the most complex in the contest -- whoever could complete these problems would -- likely be the winner. As it turns out, two teams vied for the competitive top-spot, and ultimately the winner was the team who had rapidly submitted solutions to the easiest problems in he contest. By the end of the contest, two teams had solved nine problems while a third was able to complete eight. These were certainly notable achievements!

There were a total of 114 successful problem submissions (from a total possible 358 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.

Problem Set

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

Problem Number & Name DescriptionSample SolutionSolved by...
P1

Penny Lane

Given a dollar amount between $0.01 and $9.99 you are to compute the fewest number of standard American coins needed to produce that sum.

[full description]

Q1.java 32
P2

Rinse. Lather. Repeat

Given a set of 1 . n . 5 nested for statement loops, how many times does the innermost BODY execute?

[full description]

Q2.java 4
P3

A Cold Compress Cures Everything

For an arbitrary string, construct a sequence of bits representing the compression of that string taking into account 3-bit encodings for the 7 high-frequency lower case letters in English.

[full description]

Q3.java 4
P4

Triple Play

Given integer N (where 7 ≤ N ≤ 100) you are to output in ascending order the set of all triples (X0, X1, X2) such that Xi is a perfect square and X0, X1, X2 forms an arithmetic sequence.

[full description]

Q4.java 22
P5

Anything you can do, I can do better

A saddle point is a value in the matrix which is simultaneously the largest value in its column and the smallest value in its row. Given a 2D matrix, compute the saddle point, or determine that it doesn't exist.

[full description]

Q5.java 21
P6

A Consummation Devoutly To Be Wished

Given two graphs, G1 and G2, you are to compute the union graph G3 = G1+G2 such that V3 = V1+V2 and E3 = E1+E2.

[full description]

Q6.java 10
P7

A Subset By Any Other Name

Given a set of n consecutive capital letters, "ABCDE", and an integer 1 ≤ p ≤ n, you are to output in alphabetic order all possible different subsets of size p.

[full description]

Q7.java 12
P8

When Daylight Turns to Knight

Given a 4x4 chess board, place a knight on some square and mark that square number 1. Your program must validate that a board containing a specific set of marked squares represents a final valid knight's path.

[full description]

Q8.java 18
P9

A Shadow moves across the moon

In high-speed finance it is often necessary to compute the "moving average" of a series of n values. Do so for a set of numbers to 1-digit of precision.

[full description]

Q9.java 27

 


[Return to the WPI Homepage] [Return to the CS Homepage]

webmaster at cs wpi edu / 06 March 2012