Monthly Archives: September 2009

More ACM-SPPC Goodness!

As predicted, our third place is final! This puts us one problem clear of 4th, and tied with second place, which is kinda nice. It also means that Josh, Simon and I are in limbo until early December when wildcard world finals places are allocated — that said, it’s a nice limbo to be in, as it were.

Since Simon lacks a blog, I’m publishing his analyses of problems D and F, as well as H, where his solution TLEd at minute 295…

Problem F was obviously the hidden easy problem (it was full of pointless extra data to make it look more complicated) so I got onto that once the terminal was free. It’s BFS on a graph with vertices representing cities and a connection between two cities iff there is a road which contains both cities.

Problem D: It was very number theoretic. With this one, the months had different lengths which made things complicated unless you just took one month at a time, found the solution for each one and then gave the best solution out of all them. For each month, there was a window of opportunity where a full moon could occur such that the next full moon would be in the same month. So, again, I solved the problem for each day of the month in that window and returned the best for the month. Solving the problem for each day involved solving equations in mod Y, the number of days in a year, which can be done with the help of the extended Euclidean algorithm. Writing a Date class helped keep the thing simple enough to humanly code.

Problem H (unsolved) After getting that out, I looked at the stable marriages problem again. I remembered the algorithm in the last hour of the competition (and felt stupid since it’s simple and the name of the problem is a way of remembering it). I got onto coding it, at the same time as Josh was bashing at problem B. I actually got it working in the last five minutes but in my rush I’d made it O(n^3) instead of O(n^2) and it didn’t cut it.

I guess the last thing to mention is a round of thanks to Mike Cameron-Jones, our site director and coach, as well as Robyn Gibson (our local judge), Tony Gray (who makes everything work here), and Matt Armsby (for passing our printouts, and arranging the food on the table), amongst the many other staff who made the contest possible.

ACM SPPC (And related excitement)

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.