Twelfth BU ACM Contest
March 18th, 2008
sponsored by
March 18th, 2008
sponsored by
Message from the contest committee chair
The second contest of the Spring semester brought in an unexpectedly large group for this busy time in the semester. Fortunately, 4 sheet pizzas fed the hungry coders and everything ran extremely well this time. This contest marked a departure from the difficult parsing issues from the first contest and a majority of the competitors answered the first question correctly.
Most competitors started off on the first question and found it relatively straightforward. Just keep a sum of the kilobits and solve for megabytes and then cost at the end. The major errors were dividing too early or too often but were often dealt with by simply trying again.
For the first hour, the contest went along slowly. After the first question, competitiors moved sequentially to the second. After a small correction to the Shatner problem - the question initially neglected to require the sentences to be as long as possible - a handful of solutions came in and the contest stood still with the top competitors having two correct submissions for quite a while.
No one answered the sixth question. As a scheduling problem the solution was clearly going to be slow. However, we suspect that the hassle of managing the data led to only a few attempts at the solution. The testcases were kept simple enough to iterate on but still required a bit of code just to manage.
The top three competitors (thisAintNoGame, random person and Leonid Domnitser) were the only competitors to submit correct code for questions other than the first two. Question 4, the zombie rolling problem was a dynamic programming problem where you had to keep track of how many zombies you put into the clump was answered by our second and third place competitors - leaving submission speed (a matter of 12 minutes) the tie-breaking factor. thisAintNoGame was the only one to solve question 3 (a permutation ordering problem) as well as question 5 (which was found to have a typo in the solution key) using a win/lose memoization of the game positions.
This time we also had prizes for the top two competitors who haven't won anything before. Congrats to ilost and Ari Ronen for being the fastest two competitors in this group.
- Jason Loew
Contest Standings
| Name | 1 | 2 | 3 | 4 | 5 | 6 | Total | |||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| T | N | T | N | T | N | T | N | T | N | T | N | Total Time | Solved | |
| thisAintNoGame | 0:17 | 2 | 0:45 | 1 | 1:15 | 4 | - | 0 | 1:32 | 1 | - | 0 | 3:49 | 4 |
| random person | 0:49 | 2 | 0:53 | 1 | - | 0 | 1:37 | 2 | - | 3 | - | 0 | 3:19 | 3 |
| Leonid Domnitser | 0:26 | 3 | 1:20 | 2 | - | 0 | 1:45 | 3 | - | 0 | - | 0 | 3:31 | 3 |
| ilost | 0:07 | 1 | 0:28 | 2 | - | 0 | - | 0 | - | 0 | - | 0 | 0:35 | 2 |
| *bob | 0:11 | 1 | 0:35 | 1 | - | 0 | - | 0 | - | 1 | - | 0 | 0:46 | 2 |
| With name | 0:38 | 2 | 1:18 | 6 | - | 0 | - | 0 | - | 0 | - | 3 | 1:56 | 2 |
| Ari Ronen | 0:05 | 3 | 1:55 | 8 | - | 0 | - | 0 | - | 0 | - | 0 | 2:00 | 2 |
| senk | 0:34 | 1 | 1:36 | 3 | - | 0 | - | 0 | - | 0 | - | 0 | 2:10 | 2 |
| eroth1 | 1:37 | 2 | 1:38 | 3 | - | 0 | - | 0 | - | 0 | - | 0 | 3:15 | 2 |
| Travis Farrell | 0:13 | 1 | - | 0 | - | 0 | - | 0 | - | 0 | - | 0 | 0:13 | 1 |
| erdem | 0:14 | 1 | - | 0 | - | 0 | - | 0 | - | 0 | - | 0 | 0:14 | 1 |
| TrudySue | 0:15 | 1 | - | 7 | - | 0 | - | 0 | - | 0 | - | 0 | 0:15 | 1 |
| Tim Reilly | 0:16 | 2 | - | 4 | - | 0 | - | 0 | - | 0 | - | 0 | 0:16 | 1 |
| Amandur | 0:18 | 1 | - | 0 | - | 0 | - | 0 | - | 0 | - | 0 | 0:18 | 1 |
| Gowrishankar | 0:25 | 1 | - | 1 | - | 0 | - | 0 | - | 0 | - | 0 | 0:25 | 1 |
| root | 0:29 | 1 | - | 0 | - | 0 | - | 2 | - | 0 | - | 0 | 0:29 | 1 |
| perreal | 0:30 | 2 | - | 0 | - | 0 | - | 3 | - | 0 | - | 0 | 0:30 | 1 |
| lesu | 0:44 | 8 | - | 0 | - | 0 | - | 0 | - | 0 | - | 0 | 0:44 | 1 |
| jcasner1 | - | 2 | 1:29 | 1 | - | 0 | - | 0 | - | 0 | - | 0 | 1:29 | 1 |
| sloscal1 | 1:46 | 2 | - | 0 | - | 0 | - | 2 | - | 2 | - | 0 | 1:46 | 1 |
Honorable Mention
| youThinkThisAGame steveissexier JasonGallia gsivana1 | CVR imStillTiedWithAndres |
* Competitors who were not eligible for prizes were not ranked
Problem Statements
Problem Statements 1-6.doc - Problem Statements 1-6.pdf -
Testcases
There is a folder of testcases for each problem. The input files are labelled "1.input", "2.input", etc. and their corresponding output files are labelled "1.output", "2.output", etc.
Problem 1 - Problem 2 - Problem 3 - Problem 4 - Problem 5 - Problem 6 -
Solutions
All the solutions provided are in C++.
Problem 1 - Problem 2 - Problem 3 - Problem 4 - Problem 5 - Problem 6 -
Submissions
For the purpose of anonymity, submissons have been posted by ID number rather than by name.
Problem1 - Problem2 - Problem3 - Problem4 - Problem5 - Problem6 -
Summary
| Contest Number |
BU12 |
| Date |
March 18th, 2008 |
| Location | Binghamton University, Room AAG004 |
| Sponsors | Bloomberg |
| Number of problems |
6 |
| Number of competitors |
~28 |
| Registration time |
7:45 PM |
| Contest start time |
8:00 PM |
| Contest end time |
10:00 PM |
| Supported Languages |
C/C++, Java, and C# |
| Timeout period |
15 seconds |
| Prizes |
First Prize: 30GB iPod Video, Second Prize: - $75 Amazon Gift Card Third Prize: - $25 Amazon Gift Card Runner-Ups: First Prize: - $10 Amazon Gift Card Second Prize: $5 Amazon Gift Card |
| Other Prizes |
- |
| Food and beverage |
Pizza, Soda |