

Local Contest  March 13th, 2004
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 straightforward
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.

