Tag Archives: progcomp

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.

A brief (though complete) history of “Mehffort”

For the benefit of those who were intersted, Mehffort is a portmanteau of meh and effort, and is a very popular word in the semester 2, 2008 Maclab dialect of English. It is used to convey one’s lack of motivation towards a particular task. In context:

  • Me: Paris, help me come up with a witty slogan for the TUCS T-Shirt.
  • Paris: Mehffort.

As proud denizens of the Maclab, my ACM ICPC team for this year decided to adopt the word as part of our team name.

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.

Notes on the ensuing year

Uni goes back next week, and after a long, and mostly uninteresting holidays, I’ll be quite glad to go back. Not that my holidays were awful (NCSS and LCA made sure that they weren’t), but it’ll definitely be good to go back to some form of long-term regularity, which has been missing for the past few months. This semester I’ll be studying three maths units (Algebra, Calculus and Operations Research, all at 2nd-year level) and the third year Concurrent Programming unit, which should be interesting (and hopefully difficult, challenging, and all of those other adjectives which acadmically-oriented people like to hear).

One thing that I thought might be worthwhile this year is to set some goals that fall outside the usual inevitabilities of an academic year, mostly because all these years that I don’t, I tend to somehow let the uni/school-related ones take hold (and that normally makes the following December a lot more depressing than it needs to be), and in order to hold myself to this, I’m posting them here for the world to see:

  1. Use LaTeX more. Using LaTeX to write up my Calculus 1B assignments last year seemed to coincide with a marked increase in marks for that subject (in comparison with the previous semester, in which I didn’t) — in fact, the only >90%-achieving subjects I’ve undertaken were the ones where I used LaTeX to write up my asssignments. Coincidence? I think not! Of course, the reasons I’ve just given aren’t probably very sound, and there were probably better reasons for my doing well in those units, but there’s still good reason for me to learn it better. So I will.
  2. Improve my placing in the Programming Competition. Last year, my team achieved 16th (equal 11th according to the official standings). I want my team this year to achieve 12th or better. I’ll figure out how to do this later on.
  3. Better promote Free and Open Source Software at Uni. This one is important: UTas is hosting Linux.conf.au next year, and in my opinion, the cause of Free Software is not very well-known within the student body. Therefore, I’m going to try and hold as many events as possible (probably through the Computing society, whatever it may be called this year), including one just before Software Freedom Day in September (Since this is the big FLOSS advocacy day, it would be silly not to do something then). I’ll also try to promote LCA2009 amongst the staff and students.
  4. Get more involved with TasLUG. I’ve said it once, and I’ll say it again: I was shocked to find out that TasLUG still exists, let alone that they were considering a bid for LCA2009. Now that I know that they do indeed exist, I’ll be doing my best to become an active member of the local FLOSS community.
  5. Organise a Python MiniConf for LCA next year. This one’s really a no-brainer. I like Python, and from what I could gauge at LCA this year, there’s a big Python community within Australia. Therefore, I think it’s worthwhile that we have an organised conference at LCA, so I’ll be trying my hardest to make that happen (if you think you can help here, send a mail to any_name_at_all at this domain).
  6. Make a concerted effort to get involved with a Free Software project. Unfortunately, this goal seems to show up every year. I’m definitely going to make a concerted effort on this one, and I’ll aim to participate in the Australian Summer of Code next summer (since I know that that’s going to happen). Currently Python looks good, but we’ll see how that progresses through the year.
  7. Better promote NCSS within Tasmania. Another obvious one — Attending NCSS as a student was a great opportunity for me, and going back as a tutor was wonderful. I want to make sure that more people get that opportunity.

And there you have it. I’ll make periodic posts this year as I work on achieving these.