Saturday November 11, five students from UCSB drove into Riverside, three of which emerged (somewhat) victorious and each $50 richer. This entry chronicles the events leading to and during the 2006 Southern California Regional ACM programming competition.
I mentioned the upcoming competition in my Line Segment Intersection Algorithm post which was the start of my preparation for the contest. Further preparation did not come until two nights before the competition as we are lazy Santa Barbarians. Adam and I managed to talk Scottie into participating with us thus giving us the house advantage as we all live together. We originally registered four teams however only five people attended giving us two teams, Bender and Morbo named appropriately after Futurama characters.
The Night Before
In a traditional UCSB Friday night Scott and Adam partied though managed to
make it home well before the normal return time; I abstained Friday night
because I like to be well rested before day long events.
The Next Morning
In a nontraditional UCSB morning the three of us woke up at approximately
6:45 to leave by 7:45 for the 2.5 hour drive to Riverside. One thing that must
be noted here is that the official check in was between 8 and 9 which we
definitely weren’t planning to attend.
Showers and a quick trip to McDonald’s prepared us for the day and put us on the road by 8:00. We sang songs for two and half hours and finally arrived at 10:30. Surprisingly our other team with our coach arrived within two minutes of us despite our unsynchronized departures. The six of us rolled in and tried to find the check in booth but of course being late the booth was gone and special accommodations were needed to get checked in. With all that squared away Scotty, Adam and I completed the practice problem in 15 minutes and headed out for lunch. Oddly, to us, we were one of the first teams there for lunch despite the other teams’ head start at the practice problem.
Lunch
Lunch was exciting. Rather than planning strategy and preparing our minds for
the upcoming five hours of work we joked with Tim (our coach) about future
years’ strategies. We came up with one brilliant plan, among other not so
brilliant ones.
The plan involves a team of strippers, or rather a team of some of UCSB’s finest since the majority of our female class would make excellent strippers. Throughout the competition these girls will cat fight and perform titillating dances so as to distract other teams. They may even go so far as to flirt with the competition. We being used to this, as it occurs all the time in our natural environment at UCSB, will gain an upper hand and emerge victorious.
The Competition
The competition started a half hour late due to technical difficulties. The
words starting the competition were, “You now have five hours,” which me
immediately joked as five hours to figure out how to open the packet, and the
woman guarding the printer from code thieves chuckled. Once the packet was
opened we took our places with Adam at the keys and Scottie and I yielding pen
and paper. After reading through the packet of seven problems I began solving
the fifth problem which was a nested box problem. This problem involved
figuring out the maximum number of boxes that can be nested in a given set of
boxes. I quickly recognized this as a dynamic programming problem and hacked
away at the code for it. I passed it off to Adam who had just completed our
programming environment setup. He typed it up, tested it and submit it for a
success on first submission.
Meanwhile Scottie began working on the third problem which involved calculating how to order pages when printing a booklet, and in the down time Adam began solving the second problem which was determining the best percentage one could get in a class by dropping one, two or three grades.
After the fifth problem was solved I began working on the first problem as it didn’t involve designing an algorithm, but rather just making simple math calculations with a very complicated problem description. We typed this problem up, submit it, and went for a break which occurred 2 hours into the competition.
Upon our return we were all cheers as the solution to the first problem was correct. Scottie continued working on the third problem as he was floating around a correct solution, and Adam was close to completing the second problem. That left problem four, six, and seven for me to look at. I chose the fourth problem which was a special program this year that involved interaction with another program.
The fourth problem titled Uniclue was a simplified version of the game Clue, in which we only had to come to the correct accusation in under 47 turns. There are only 18 cards in clue which need to be accounted for before making an accusation thus making the problem quite simple. I wrote the pseudo code for this, and handed it off to Adam, who by this time had programmed a solution for the second problem.
My code had a few mistakes but with some solid debugging skills we were able to quickly fix the mistakes and submit for a correct answer. With less than an hour left and one problem just about correct we decided to assist Scottie in finding the correct answer for the third problem.
It turns out we had interpreted part of the problem wrong and were trying to correct something that didn’t need to be corrected. Upon realizing that we knew our initial solution was wrong for some number 1-200 and started checking each of those (something we should have done initially). As a shot in the face the problem occurred when ‘1’ was entered. A one line fix gave us the correct solution and rights to pick on Scottie for a few months.
Getting the correct answer on this problem had jumped us up to fourth place from sixteenth or so, and with only fifteen minutes left in the competition we rolled out, feeling victorious and singing “Olay, Olay Olay Olay! Gauchos! Gauchos!”
We now had to wait approximately an hour to see how far we were bumped down. Finally it is announced, “Fifth place goes to UCSB Bender.” Maholler!
As it turns out we do alright without a team of strippers, but it’s still a brilliant plan.
Comments
comments powered by Disqus