UNB's first ever undergraduate programming contest was a huge success. The competitors were given 7 different problems of varying degree of difficulty and given 5 hours to try and solve as many as possible. Almost all the competitors solved atleast one problem, and one student (Aaron Small) managed to solve all 7 with just 4 minutes to go in the contest. All but three of the competitors had never been in a programming contest before, so everyone did very well.

Nathan Scott and Sean Falconer would like to thank the competitors for participating. Also we'd like to thank professors Natalie Webber, Ken Kent, and Joe Horton 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. Almost all the issues were due to inexperience, not ability, we're sure our next contest will have even better results. Go here for a copy of the problem set, judge's solutions, and judge's I/O.

• A. Campus Speeding - This problem is probably the easiest of the set and most competitors solved it without problems. The only small issue we noticed with a few competitors was that they forgot to process multiple test cases or did not properly format their output. All that was really required of this problem was to properly proces the input. The judge's solution reads in the number of cases, then for each case reads in the speed limits, then reads in each vehicles speed and compares their speed with the speed limit. If it's above the limit, then they are speeding.
• B. So Who Won? - This problem had the most wrong answers. Nathan originally designed it to be a straight-forward problem that anyone could get, but we underestimated some of the ambiguity that arose during the competition. The main issue was that most competitors did not realize that a competitor may have no accepted solutions, this results in an input value of "name" -1. This caused most people's programs to run forever or spit out something wrong. The other issue was not properly processing multiple inputs.
• C. Data Classification - This problem was actually probably the easiest problem in the set, but only 4 people attempted it. All 4 people that did it were rewarded with an accepted solution on the first or second try. The math formulas are only there to scare people away, but if you take the time to read the problem, all that is required is to multiple numbers together and determine which one is the largest. The lesson here is that scary problems are not usually as bad as they seem and sometimes friendly looking problems aren't so nice.
• D. Balloon Collecting - A lot of people tried this problem, but I think only two solved it. It looks like an easy problem, but it's actually more difficult that it appears as it requires an efficient solution. Most people were getting time limit exceeded or memory runtime errors. There's a note at the end of the problem that warns people that they need an efficient solution to solve the problem so we thought this might prevent some people from trying naive solutions. This problem is actually a very common type of Dynamic Programming problem that most people who have taken Algorithms would have seen. You have to find what is known as the Longest Decreasing Subsequence. There's a very efficient solution to finding this, check the judge's solution for code.
• E. Selbat H. Turt - Only one person tried this problem and he solved it on the first try. The problem looks a little scary because of the diagrams and also the fact it's talking about reversible logic which is a topic most students are not familiar with. If you take the time to read the problem carefully, all that is required is for you to read in the input, build a data structure that emulates the given gates, and then simulate the transition of various inputs to their outputs. The gates simply invert the bits provided their indicated control gates are set properly. This is a very good problem to try if you are interested in programming contests. Simulations are a very common type of problem.
• F. The Kings of Mesopotamia - Several people tried this problem, and a few people were close to a correct answer, but only one or two people had their code accepted. Originally, the problem did not include the area formula or the hint about how to figure out if a point is inside a triangle, but we decided to make it easier. All that was really required to solve this problem was to read in the input into some sort of point structure, and then try building triangles out of all the points. For each triangle, calculate its area, see if any other points were in it, if not, see if its area is larger than the current best triangle, if so, that's your new best triangle. To tell if a point is inside a triangle, you can build 3 triangles between the vertices of the triangle with the point. For each of those triangles, calculate their area and sum them, if their summed area is the same as the original triangles' area, then the point is inside the triangle, otherwise it is not.
• G. Princess Penelope - Only one or two people solved this problem. Most people that attempted it, either had answers that were only partly correct or their program ran forever. The running forever was probably a result of not properly handling the input for multiple test cases. There are multiple ways to solve this problem, but the judge's solution solves the problem by doing breadth first searches over each map where a grid cell represents a piece of land and has not already been counted. The search returns the size of the connected component, and if that component is larger than the current largest component, update the biggest component variable. Breadth first search is a very common algorithm for solving different types of problems. Graph problems, games, and searches are very common in these type of contests.