First BU ACM Team Contest
May 6th, 2008
sponsored by
May 6th, 2008
sponsored by
Message from the contest committee chair
This was an interesting contest. Our first team contest, first time using an answer verifier, lots of new faces and more difficult problems than usual. The turnout was a bit more than expected due to the influences of Prof. Garrison and these problems proved to be a bit more difficult than usual.
Problem 1 was a greedy problem. Since all food items have the same value, you just want to maximize the number of food items served. This could be approached by looking at the fact that food restrictions were nicely hierarchical so you could work from most restrictive to least or least to most. Either way, the greedy approach gave a valid answer. This question caused a problem with our verifier and let through a solution which fed spicy food to a non-spicy customer. Fortunately, this didn't change the contest results.
Problem 2 kept competitors thinking that there was a nice formulaic solution - if there is, I have no clue about it. A DP solution is the expected approach, however, it can't be solved with traditional 2D DP. 3D DP handles the problem appropriately. A few groups tried a tree approach - which will work in this case due to the layout of the problem - however, it must be a weighted tree in order to appropriately reflect the probability of a particular path (or it must be a complete tree which would degenerate to the DP case).
Problem 3 was a graph problem. The bounds were small enough to try all cases (only about 7500 in all). So, competitors needed to generate a function to check if the new map was valid and a function to generate all possible maps. In this case, the verifier just took the output provided and tossed it into its generator. This resulted in a bit of code, but could be relatively clean to implement.
Problem 4 was the only problem successfully solved. This was probably the easiest to solve but timeout considerations threw out a lot of potential answers. Naively squaring the digits for all numbers and detecting the loop was too slow to pass through the timeout. However, you could retain previous results and check against those in order to improve performance. The first solution took a slightly different approach - run until a single digit result occurs, only 1 and 7 are valid the rest are not - that preserved no prior information but was fast enough.
Problem 5 was the return of a problem that previously didn't make the cut for a competition. The roaming guards were a simulation problem. Put all of the zombies on the map and move everyone at the same time. You can attempt to solve for all 4 possible directions at once so you just need code to check if the cart makes it past the boundary.
- Jason Loew
Contest Standings
| Name | 1 | 2 | 3 | 4 | 5 | Total | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Time | Attempts | Time | Attempts | Time | Attempts | Time | Attempts | Time | Attempts | Total Time | Solved | |
| f***java | - | 0 | - | 0 | - | 0 | 0:28 | 1 | - | 0 | 0:28 | 1 |
| Prague Isotops | - | 0 | - | 0 | - | 0 | 0:55 | 6 | - | 1 | 0:55 | 1 |
Honorable Mention
| WestCoastBallers tulin bluebarracudas every extend extra credit KRACK2 Glorious | Marlette Mahan krack BT AND THE PASTIES pmadden ercan caner |
* Competitors who were not eligible for prizes were not ranked
Problem Statements
Problem1.pdf - Problem2.pdf - Problem3.pdf - Problem4.pdf - Problem5.pdf - Problems1-5.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 -
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.
2329 - 2729 - 5333 - 5626 - 6402 - 7893 - 8109 -
Summary
| Contest Number |
BUT1 |
| Date |
May 6th, 2008 |
| Location | Binghamton University, Room AAG004 |
| Sponsors | Bloomberg |
| Number of problems |
5 |
| Number of competitors |
~29 |
| Registration time |
7:45 PM |
| Contest start time |
8:00 PM |
| Contest end time |
10:00 PM |
| Supported Languages |
C/C++, Java, C#, and Python |
| Timeout period |
10 seconds |
| Prizes |
First Prize: $45 Amazon Gift Card Second Prize: - $30 Amazon Gift Card Third Prize: - $15 Amazon Gift Card |
| Other Prizes |
- |
| Food and beverage |
Pizza, Soda |