Henry Jeff - 24 days ago 8

Java Question

My computer science teacher has assigned this problem to us, and just about everyone in our class up-roared over the complexity of the problem. We are only in Advanced Topics of Computer Science in High school and none of us really have no idea where to start, what algorithms to use or anything. We have determined that going straight though every possible combination, there would be 2^50th combinations to run though which is way WAY to big for really any of us to search for. I'm just curious if this is even possible to do at our low Computer Science skill level and if anyone personally thinks that this is a fair problem because our teacher still hasn't found a solution to his own problem.

Thanks!

Answer

The solution space is not really 2^50. A tie (assuming only two candidates) means 269-269. You can't get to 269 with only one state (or even only a handful of states) so you can immediately throw out all small subsets and all large subsets (winning every state also doesn't work). Furthermore, you only need to look for subsets that total 269 (because there are 538 total, that means that the complement of each of those sets is also 269).

That said, this still boils down to the subset sum problem: (https://en.wikipedia.org/wiki/Subset_sum_problem) so any solution will not scale well (unless you figure out how to do it in polynomial time, in which case you can claim $1,000,000). However, your problem is not to scale it; for the case of the US electoral college configuration (including vote splits in some states) it is not too large to figure out in a reasonable (< 10 mins as you say) amount of time.