I hope this isn't homework. This is can be solved with a DP roughly similar to the classic one for subset sum. Let X and Y be the districts. Use a 4d table of booleans G.
G(i,x,y,p) is true iff there is an assignment of precincts P(1)...P(i), with p in X and i-p in Y, and with x and y "gnu party" voters respectively. The details of filling in the table for i=1,2...2n are not hard. Since p <= i <= 2n, x <= 2mn, y <= 2mn, the table can be filled in in polynomial time. The precincts can be gerrymandered in favor of gnu iff there are any true elements G(2n,x,y,n) where x>nm and y > nm. A symmetric computation can tell you if gerrymandering is possible for the "unix party." --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
