Last Saturday, the two UVic teams participated in a practice session with teams from SFU, UBC, and Columbia university. Columbia was first overall with 6 problems solved, and two individuals from UBC also solved 6 to claim second and third.
We had a bit of a rough start as some UVic team members were locked out of the building and arrived late. Also, the top UVic team was missing a member and the other team had one member that had never competed before. The top UVic team solved 5 problems and finished 5th overall, just being edged out by SFU’s top team, that also solved 5 problems. The second UVic team solved 5 problems, but finished 10th overall.
A lot of teams managed to solve 5 problems, as there was 5 reasonably easy and short to code problems, and then 3 hard problems. Of the hard problems, all of the teams to solve 6 solved problem G from this problem set: http://cs.stanford.edu/group/acm/SLPC/problems.pdf
Problem G is identical to problem F, except that there are far more rectangles. You can solve F with a straight-forward N^2 implementation of the standard dynamic programming solution for longest increasing subsequence. However, problem G requires an NlogN solution as there are as many as 100,000 rectangles. There is a known NlogN solution for solving the longest increasing subsequence problem, however, none of the UVic students knew of this algorithm. It may also be possible to implement enough short-cuts in the N^2 solution to drop it down under the time limit.
The two unsolved problems were B and H. B is a geometry problem, where you need to figure out how many balls can fill a fruit bowl given the description of the fruit bowl and a description for how it should be filled.
In problem H, you have to find valid solutions to a 2x2x2 rubik cube. You are given an initial configuration and you can apply 3 different spins a number of times to try to get all sides to have a single color.
I’m not really sure how H can be solved within a standard 2 or 5 second time limit without breaking the standard memory constraints for a problem. It’s possible to solve the problem using a bounded breadth first search algorithm, with efficient implementations of the spins and storing seen states, but this is still slow without relying on significant amounts of memory. It’s also possible to pack the cube state into two integer values rather than a 6×8 char array to cut down on memory, but then extra processing time has to be spent on packing and unpacking the values for applying the spins.
The teams are competing this weekend in the Alberta Collegiate Programming Competition. There will be a lot of teams from Canada and the US competing, so it should give us a good chance to see how we will fair at regionals.
Finally, I am speaking today at a computer science event for undergraduates to try to generate more interest in the ACM ICPC contest.
