Connection Status:
Competition Arena > Election

Election

SRM 361 · 2007-08-01 · by slex

SRM 361 · 2007-08-01 · by slex · Greedy, Sorting
Class Name: Election
Return Type: int
Method Name: votesNeeded
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

N candidates, indexed from 0 to N-1, participate in an election. After the voting is over, candidates are sorted by decreasing number of votes, and by increasing index in case of ties.

With the voting underway you have your favorites for different positions. You wonder how many additional voters would have to come to make your selection possible.

The int[] votes represents the results so far, where the k-th element is the number of votes received by candidate k. The int[] wishList corresponds to the positions where you would like to see the candidates after the voting is over. If element k of wishList is -1, it means that you don't care where candidate k ends up. Otherwise, the number represents your desired 0-based position for candidate k. Return the minimal number of additional votes needed to make it possible for the final ranking to match your wishes.

Constraints

  • votes will contain between 1 and 50 elements, inclusive.
  • wishList will contain the same number of elements as votes.
  • Each element of votes will be between 0 and 10,000,000, inclusive.
  • Each element of wishList will be between -1 and N - 1, inclusive, where N is the number of elements in votes.
  • Elements of wishList, other than -1, will be distinct.
Examples
0)
{10,8,6,4}
{-1,0,-1,2}
Returns: 6

If 3 more people vote for candidate 1, and 3 more people vote for candidate 3, the vote distribution would be {10,11,6,7}, and the final candidate ranking would be {1,0,3,2}, which matches your wishes.

1)
{10,20,30,0}
{-1,-1,-1,0}
Returns: 31

Candidate 3 will need 31 votes to take the lead.

2)
{10, 100, 40, 15, 15}
{4, 0, 1, 3, 2}
Returns: 1

It's almost as wished, but the tie breaker rule would make candidate 3 come before candadiate 4. One more vote is enough to fix that.

3)
{5052863,4419975,3556783,9490441,6166389,836297,
 4623556,4905465,117307,8071245,932463,9194925}
{-1,-1,-1,-1,2,0,-1,-1,8,9,4,11}
Returns: 53562445
4)
{0}
{0}
Returns: 0

Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Election with a public method int votesNeeded(vector<int> votes, vector<int> wishList) · 70 test cases · 2 s / 256 MB per case

Submitting as anonymous