UNB's second annual undergraduate March competition was not quite as successful as the previous competitions held in October and March of 2004. This was partly due to the contest being held on a Sunday, rather than a Saturday. A lot of students were not able to compete due to mid-terms scheduled for Monday. Also, the problem set was much more difficult than the previous two competitions, which made it difficult for first and second years that had never competed before to solve any problems.

The format of the contest was similar to the previous undergraduate competitions. Each competitor was given 7 problems and they each had 4 hours (rather than the usual 5) to attempt to solve as many as possible in the shortest period of time. There was great back and forth action between Nathan Scott and Aaron Small. Nathan jumped out to an early lead, solving the first 2 problems in 27 minutes, while Aaron received a wrong answer on problem E. At the 61 minute mark, Aaron solved his first problem (question A). Aaron, then jumped ahead of Nathan by solving B and E, while Nathan received a wrong answer on C and D. Nathan finally had D accepted, and jumped into the lead again. Aaron solved D 13 minutes later, and took the lead once again. Then, just 14 minutes after, Nathan solved E, and retook the lead. Aaron fought back by solving F and then C, while Nathan received a wrong answer on F. Aaron, now with 6 problems solved, moved onto the last and hardest problem. Nathan quickly fixed F, but Aaron was still one problem ahead. At the 190 minute mark, Nathan had C accepted and jumped into the lead for the final time. Both Aaron and Nathan submitted G several times, but neither managed to find the correct algorithm to get under the judge's time limit. The contest ended with both Nathan and Aaron solving 6 of 7 problems, but Nathan had a total time of 679 minutes, while Aaron had a total time of 722 minutes. It was a great effort by both competitors.

• 1st year winner - Nicholas Doyle
• 3rd year winner - Trevor Bernard
• 4th year winner - Nathan Scott

Overall winner was Nathan Scott, and second place overall went to Aaron Small.

Sean Falconer would like to thank the competitors for participating. Also I'd like to thank Natalie Webber, Ken Kent, Joe Horton, David Bremner, and Tom Robichaud for all their help with running/organizing the contest, getting prizes, printing, and suggestions about the problem set. Finally, we'd like to thank Sean Seeley for providing the Unix accounts for the competitors, setting up printing, and taking care of some other technical details.

Below is a list of the problem set with a brief overview the algorithms necessary to solve the problems. Go here for a copy of the problem set, judge's solutions, and judge's I/O.

1. Beat the Devil - This was probably the easiest problem in the set, although some people may have found problem B more straight-forward. In retrospect, this was a bit too difficult to be the easiest problem. To solve the problem, you really just need to read the description and understand how the game is played. After that, you just need to write code to simulate the game play, which can be done by using an array of size 8 to keep track of the piles. You only need to look at the card values, not the suit, when making a match.
2. Part of speech tagging - This is kind of a typical programming competition problem that involves input parsing and some output formatting. The biggest problem people had was with the output format. We were reasonably lenient with respect to extra lines in the output, however, the tags had to be in the correct position. To solve the problem, you just need to store the dictionary words, and parse the input, word by word. With each word, check the dictionaries to see if they exist in any, if they do, append the appropriate tag.
3. Factorials and exponents - This is the first problem of this type that we've ever used in one of our local competitions. The problem involves almost no coding, but it requires a little math incite with logs to realize how to solve the problem efficiently. Unfortunately, only two competitors figured out the trick to solve the problem.
4. Can you win the game? - Again, only two people attempted and solved this problem. All that was required was to try all possible rotations of the octagons to find a winning match, if none exist, then you can't win the game. You can try all possible rotations by backtracking, or by coding 6 embedded loops, each ranging from 1 to 8, to try all possible octagon sides.
5. Subsequences - There was only two accepted submissions on this problem, however, 4 people attempted it. If you know the 2 dimensional solution for LCS, then this problem is a straight-forward extension of that solution. Some people didn't realize this, and thought the problem could be solved by some other greedy-like algorithm, but unfortunately, that will not work.
6. Building teams - There's two "tricks" to solving this problem. The first is to realize that it's just a form of graph coloring and the second is to realize that you don't need to care about the students, only the cliques matter in the graph representation. You know that some cliques do not like other cliques, so if we consider each clique as a node in the graph, we draw an edge between cliques that do not like eachother. Once the graph is completed, we want to paint the nodes, such that no two adjacent nodes have the same color (i.e. they are on different teams). You can do this by backtracking, that is, trying all possible colorings.
7. MTV slaverly - No one solved this problem, which wasn't that surprising, it was BY FAR the most difficult problem in the set. The problem is an instance of weighted bipartite matching. You want to match planes to locations, such that, you minimize the overall total distance travelled by the used planes. Both Nathan and Aaron attempted this problem, but they could not get their solutions in under the time limit. My solution involves using the Ford Fulkerson maximum flow algorithm, but instead of finding augmenting edges with DFS or BFS, I use the Bellman Ford algorithm.