Question
Gerrymandering, which lias been in the news again lately, is the practice of carving up electoral districts in very careful ways so as to lead to outcomes that favor a particular political party. Recent court challenges to the practice have argued that through this calculated re-districting, large numbers of voters are being effectively (and intentionally) disenfranchised. Computers, it turns out, have been implicated as some of the main "villains" in much of the news coverage on this topic: it is only thanks to powerful software that gerrymandering grew from an activity carried out by a bunch of people with maps, pencil, and paper into the industrial-strength process that it is today. Why is gerrymandering a computational problem? Partly it's the database issues involved in tracking voter demographics down to the level of individual streets and houses; and partly it's the algorithmic issues involved in grouping voters into districts. Let's think a bit about what these latter issues look like. Suppose we have a set of n precincts P1, P2,..., Pn, each containing m registered voters. We're supposed to divide these precincts into two districts, each consisting of n/2 of the precincts. Now, for each precinct, we have information on how many voters are registered to each of two political parties. (Suppose for simplicity that every voter is registered to one of these two.) We'll say that the set of precincts is susceptible to gerrymandering if it is possible to perform the division into two districts in such a way that the same party holds a majority in both districts. Give an algorithm to determine whether a given set of precincts is susceptible to gerrymandering; the running time of your algorithm should be polynomial in n and m. Example: Suppose we have n = 4 precincts, and the following information on registered voters. Example: Suppose we have n = 4 precincts, and the following information oil registered voters. precinct Number registered for Party A Number registered for Party B 1 55 45 2 43 57 3 60 40 4 47 53 This set of precincts is susceptible, since if we grouped precincts 1 and 4 into one district, and precincts 2 and 3 into the other, then party A would have a majority in both districts. (Presumably, the "we" who are doing the grouping here are members of Party A.) This example is a quick illustration of the basic unfairness in gerrymandering: although party A holds only a slim majority in the overall population (205 to 195), it ends up with a majority in not one but both districts.
Explanation / Answer
#include struct input{ int serialNo,partyA,partyB; }; int main(){ struct input X[1000]; int n,i,sumA=0,sumB=0,sumdivA=0,sumdivB=0,a[i],b[i],j,k; scanf("%d",&n); for(i=0;i
