Eleventh BU ACM Contest
February 19th, 2008
sponsored by
February 19th, 2008
sponsored by
Message from the contest committee chair
First contest of the Spring semester and things ran smoothly overall. The contest server didn't have too many issues - although, we realized an issue that could occur with timeouts and multiple test cases (maybe we'll reduce the timeout?). Attendance was expected to be large, but it defeated all expectation. We had a full house, just about every computer was in use and we had a bunch of new faces - our 20 paper copies of the questions just wasn't enough! Also, python was used to generate test cases for every question this time, providing a dynamic and different set of test inputs.
The apparent theme of this contest was handling input and input issues proved to be a significant issue for our competitors. This was demonstrated by the large number of failures to the first question. Many competitors used nextInt, or took input into an int which failed many of the test cases (notably, test case 10 and 11 took out a majority of the attempts). One of the provided sample cases showed an excessively large numbers but this didn't stop the barrage of solutions that couldn't handle large numbers. Still, question 1 was the most solved by the competitors as it relied on only looking at the last two digits of the answer for all of the inputs and determining which sum was larger (the unmodified sum, or sum of the rounded to the nearest dollar values).
Question 2 was the next most solved. It was a modified nim game where 1-4 could be taken. Since the "you" always starts, you can guarantee the win if the number of zombies%5 == 1. Otherwise, Paul could force the win. A simple solution, but required a little bit of thinking to know how to play the game - this was the only problem with no tricky input, just a number. Questions 4 and 5 were the next most answered. Question 5 required parsing to find the appropriate values. Reading the problem statement, you know that ":" only appears in the appropriate locations (the food names only contain lowercase, uppercase and whitespace) so you can search each line for "fat: ", "carbs: " and "protein: " convert the value afterwards and do the appropriate calorie conversion. Some submissions neglected the whitespace issue. I expected simple find solutions but many didn't see that as a possibility. Question 4 was a minimum spanning tree question. It was constrained in such a way that with each new node in the tree, you immediately knew the value of the edge that would be added to the MST - each new node generated edges to all existing nodes with a value strictly larger than any existing edge. So, a MST approach could be used, or simply adding the edges would work too.
Question 3 and 6 were least answered. I was surprised by the lack of responses to Question 6. It was a simulation question and simply producing the steps generates the almost correct answer. Competitors were confused by the potential of the "Inf" answer - no sample that generated "Inf" was provided - and it seemed as if that were the limiting factor to this question. Otherwise, it was rather easy. Question 3 was probably the hardest question. It was a word search and not only did competitors have to find the width of the grid but they also had to clean up all of the whitespace. Then, search for the word in any usual orientation. Typos are common in this case - look at the solution for my method to help reduce the issue of typos - and they took out one of the solutions.
Overall, it seemed like a pretty good competition. There was food, coding, and chatter. Now, we are preparing for the next one - with less crazy inputs!
- Jason Loew
See pictures here! Completely unsorted!
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 | |
| JasonIHaveAName | 0:46 | 5 | 0:08 | 2 | - | 0 | - | 0 | 1:20 | 4 | 0:33 | 6 | 2:47 | 4 |
| guytotherightofworm | 0:06 | 3 | 1:15 | 2 | - | 2 | 1:20 | 1 | 1:03 | 3 | - | 0 | 3:44 | 4 |
| Alex Jaspersen | 0:02 | 2 | 1:29 | 2 | - | 0 | - | 0 | 0:29 | 1 | - | 0 | 2:00 | 3 |
| Strongwater | 0:13 | 3 | - | 34 | - | 0 | - | 0 | 0:49 | 3 | 1:47 | 11 | 2:49 | 3 |
| Leonid Domnitser | 0:34 | 3 | - | 0 | 1:00 | 2 | 1:30 | 2 | - | 2 | - | 0 | 3:04 | 3 |
| Amandur | 1:43 | 8 | 0:36 | 2 | - | 3 | - | 0 | - | 0 | - | 0 | 2:19 | 2 |
| Ari Ronen | 1:50 | 1 | - | 0 | 1:33 | 4 | - | 0 | - | 0 | - | 0 | 3:23 | 2 |
| erdem | 2:02 | 2 | 1:46 | 8 | - | 0 | - | 0 | - | 0 | - | 0 | 3:48 | 2 |
| RS | 0:34 | 7 | - | 0 | - | 1 | - | 0 | - | 0 | - | 3 | 0:34 | 1 |
| senk | 0:42 | 3 | - | 0 | - | 1 | - | 0 | - | 0 | - | 0 | 0:42 | 1 |
| Travis Farrell | 0:47 | 3 | - | 0 | - | 0 | - | 0 | - | 0 | - | 0 | 0:47 | 1 |
| Kevin Acunto | - | 0 | 0:50 | 6 | - | 0 | - | 0 | - | 0 | - | 0 | 0:50 | 1 |
| Timothy Reilly | - | 12 | - | 0 | - | 0 | 1:10 | 7 | - | 0 | - | 0 | 1:10 | 1 |
| thisAintNoGame | - | 4 | - | 0 | - | 6 | 1:15 | 4 | - | 1 | - | 0 | 1:15 | 1 |
| tedward | 1:31 | 3 | - | 0 | - | 4 | - | 0 | - | 0 | - | 0 | 1:31 | 1 |
| Tao Zhang | - | 0 | 1:32 | 5 | - | 0 | - | 0 | - | 0 | - | 3 | 1:32 | 1 |
| lesu | 1:36 | 13 | - | 6 | - | 0 | - | 0 | - | 0 | - | 0 | 1:36 | 1 |
| Gowrishankar | - | 0 | - | 0 | 1:37 | 2 | - | 0 | - | 0 | - | 0 | 1:37 | 1 |
| commaKazie | 1:57 | 12 | - | 0 | - | 0 | - | 0 | - | 0 | - | 0 | 1:57 | 1 |
| chao | - | 0 | - | 0 | - | 0 | 2:02 | 1 | - | 0 | - | 2 | 2:02 | 1 |
Honorable Mention
| erendemir ufuk kemal Steven | AriFTL Aaron Josh ajethoo1 | Rooster Abdoulaye perreal |
* Competitors who were not eligible for prizes were not ranked
Problem Statements
Problems 1-6.doc - Problems 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 |
BU11 |
| Date |
February 19th, 2008 |
| Location | Binghamton University, Room AAG004 |
| Sponsors | Bloomberg |
| Number of problems |
6 |
| Number of competitors |
~35 |
| Registration time |
7:45 PM |
| Contest start time |
8:10 PM |
| Contest end time |
10:15 PM |
| Supported Languages |
C/C++, Java, and C# |
| Timeout period |
30 seconds |
| Prizes |
First Prize: 30GB iPod Video, Second Prize: - $75 Amazon Gift Card Third Prize: - $25 Amazon Gift Card |
| Other Prizes |
Bloomberg Mouse Pads, T-Shirts, Rubix Cubes, Pictures, Bags |
| Food and beverage |
Pizza, Soda |