[Natsu]

It's weird how full-circle I've gone on this. I went from "the naive solution is easy enough to write" to "I bet there's a more efficient way" to "oh crap, my solution doesn't actually work, because the preferences can have ties."

I did have the fun of coding up the algorithm I saw on HN a while back, though, so it was fun.

[Natsu]

Incidentally, I had more time this weekend and found that it gets a lot easier if I use a more suitable algorithm. Considering it as a S-M problem only makes things more complex, because there can be ties (which kills the nice algorithm for solving these) while introducing more complexity than is necessary, given that there's a single cost to be maximized, rather than two distinct preference lists.

Seems like I should have been doing it as an A problem, where you can just use the H algorithm. So I want to say thanks to the guys who posted the challenge: it was a good excuse to teach myself some combinatorial algorithms.

Lest anyone wonder, I'm using those weird abbreviations so as not to spoil the problem. Figuring out which algorithms to use is half the fun and I read about quite a few different types of problems before figuring out which was the most suitable. I'd hate to deny anyone else the same learning experience.