* ElectionFraudDiv2

DIV 2 250 - ElectionFraudDiv2

http://community.topcoder.com/stat?c=problem_statement&pm=11946

You are given a list of of integers {0,5,100} that represent the percentages received by each of the candidates of an election. You are ask to write a program that detect if the election is fraudulent, or if the reported percentages are rounded. In that case, return "YES", otherwise, "NO". For more details of the problem statement please check the link below.

In my opinion this problem was little bit more tricky than a normal DIV 2 250 the 19.10% of success rate confirm my thoughts...

To solve this problem we need to consider the following three cases:

Case #1: The sum of percentages equal to 100%

In this case we assume the elections were not fraudulent. The answer for this case is "NO".

Case #2: The sum of the percentages is greater than 100%

In this case we need to check if the sum is greater than 100% because of a rounded up error. For example if the percentage for a certain candidate is 13% means that the real percentage value (not rounded) of the elections for that candidate is in the range [12.5%,13.49%]. To check that occurred a round error we substitute each of the candidate percentage for the minimum value in this range and sum them up. If we get a percentage sum less or equal to 100% means that the results are not fraudulent. The reason is because we can always get 100% with some combination of the rounded up error. In this case we should be careful with 0% is not possible to get 0% as a result of a rounded up error. For example:

3 candidates 

A1={34%,34%,34%}

sum_percentage=102

A2=33.5%,33.5%,33.5%

sum_percentage=100.5

The results of this elections still fraudulent even after fixed the rounded up errors.

Case #3: The sum of the percentages is less than 100%

Similar to case #2 but taking the maximum value of the candidate percentage range.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

class ElectionFraudDiv2 { public:    string IsFraudulent( vector <int> p ) {       int sum, N;       sum = N = 0;       for(int i = 0; i < sz(p); ++i) {          sum += p[i]*100;          if(p[i] > 0) ++N;       }       if(sum > 10000) {          if(sum - (N * 50) > 10000) return "YES";          else return "NO";       } else if(sum < 10000) {          if(sum + (sz(p) * 49) >= 10000) return "NO";          else return "YES";       }       return "NO";    } };