Local Contest - October 2nd, 2004
Division 2 was open to any students currently enrolled in CS1073/1083. Only a few students chose to participate, but many of them had only been in university for approximately 4 weeks. Each student was given 14 word problems and 5 hours in which they had to come up with explanations, pseudocode, mathematical proofs, or possibly a mathematical expression. Some of the problems were extremely difficult, but all the judge's (Professor David Bremner, Professor Joe Horton, Nathan Scott, and Sean Falconer) were surprised and delighted with how well they did and how unique some of their solutions were. Below is the list of the division 2 winners:
- Ian Sawlor - 8 problems solved
- Yinam Zhang - 7 problems solved
Click here for the division 2 problem set and here for the scoreboard. Below is the list of the problems with their solutions.
- Rectangle in a Rectangle - Anything similar to this:
if(Bx1 >= Ax1 && By1 <= Ay1 && Bx2 <= Ax2 && By2 >= Ay2)
was accepted. Basically, you just needed to explain how to tell if rectangle B was within/on rectangle A.
- Swapping Numbers - There's a few different ways to do this problem, but probably the simplest way is the following:
a = b + a;
b = a - b;
a = a - b;
- Team Selection - The answer is: 7770. This problem is actually quite difficult, and I probably shouldn't have put it as the third problem as it involves math that most first years probably have not seen.
- What's Wrong - This problem is reasonably simple, but the big formula probably scared some away. The reason the program crashes is because the lines are parallel, meaning they won't have an intersection point, causing a division by zero in the equation.
- Picnic Baskets - Everyone solved this, yay! It's a typical logic puzzle that you'll see sometimes in job interviews, IQ tests, or logic books. You need to get two bits of information by making only one choice, the only way to do that is by selecting a fruit from the basket labelled Apples and Oranges. There are two possibilities:
- If it's an Apple, then you know that basket contains Apples. Since every label is wrong, the basket labelled Oranges cannot contain Oranges, therefore it contains the mixture and the basket labelled Apples must contain Oranges.
- If it's an Orange, then you know that basket contains Oranges. Since every label is wrong, the basket labelled Apples cannot contain Apples, therefore it contains the mixture and the basket labelled Oranges must contain the Apples.
- Open Water - Only one person got this problem, and his solution was really unique. The problem originally started out as a classic computer science problem: given a singly linked list, and two pointers, how can you tell if there's a loop in the list? Now, since no one competing in this division would know what a singly linked list is, we tried to write it in a real world context, however, when we did that, we made the problem considerably simpler. If you draw out the description of how the buoys attach, you'll realize that the only way to have a loop is if the buoys make one big circle. Therefore, if you simply send Fred and Dave swimming in opposite directions, they'll either meet eachother, or hit the end of the buoys. Another solution is to have Dave swim two buoys for every one Fred swims, timing the starts with their watches, if there's a loop, Dave will catch up to Fred. The solution we received was to tie the watch around the buoy rope, and swim in one direction, if there was a loop you'd see your watch again, otherwise you'd hit the end of the rope.
- Cable Car - This problem is kind of tricky, the obvious solution has a total time of 19 minutes, but the minimal solution is 17 minutes. I'll put up the sequence of movements to make 17 minutes as soon as I find it :-).
- The Eternal Triangle - No one tried this problem, which isn't that surprising since most of the competitors have probably never done proofs before. Here's Joe's solution, but there could be some variation.
Consider one of the people. Call him X. There are five other people. Suppose he knows three other people, call them Y, Z and W. If two of these know each other, say Y and Z, then X, Y and Z all know each other. Otherwise Y, Z and W do not know each other. Thus if there is no triangle, then X does not know three of the people. Therefore there must be three people of these five that he does not know. Call them A, B and C. If two of these people do not know each other, say A and B, then X, A and B all do not know each other. Otherwise A, B and C all know each other. In all cases, either three people all know each other or three people do not know each other.
- The Maze - There's more than one solution to this problem, but one way to do it is to use the pencils as arrows marking the leaving and entering of intersections, and perform depth first search. I think everyone that solved this problem basically described something similar to this where they gave a description of how to perform a depth first search.
- Choosing Coins - There was a lot of debate among the judge's as to how to solve this problem and what an acceptable solution was. Basically, the judge's decided to accept any solution that did not involve counting the coins, but guaranteed a random selection.
- Shuffle it to the Man - There's more than one way to solve this, but here's the judge solution:
for i=1 to 19
j=random(i+1 ... 20)
- Clean Up After the Jerk - Answer: some sort algorithm. The solution to this problem would be reasonably obvious to anyone in their second year of CS, however, none of the competitors had seen a sort algorithm before, so the one person that solved this problem, reinvented the Insertion Sort.
- Clean Up After the Jerk v2.0 - Answer: merge sort. No one solved this, however one person was very close. The solution involved reinventing the merge sort algorithm if you'd never seen it before. With merge sort, you split the number of boxes in half, and then for each half, you split those in half, and then for the quarters, you split those in half, until each box is by itself. Then, you merge the boxes back together in the reverse order that you split them while sorting each merge. This results in a lot less uses of your handheld device.
- Man Overboard! - Answer: The length of the minimal path to guarantee you hit shore is: sqrt(3) + 1 + (7/6)pi kilometers. Coming up with this answer is extremely difficult and not obvious. There was a ton of submissions on for this problem, and a few interesting answers, but nothing close to the minimal path. Some of the answers would have guaranteed that the person finds the shore, but they were not the minimal path.