Tag Archives: acm icpc

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.

What? Where did the last 2 months go?

Well, somehow we’ve made it to the end of the first semester of this year, and I quite inconveniently forgot to write about anything since the start of April. This is quite problematic. I guess that means it’s time for me to do my semi-regular dump of notable things. Bleh.

So, where to begin?

ACM-ICPC Trip

So yes, we did arrive safely in Germany, spending a week with my relatives who live just outside of Frankfurt-am-Main in centre of the country. That was a fun week, we spent many days taking in the area, sampling the culture, and preparing for the programming contest the next week. We spent a week in Stockholm, where the contest was held, which was great fun in general (despite being somewhat colder than Germany and indeed Australia), we met many like-minded people, and thoroughly enjoyed the week. In the end, we solved three problems in the contest, which was (just) sufficient to see us getting a ranked position of equal 49th (yay!).

I’ll write up the two weeks spent overseas in greater detail soon (hopefully).

Twitter & Co.

So I succumbed to peer pressure roughly two weeks ago, signing up for Twitter and Identi.ca. As a fun experiment into the field, I investigated how long it would take, and what measures would be necessary, for someone to notice that I was on Twitter, and then follow me. I did this by following one or two people per day, and getting them to drop relatively silent hints about my existence. In the end, it took about a week for someone to notice me, with a fairly blatant reference to me needed to make it obvious. Despite the great scientific breakthrough observed, I don’t think the result is sufficient to write a paper about… :P

My main observation is that Twitter is miles behind Identi.ca in terms of useful features (I like group notices, denoted by ‘!’ tags in Identi.ca, and Jabber-based updating in particular), stability (updating my Avatar in Identi.ca does indeed work first time, every time, whereas it took me 10 tries to get it to work in Twitter), and ability to store my own name (This would make Twitter the first site that I have ever needed to call myself “Chris” as opposed to “Christopher”), that said, Twitter is ahead greatly in terms of the number of people on it, which makes sticking around there a necessary evil (boo for centralisation!).

End of Semester/Undergrad

And yes, it would be amiss to not note that last week was my last week of lectures as an undergrad student (presuming, of course, that all of my exams go sufficiently well), it was mostly uneventful, with the exception of having to hand in two major assignments, prepare and present a lightning talk, and run the session in which it was presented. All-in-all rather busy!

Leavin’ on (a) jet plane(s)

As previously mentioned I’m on one of the Australian teams competing in the ACM ICPC World Finals being held in Stockholm on April 21 — that means that I somehow need to get to Europe, and that somehow is series of flights, today — with a week’s stopover in Frankfurt, to visit relatives who live there.

Flights today are Hobart-Melbourne (not too bad) and Melbourne-Frankfurt via Bangkok (oriental setting), an ugly 28 hours total in transit (that I’m not really looking forward to), arriving at the somewhat inconvenient time of 6AM (just to ensure that any excess jetlag will be comfortably prolonged).

I’ll be trying pretty hard to document my trip here, and this will probably mean that there’ll be a bit of extra noise coming from me on PLOA — for those of you with little interest in what I’m doing: sorry about that!

Happy Arbitrarily-celebrated Public Holiday!

I notice that the most significant number on my clock has incremented (as it tends to do once every 365ish days), and hence I feel obliged to point it out to you all: Happy new year!

2009 looks like it’ll be a really exciting year for me (for the first few months of it, anyway) — I’m looking forward to (in no particular (chronological) order):

  • Not going to Sydney to tutor at NCSS, instead, filling most of the rest of my summer break doing programming competition practice (exciting!!!?!)
  • linux.conf.au 2009 in Hobart (and the associated bonus of finally getting friends from interstate to reciprocate visits I’ve paid). Only 18 more sleeps until the first day of miniconfs kicks off — I’m thoroughly excited!
  • Starting my final semester of undergrad study (not so much the overload that I’ll be undertaking in order to actually finish my degree :()
  • Easter in Germany!
  • Competing in the World Finals of the ACM ICPC, to be held in Stockholm towards the end of April

May your 2009 also be fun, exciting and productive!

ICPC 2008 (huge success)

The ACM ICPC South Pacific Region was on yesterday, and was great fun (as usual). My team this year, the Mehffort Musketeers consisted of Alex Berry (who’ll be competing in the Google Code Jam regionals soon as well), Michael Ford and myself.

For the benefit of people who did the ICPC this year: I solved problem A, C and I; Michael solved B and D, and Alex solved E, F and H. Here’s some general commentary on the problems that I solved:

  • Problem A was very simple, and the shell of my solution was complete within three minutes of the contest starting. Unfortunately, the entire problem was not defined until halfway through the test data, which led me to finishing it a bit later.
  • Problem C, which seems to have been the problematic problem this year (as far as judging’s concerned) was relatively straightforward, though I had two rather annoying bugs that took me about an hour to week out… it happens, I suppose. Solved on the first submission, which I’m happy about.
  • Problem I was a longest path problem, that was relatively straightforward depending on what sort of algorithm you chose to solve it. I’ve heard reports of people using the Bellman-Ford Algorithm and failing — as far as I can tell, such an algorithm would work on problems except where there existed a cycle not involving the endpoints of the path taken in the problem. I used Floyd’s Algorithm and had it solved first time. Simple.

As alluded to earlier, we solved 8 problems, and we’re currently the only team to do so with the testing data used on the day (this means that we’re in a provisional first place), however, there are many teams who are likely to get problem C rejudged, and following that we’ll likely be third. More news to come.