UNB's second ever programming competition was even more successful than last March's. This time, we had two different divisions, Division 1 and Division 2. Division 1 was for the regular programming competition, where students were given 8 problems and 5 hours to solve as many as they could in the least amount of time as possible. Below is a list of the division 1 winners:

• Aaron Small - 5 problems solved
• Jordan Bramble - 4 problems solved
• Nicholas Doyle - 4 problems solved (in more time than Jordan)
• Tom Robichaud - 3 problems solved

Nathan Scott and I (Sean Falconer) would like to thank the competitors for participating. Also we'd like to thank professors Natalie Webber, Ken Kent, Joe Horton, and David Bremner for all their help with running the contest, getting prizes, printing, and suggestions about the problem set. We'd also like to thank Tom Robichaud for setting up the judging software and helping with the user accounts. 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 of what the common problems people had with getting an accepted solution. Go here for a copy of the division 1 problem set, judge's solutions, and judge's I/O.

1. Pirate versus Ninja - This problem was the easiest of the set, and we had 8 accepted submissions for it in the first 20 minutes of the contest. Only a few people did not have it accepted on the first try. There's more than one way to do it, but one of the simplest is to simply simulate the hits until either the pirate or ninja's health is down to zero. At this point, output the winner and his/her health.
2. Text Books - This problem had the second most solutions to problem A. The major issue with this problem was to properly parse the input and also to catch the case where someone cannot fullfill an order, and they storm out, meaning you had to back track whatever books you had already allocated to them. Remember, it is always important to read the entire problem description. Other than these two issues, all that was required was the simulate the purchase of the books and keep track of the minimum cost of the books.
3. Most Interesting Problem Ever - Surprisingly, there was only one accepted solution to this problem. The problem was reasonably straight forward, but required some concise coding to get all the commands programmed correctly. The problems most competitors were having was with either not ignoring invalid commands, not processing the input correctly, not outputing the table in the proper format, or not realizing that indexing for the rows and columns starts at 1; therefore, if you allocate a 100 by 100 matrix and do not decrement the commands rows and columns, your program will crash when trying to index something outside the bounds of the array. The program does not require as much code as some thought, my judge's solution only has 192 lines, which is fairly long for a contest, but not extreme.
4. Caesar Cipher Madness - This problem is less daunting than most people realized. The top four competitors figured out the trick with it, and we hoped others would give it a second look because the solution is very simple and requires little code. The trick is that a multiple caesar cipher is not anymore secure than a single caesar cipher. Using multiple keys to encrypt the same message over and over, is the same as adding up all the keys and moding them by 26, and using that value to encrypt the message once. Since the problem says to maximize k, and minimize the other two variables, all you need to care about is k. The other two variables are always going to be 0 and 1, so all you need to do is try all possible k's from 0 to 25.
5. Magic Squares - No one solved this problem, and we had only one submission, which received a TLE. The trick is to realize that by using the 1 to 9 solution of a magic square, you can figure out the missing values for larger magic squares. There's only one 1 to 9 solution, all others are equal through a rotations and flips. Given an unknown square, you know the values have to be consecutive, so by trying all rotations and flips of the 1 to 9 solution, you compare the known values to how they match up to the 1 to 9 solution. If each known value is an equal distance from the 1 to 9 solution, then you can figure out the rest of the numbers by adding that distance to the 1 to 9 solution. For instance, consider the 1 to 9 solution given in the problem:

   8	1	6
   3	5	7
   4	9	2

   
   If you were given:

   19	12	X
   14	X	X
   X	X	X

   
   Then, 19 - 8 = 11, and 12 - 1 = 11, and 14 - 3 = 11, therefore, by adding 11 to the rest of the 1 to 9 spots, you can figure out the missing values to the unknown magic square. The solution is not always going to line up so nicely, so sometimes you'll have to try rotations and flips. There's a simpler way to solve the problem without writing rotation and flip code, but I'm not going to explain it here.
6. The Wireless Network Problem - Four people managed to solve this problem, and aid me in my attempt to get better wireless coverage in St. Stephen. The problem is reasonably simple if you figure out that in order to tell how many stores are covered in the downtown area, you simply count how many stores are within all four router station circles. So, for each point, do the point in a circle test for all four circles, if it is within all of them, count it as in the downtown area. Afterwards, divide the number of stores in the downtown area over the total number of stores, and print out the appropriate message. There's a slight ambiguity with the problem for the case where there are no stores. Everyone that had their solution accepted said that "The wireless coverage still stinks, but good enough for now.", however, my solution says "St. Stephen needs new equipment.", either answer was acceptable.
7. Double Checking - Only two people attempted this problem, and there was one accepted solution, although the second submission was extremely close. In my opinion, the simplest way to solve the problem is to build the tree by recursively parsing the output. Afterwards, do the binary search tree check by recursively checking left and right subtrees. If that passes, do the AVL tree check by recursively checking left and right subtree heights. If both pass, it's an AVL tree, if the first passes but the second fails, it's a binary tree, otherwise it's an ordinary tree. The accepted solution actually figured out the tree properties as the tree was parsed, which makes the solution slightly faster, but rather messy :-). Bye the way, you'll probably see a problem like this in CS3323 (data structures).
8. Candy Machine - No one solved this problem, but a lot of people used up most of the contest time on it. I was hoping that people would realize it wasn't as easy as it appeared to be since it was the last problem in the set and I said that the problems were roughly in order of difficulty. Also, after several people had over 5 wrong submissions, I was hoping some people would move on, and some did, but others still continued on it. The problem is actually rather difficult, and involves algorithmic ideas students usually do not see until their third or fourth year of CS. I think everyone that attempted it tried a greedy solution, which is the obvious way, but wrong way, to do it. Unfortunately, the test cases in the sample I/O can be solved using greedy, I didn't realize this when I made them up. Now, in a regular contest, you may want to try greedy on something like this because it doesn't take much time to code, and you might luck out, however, if you get several WA's, your algorithm is probably wrong. To solve this problem, you have to use a technique known as dynamic programming or recursion with memoization. My solution uses recursion with memoization, because it's easier to code :-). The reason you can't make local optimal choices as in greedy is because there could be cases where you'd want to put a dime and 3 pennies in the machine to get a nickel back, in this case, you aren't making a local optimal choice, but a global one.

   If you look at my solution, you can see me recursing on all the possible ways you'd want to use your money, and storing the best solution in a 3 dimensional array. I store them this way, because this saves time in the recursion if I've already seen some solution before. There are different ways to reduce your change to the same values, meaning if you don't store the solutions, you'll be figuring out the same stuff over and over again and run out of time to solve the problem.