1. Skip to Menu
  2. Skip to Content
  3. Skip to Footer>

2nd Annual UAkron Programming Competition: Problem Set & Results

The 2nd Annual University of Akron Programming Competition took place on Saturday, April 30th, 2011. There were 6 teams in attendance made up of current UAkron students (although we’re considering opening up the event to other schools in the future). My responsibility for the event was writing the problem set and judging proposed solutions. The problem set can be found here:

Revised Contest Problem Set

I’ll give a bit of background on the problems here. This may contain spoilers, so if you want to work on the problems you may want to skip the rest of this post. These explanations assume you’ve read (or at least looked at) that problem.

Problem A: Overlapping 2D Barcodes

   Difficulty: 1/5, Solved by 6/6 teams

This problem is pretty straight forward, and mainly involves nested loops and checking individual characters within a string. This problem was solved by 6/6 teams.

Problem B: Randomly Evaluated Boolean Expressions

   Difficulty: 5/5, Solved by 0/6 teams

This is one of the hardest problems in the set. The root problem is considering all of the full parenthesizations of a boolean expression and figuring out how many of those parenthesizations return True. Here are a couple larger examples than the problem description provides:

Input: return T or F xor T and F xor T or F xor T and F and T xor F or T or T or F xor F and T xor F;
Output: 7161517 of 9694845

Input: return F xor T and T xor F or F or T xor T and T xor F xor T xor F and T or F and F xor T and F and T xor F or T and T xor F and F and T xor F and T xor F xor T and F and T xor F and F or T xor T xor F or F or T;
Output: 2288490719605020900 of 3116285494907301262

The problem also involves utilizing randomly evaluated local variables as part of the final return statement, rather than just returning a statement full of constant T / F values.

Boolean a = T xor F xor F xor F and T;
Boolean b = T and F or F;
Boolean c = T and T xor b and b xor T and F;
Boolean d = a or c or F or F xor b xor c;
return c and d or d and T and F;
197061645695975424 of 2591129315051569152

The efficient solution involves Dynamic Programming and is O(n^3) where n is the number of terms in the Boolean expression.

Problem C: Long Division

   Difficulty: 3/5, Solved by 1/6 teams

This problem mostly involves output formatting and bookkeeping as you must emulate the full process of long division, and there are many places that formatting errors can creep in if you aren’t careful.

Problem D: Heart Monitor

   Difficulty: 1/5, Solved by 6/6 teams

This is one of the two “easy” problems in the set (along with Problem A). The only real problem encountered by teams was not following the definitions of “impossible” and “concerning” heart rates precisely.

Problem E: Inverse Function Domains

   Difficulty: 4/5, Solved by 0/6 teams

This is an interesting problem, and a bit trickier than I thought when I was originally writing it. I originally thought you could just sort the incoming points by x value, then travel the function marking y values as hit every time a line segment went through that y value. This almost worked, except for the case of {(0, 1), (1, 0), (2, 3), (3, 2)} which results in the open interval (1, 2), but this is missed if only integer y values are tracked. Updating the solution to keep track of *.5 values solves this issue, at which point it becomes a matter of formatting the output with proper set notation.

Problem F: Late For the Final Exam

   Difficulty: 5/5, Solved by 0/6 teams

This is the other crazy problem in the set (along with Problem B). It’s a “shortest path” problem when driving between points on a directed graph (in the Cartesian plane). The catch is that there is a speed limit, rate of acceleration & rate of deceleration, and a maximum speed at which turns can be navigated (full speed at a <10 degree turn, full stop at a >90 degree turn, and a linear relation between 0 and full speed between 10 and 90 degree turns). Figuring out the minimum drive time between two points in the graph involves not only a graph traversal and calculation of maximum turning speed at various angles, but also the amount of time required to navigate a segment of road given the road length, starting speed and maximum ending speed (which may or may not be achieved). It ends up involving a reasonable amount of algebra and to calculate these times.

Problem G: N Degrees of Ashton Kutcher

   Difficulty: 2/5, Solved by 1/6 teams

This is a fairly simple graph problem. The only awkward part is input reading because people are introduced during the descriptions of other people, so they may not have an ID yet (depending on the implementation).

This entry was posted in Programming Contests. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *


You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>