Third and Final Pass
Although I could have stopped here, I thought it might be interesting to see how expensive the use of an associative container like multiset was compared to something simpler. I replaced the setup code so that it stored the data in an std::vector instead of a multiset, on the theory that the comparison operator would run much faster on a vector. I had to add a call to sort the data after inserting it in the vector, which would be executed 50 times, but nowhere near as many times as the comparison operator.
The results were more or less as I expected. When run under Windows with default Release optimization, the vector version of the program ran about twice as fast as the multiset version. When compiled with g++ 3.3.5 with -O2, I saw roughly the same ratio of execution speeds.
No Spoilers
I'm not going to spoil the puzzle for you by giving away the answer. Let's just say that it is a good word puzzle, and if you manage to arrive at the answer you'll see why. If you don't manage to solve it in your head, you can download the source, compile it, and get there by brute force, just like I did.
But I don't think it will count as a spoiler if I tell you that you don't need a computer program to solve this problem.
