[Estragon]

  ...am I falling victim to the effect where everything I
  know how to do looks easy?

You could try it and find out. :-) I ended up using a third-party library which implements an algorithm I hadn't heard of before. (My response to the challenge is below, with the useful hints X'd out.)

  Hi, guys.  This is not a gungho-serious job application, though I have
  been sniffing around machine learning/coding jobs for a long time and
  could be persuaded in the right circumstances.  I saw justin_vanw
  mention your Code Challenge on HN and decided to give it a go for fun.
  Didn't realize when I started that the upload mechanism at Code Eval
  assumes a single file, so I am mailing it to you for evaluation,
  instead.  I must admit, I don't have much formal algorithms training,
  but after about an hour's thought I just googled "XXX," and the XXX
  algorithm happened to be the top of the list.  I have a PhD in Applied
  Mathematics from MIT, and I have been focusing on Bayesian Data
  Analysis in Computational Biology, so maybe it was just a lucky
  search-engine hit.  But in general, I am a reasonably quick study.  My
  solution is at <http://XXX>, and is tested on python 2.6.5 with scipy
  0.7.0.  Untar the download, go into the XXX directory, run "sudo make
  pyinstall" (I had to add -fPIC to Makefile's CFLAGS assignment to make
  this work), and then the solution program is in
  milo-challenge/solution.py:
  
    met% python solution.py < test-input.txt 2> /dev/null
    XXX
    XXX
  
  BTW, XXX is a C implementation of the XXX algorithm from <http://XXX>,
  and is the reason I couldn't easily go through the Code Eval framework.
  It sends some garbage to stderr, which I haven't bothered to clean up.

[Natsu]

An external library? Some sort of linear algebra, I assume? I believe that a very simple algorithm that solves problems like this was featured on HN something like a week ago.

I hope that's not too much of a hint, but anyone who can figure it out from that was probably a good candidate, anyhow.

I should also mention that I did code a solution in Perl, or at least most of one, though I did not submit it. I have a grandmother to care for and that limits me on relocating, even though I would be interested in finding more interesting work.

Assuming I don't eventually go crazy in a futile attempt to explain to corporate that methods which turn a 9/2272 inch rounding error into a piece of glass that's half an inch too big do not qualify as "validation."

[Estragon]

Not linear algebra, although the optimization problem can be expressed in terms of linear programming, I think.

I wish you well in caring for your grandmother. That stuff is way more important than programming techniques.

[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.