27th Annual Spring Programming Contest
The 27th Denison Spring Programming Contest was held in the F.W. Olin Science Hall on Saturday, February 27th. There were 15 teams from 6 schools (Baldwin-Wallace College, Denison University, Muskingum University, Oberlin College, Ohio Wesleyan University, and University of Akron). The top three teams from first to third were:
- Bijective Isomorphisms (Drew Lytle, Andrew Read-McFarland, and Jessica Tang) of Denison University solving all six problems.
- qUArk (Cody Skala and Michael Wilder) of University of Akron, solving five problems
- ThirdThree Whales! (Trevor Masters, Taylor Kessler Faulkner, and Paige Vosmik) of Denison University solving five problems.
All problems were solved by at least two teams and all but two teams solves at least one problem. Associate Professor Ashwin Lall of the Department of Math and Computer Science at Denison University organized the event. Thanks to him and everyone else who made this such a successful event.
Wondering what types of problems they solved? Try you hand on the two samples below.
Problem E: Onesies Twosies
Erin doesn’t like doing laundry. She wants to dress her baby in as many matched onesie and pant combinations as possible (wearing each article of clothing at most once) before having to do a wash. The catch is that not every onesie and pant pair match and she doesn’t want to take her baby out of the house looking like her dad dressed her.
For this problem, you have to determine the size of the largest collection of pairs of onesies and pants such that each pair is matched and none is used more than once.
For example, if we have that onesie 1 matches pants 1 and 2, onesie 2 matches pants 2 and 3, and onesie 3 matches pants 2 and 3 (see figure below), then Erin can dress her baby in three non-overlapping outfits without doing laundry by matching 1-1, 2-2, 3-3 (or 1-1, 2-3, 3-2).
Problem F: Pandemic
In the board game Pandemic LegacyTM, you have a number of connected cities in which you are trying to stop the spread of deadly diseases. Any time a city that already has three disease cubes gets infected, it has an outbreak and brings you closer to losing the game. When an outbreak occurs, all the cities connected to the outbreak city get infected, adding another disease cube if it has fewer than three or causing an outbreak if it has three. This can cause outbreaks to cascade across the board in a chain reaction. To protect against outbreaks, players can choose to “quarantine” one city each turn; this prevents that city from having an outbreak. In this problem, you will determine which city should be quarantined.
At the beginning of a turn, each city has between zero and three disease cubes in it. During the turn, the player can put a quarantine on any city on the board. At the end of the turn, a disease cube will be added to a random city, so it is important to place the quarantine strategically.
When an outbreak occurs in a city, the infection is spread to all the cities it is connected with that have not had an outbreak yet this turn. Note that a city can only have one outbreak per turn, preventing indefinite chain reactions. However, it is possible for a city to get multiple disease cubes in a turn. Consider the following example:
Suppose an outbreak hits London. This causes outbreaks in Essen and Paris. The outbreaks in Essen and Paris both cause cubes to be added to Milan (which will now have a total of 3 cubes). Note, however, that the outbreaks in Essen and Paris don’t cause outbreaks in London or one another again (since they have all had outbreaks this turn). Hence, there will have been a total of three outbreaks from London getting hit.
If Essen gets hit first, then there will be outbreaks in London and Paris, also for a total of three outbreaks. Similarly, Paris will cause three outbreaks. Milan getting hit doesn’t cause any outbreaks since it only has one cube.
Your goal is to determine which city would cause the largest number of outbreaks if it gets hit at the end of the turn. This is the city you’d probably want to quarantine.