The ACM South Pacific Regional Programming Contest is done and dusted for another year. My team (The Triple Helix) scored a provisional third place with seven problems (that’s tied with the team on second, but not the team on first as was the case last year), which after talking with other teams at the top seems fairly stable. This is a really encouraging result for us, not least because I shared a team with completely different teammates from previous years, but also because one of those teammates was attempting this contest for the first time.

So of the seven problems, I solved three, being problems A, G and I, Josh solved B and E (there’s an interesting story there that I’ll leave him to tell), and Simon solved D and F (spending the last hour on H). Here’s my analysis of the ones I solved.

Problem A: The problem at the front of the pack is, as usual, a “typing practice” problem, that is, one where the trick is doing precisely what they tell you on the statement as quickly as possible. I had a working solution in 8 minutes, but a technical glitch on our local site meant that I didn’t have any pretyped test data (the sample data was very tedious and difficult to type correctly) until minute 15. A quick test and submit, and done.

Problem G: The idea of this problem is to determine if a path exists allowing you to visit all cities from a list of cities, in order, and only once. You are given a set of flights that may contain cities not from the original list, which you may visit as frequently as necessary. The observation here is that you’d like to determine if a path exists between adjacent cities on the list through the allowed intermediary cities only. By being judicious about ordering your verticies in an adjacency matrix, you can solve this using a non-standard version of Floyd’s algorithm, whereby your outer loop (the one that considers your current intermediary vertex) only considers the valid intermediary cities. Determining if the desired path exists is just a matter of stepping through the path.

Problem I: This problem involved determining if a path to a point in a grid exists, whereby the only possible moves at a given point are to go “forward” or “rotate to the right”, and determining the length of the shortest path if one exists. As a grid-based shortest path problem, a BFS is the correct method; the trick is to notice that the state space involves not only the grid itself, but actually the grid in each of the four possible orientations — once this key bit of insight is out of the way you only have to consider a few special cases: are you at the goal state already; is the goal state on a wall in the maze; and the one clarified by the judges, is your start space on a wall?

We didn’t solve our eighth problem (H), but luckily, a tiny change to our solution to B in the last 5 minutes got accepted (at minute 297, no less), which was sufficient to knock us up to 3rd.

So that’s it until after the rejudging occurs, hopefully with no drastic changes at the top 🙂

Update: Josh posted analysis of the problems he solved (a long with some ACM t-shirts) to his blog. Check it out for more of the story about this year’s contest.