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.