BC Winter Programming Contest

The BC Winter Programming Contest took place this past weekend, January 16th. You can check out the scoreboard here. It was an excellent competition, only one student, Jaehyun Park from Stanford, solved all 7 problems, and almost all students solved at least one. Brad Bart from SFU did most of the work to write problems, solutions, and organize everything. Sonny Chan (coach of Stanford) and myself made small contributions with some solution validation, test case generation and I wrote one of the problems.

There were 5 pairs of UVic students competing and one UVicer competing remotely while on co-op with Research in Motion in Waterloo, ON. The top UVic team was Dan Sanders and John Hawthorn with 4 problems solved. They finished 6th overall and were the 2nd overall amongst BC students. They were in 3rd or 4th about half way through the competition, but got stuck trying to debug wrong answers on problems C, D and F for the second half of the competition. In the last half hour, students from SFU solved their 5th problem and jumped ahead of them. Scott Porter, competing remotely by himself, was the second top UVic student, placing 20th overall.

Many of the UVic students that participated were completely new to competitive programming. They had really no idea what to expect, so I would like to congratulate all UVic students that came out and gave it a try. These competitions can be very intimidating and stressful the first few times, so I’m really proud of everyone that stuck it out for the full 3 hours. Hopefully you’ll keep practicing and compete in the ACM competitions next Fall.

Problems:
A – This was the simplest problem in the set. You had to read in words and determine whether they were writable in Hawaiian. This amounted to determining whether the word contained only letters from the Hawaiian alphabet. The catch for some solutions was not properly handling the stopping condition. The problem states that the last test case ends with the exact string “Ahuihou”. Some students matched against this word ignoring case, which is wrong.

B – In this problem you have to read in a number, up to 30 digits in length, and determine what bases it can be rewritten in such that it is evenly divisible by 7. If the number is never divisible by 7, you have to print “Always unlucky.”. It turns out that you only need to test bases up to base 16. All other valid bases will be one of these bases plus Y*7 (Y >= 1). For example, if base 9 works, then base 16 works, 23, 30, etc. You can easily do this in Java using the BigInteger class. Python probably also has something equivalent.

C – This was the hardest problem in the set, and only one student managed to successfully solve it. You are given a grid of diamond shaped cells. You are also given a metal detector that can probe a gridsquare and give you one of 8 compass directions. Compass directions North, East, South, and West are only valid responses if the treasure you are hunting is located along that exact path. Otherwise, you get a direction like Northwest that simply narrows your search to a region of the grid.

You can solve this problem using dynamic programming or memoization. A sub-problem can be described by the grid size, m and n. However, there are some tricky conditions for the recursion for certain values of m and n.

D – This is the problem I wrote. The problem describes a game with colored marbles on two tracks, one horizontal and one vaertical. You can rotate either track to move marbles from one track to the other. You are given an initial configuration of the tracks and you have to figure out the minimum number of moves (i.e. rotations) such that you get all the blue marbles into the middle square. It turns out that there’s not that many valid starting configurations.

One approach to solve the problem is to start by representing the winning condition as two bit strings of length 18, “111100000111100000” and “100000111100000111”. Then using these strings as a representation of state, you can breadth-first-search across all possible valid moves to generate any potential starting position that takes one move to reach the winning state. Continue to do this for all of these states to get all configurations 2 moves away. Do this until you can’t find any new states and store everything in a table. You can now simply look-up the answer based on the read in configuration. If the given starting configuration does not exist in the table, then it is impossible.

E – In this problem, you are told that two flat oranges rest at the bottom of a fruit bowl shaped like a parabola. You have to determine at what value of y the fruit’s centers are located at. Applying some geometry, you can work out an equation to calculate y given some “guessed” value for x. To guess a value for x, we can use binary search and terminate when the high and low value become significantly close.

F – This problem describes a bad measuring device that is only precise within 1 foot. So any measurement has value V feet plus or minus 1 foot. The distance between floors in a building are measured with this device and you have to determine whether these measurements are consistent or inconsistent. Consistent means that the measurements are possible, inconsistent means that there’s no way they could be right, there is some sort of conflict between two or more floor distances.

We can represent this problem as a graph. All floors represent nodes in a graph and two floors, a and b, have directed edges between them if there is some measurement d given in the problem input. The edge from a to b can be assigned weight 1-d (the minimum possible value) and b to a has weight 1+d (the maximum possible value). Once the graph is constructed, the measurements are consistent provided there are no negative cycles in the graph. To detect negative cycles, you can apply the Bellman-Ford algorithm.

G – This was the second easiest problem in the set. You are given numbers that represent the values of odd-indexed nodes in a full binary tree. You have to figure out the values to the even-indexed nodes. You can represent the tree using a one-dimensional array. Most people learn this in undergraduate data structures courses. Then it’s just a matter of filling in the array, where you use the odd-indexed values to calculate the even-indexed values. Instead of an array representation, you could also implement your own binary tree with left and right nodes, and apply recursion to fill in the tree.