In one sense, it's obvious how to solve the problem: just try out all the different ways a candidate could win the various states and return the one that requires the least votes. Unfortunately, that's very expensive, requiring evaluating the best of 251 = 2251799813685248 different possibilities, a far bigger space than a program can visit in any reasonable amount of time.
All the submitted programs tried some way around that problem. They fell into a couple different camps: in one corner we had dynamic programming algorithms, and in the other we had greedy algorithms. The greedy algorithms — TurboThy, ColPanic, and geekmug's entries — worked on the principle of buying votes where they're cheapest by computing the states in which winning an electoral vote costs the fewest popular votes. This is a cheap algorithm, it's easy to understand, and it sounds like it will certainly yield good results.
In the other corner we have dynamic algorithms. The dynamic algorithms — tmoertel's and TPD's entries — work on a clever principle: assuming some ordering of the states (any old ordering will do), the number of votes you need to win X electoral votes is the minimum of (a) half (plus one) of the first state's voters plus the number of votes you need to win X - Y electoral votes where Y is the first state's electoral votes (if you won the first state, presumably by the narrowest possible margin), or (b) the number of votes you need to win X electoral votes in the rest of the states (if you lost the first state without even one vote cast for you in that state). Because of this recurrence relation, you can build a table with 51 columns (one for each position you could be in when traversing the list of states) and 270 rows (one for each different number of electoral votes the candidate could need). If you you fill in the table starting with the smallest cases, you'll have to do only constant work for each cell of the table and thus you can fill in the entire table, including the final square which contains the answer to the original problem, with just 51 * 270 = 13770 calculations.
So who's the winner? Well, this being a mini micro PFC, we'll refrain from ranking entries. But on the question of dynamic programming algorithms versus greedy algorithms: the greedy algorithms were in general much easier to read, but the dynamic programming algorithms performed as well as them1 and were provably optimal. I think if I were programming this for myself, I'd prefer the dynamic-programming method, but the greedy algorithm does very well and has the advantage that it's much easier to explain.
I was very happy with the results and I hope you all had fun with this little programming exercise.
And in case you're wondering: it turns out that to win the presidency of the United States, you can get by with a minimum of about 22.175% of all votes cast. You'd need to win al ak az ar co ct de dc hi id ia ks ky la me md ma mn ms mo mt ne nh nj nm nc nd ok or ri sc sd tn ut vt va wv wi and wy to have this happen.
1: Technically, the dynamic programming algorithms will be O(n*V), where n is the number of states and V is the number of needed electoral votes, whereas the greedy algorithms will be O(n*log n), but in actual elections the magnitude of V will be directly proportional to n and thus its size will be proportional to log n, so the DP algorithms will be O(n*log n) as well.
|< So I was listening to... | BBC White season: 'Rivers of Blood' >|