Third BU ACM Contest
April 20th, 2006
sponsored by Professor Garrison and
April 20th, 2006
sponsored by Professor Garrison and
Message from the contest committee chair
This was the last contest of the school year, and it was the best contest yet! The problem difficuly was just right, and the room was packed to capacity thanks to both our "regulars" and Christine Horgan's advertising and publicity efforts.
Perhaps there should have been a sixth problem, because three of the competitors managed to defeat all five problems. Although Derek Mauro and Jason Loew had secured first and second place respectively with 20 minutes left in the contest, third place was still up for grabs until the final minutes of the contest. During these final minutes, Saugata Ghose jumped up to third place by solving "Change It Up". Once again, the competitors exceeded my expectations.
One interesting issue was the order that the competitors chose to solve the problems in. On average, competitors tended to solve Problems 1 and 4 first, followed by Problems 3 and 5, and finally Problem 2; however, there was a significant amount of variation from this pattern. The standings also shed some light on problem difficulty; from easiest to hardest we have: 4, 5, 3, 1, 2. "Unbalanced" was a relatively straight-forward problem, and it could be solved using either the stack model (push down automata), or by using a recursive method. "Blaisin'" was also straight-forward, but there was the issue of overflow. Students could overcome the overflow issue in a number of ways: by using Pascal's triangle to avoid large numbers, by using Java which has the BigInteger class, or by writing code to cancel and reduce terms in the n!/(r!*(n-r)!) equation before evaluating it. "Romani Ite Domum" had a clear description but one of those annoying problems that had many separate cases to be deal with. And, to top it off, there was the issue of whitespace do deal with as well. Problem 1, "Change It Up", was deceptively hard - many students attempted this problem but did not solve it successfully. Some of this could be explained perhaps by a bias towards the Problem 1 because it is the first problem that many of the competitors read. The problem had very simple input and output: one integer between 1 and 99 as input, and one integer between 1 and 9 as output. Problem 2, "Fragments", was clearly the hardest problem, requiring a brute force approach. Only the competitors who solved all five problems solved "Fragments" successfully.
The problem set aside, this contest was also interesting because we experimented with the idea of allowing two person teams. Although none of the teams solved two or more problems, I think this experiment provided a lesson in the difficulties of working as a team and dealing with challenge of sharing a single computer among multiple people. It is my hope that we can experiment further with two and three person teams in future contests.
Another experiment we tried this contest was a change in the food. Typically, we just order two sheet pizzas because they feed many people for a relatively small amount of money. For a change, I decided to pitch in some extra money from my own pocket so that we could get Quizznos and a single sheet pizza instead. Although many of the competitors seemed to enjoy the food from Quizznos, it was ultimately a mistake to cut back on the number of sheet pizzas that we ordered. Nevertheless, I think it was good to try offering a wider variety of food.
This semester was a great start for the BU ACM Chapter, and this contest was an awesome way to end the semester. Hopefully, BU ACM Chapter can keep this momentum going next semester. Special thanks to Professor Garrison and Bloomberg for furnishing the prize money and the food and beverage.
-Andrew Paroski
Contest Standings
Rank |
Name |
1 |
2 |
3 |
4 |
5 |
Total Time |
Problems Solved |
| 1 |
Derek Mauro |
11:41 |
1:34:28 |
49:00 |
37:15 |
18:31 |
3:30:55 |
5 |
| 2 |
Jason Loew |
56:27 |
1:39:16 |
26:07 |
31:48 |
1:14:40 |
4:48:18 |
5 |
| * |
Nicholas Maliwacki |
18:18 |
39:04 |
1:40:54 |
1:19:24 |
1:10:50 |
5:08:30 |
5 |
| 3 |
Saugata Ghose |
1:56:18 |
- |
1:22:06 |
46:39 |
1:01:09 |
5:06:12 |
4 |
| 4 |
Timothy Reilly |
- |
- |
56:02 |
1:14:54 |
11:54 | 2:22:50 |
3 |
| 5 |
James M Leddy |
24:52 |
- |
- |
1:02:40 |
1:21:01 |
2:48:33 |
3 |
| 6 |
Matt McDonald |
- |
- |
1:38:54 |
16:31 |
1:03:58 |
2:59:23 |
3 |
| 7 |
Yash Lodha |
11:03 |
- |
- |
1:12:48 |
1:38:09 |
3:02:00 |
3 |
| 8 |
Robert Frank |
- |
- |
57:05 |
1:09:55 |
1:26:03 |
3:33:03 | 3 |
| 9 |
Leonid Domnitser |
- |
- |
1:06:32 |
1:31:03 |
1:54:46 |
4:32:21 |
3 |
| 10 |
Ari Fuchs | - |
- |
1:30:23 |
31:32 |
- |
2:01:55 |
2 |
| 11 |
Chetibi Aymane | - |
- |
- |
1:33:43 |
1:13:43 |
2:47:26 |
2 |
Honorable Mention
| Afro Thunder Jacob Benko Onur Can Cakmak CHUBU Dan Copel |
Xiangfeng Du Brad Dzigas Manuel E GarciaDuque Joe Gentile Tenseng Guh |
Nadir Seha Islam Ping-Han Lin Jake McGraw Mitch and Luke Brandon Shu |
* Competitors who were not eligible for prizes were not ranked
Problem Statements
Problem 1 - Problem 2 - Problem 3 - Problem 4 - Problem 5
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
Solutions
All the solutions provided are in C++.
Problem 1 - Problem 2 - Problem 3 - Problem 4 - Problem 5
Submissions
For the purpose of anonymity, submissons have been posted by ID number rather than by name.
1068 - 1306 - 1910 - 2004 - 2236 - 2758 - 2804 - 2835 - 3803 - 3856 - 4024 - 4483 - 4599 - 4881 - 5067 - 5562 - 6292 - 6648 - 6742 - 6786 - 7926 - 7956 - 8144 - 8354 - 8855 - 9430 - 9601 - 9786
Summary
| Contest Number |
BU3 |
| Date |
April 20th, 2006 |
| Location | Binghamton University, Academic A, Room G04 |
| Sponsors | Bloomberg and Professor Garrison |
| Number of problems |
5 |
| Number of competitors |
32 |
| Registration time |
6:20 PM |
| Contest start time |
6:30 PM |
| Contest end time |
8:30 PM |
| Supported Languages |
C/C++, Java, and C# |
| Timeout period |
5 seconds |
| Cash Prizes |
First Prize $90, Second Prize $60, Third Prize $30 |
| Other Prizes |
TopCoder T-shirts |
| Food and beverage |
Quizzno's subs, Nirchi's pizza, bottled watter, soda, juice boxes |