CondorcetVoting
SRM 371 · 2007-10-13 · by bmerry
Problem Statement
One approach to voting is to have voters assign a rank to each candidate. Candidate A is preferred to candidate B if there are more voters who rank A ahead of B than there are voters who rank B ahead of A. A Condorcet winner is a candidate which is preferred to all other candidates. There can be at most one Cordorcet winner in an election, but there might also be none.
You will be given a
Constraints
- votes will contain between 1 and 50 elements, inclusive.
- Each element of votes will contain between 1 and 50 characters, inclusive.
- Each element of votes will contain the same number of characters.
- Each element of votes will contain only lowercase letters ('a' - 'z').
{"acbd",
"bacd",
"bdca"}
Returns: 0
Voters 0 and 2 ranked candidate 0 higher than candidate 1, while voter 1 ranked candidate 1 higher than candidate 0. Therefore, candidate 0 is preferred to candidate 1. All three voters ranked candidate 0 higher than candidate 2, so candidate 0 is preferred to candidate 2. Finally, voters 0 and 1 ranked candidate 0 higher than candidate 3, while only voter 2 ranked candidate 3 higher than candidate 0. Therefore, candidate 0 is preferred to candidate 3 as well.
{"abc",
"bca",
"cab"}
Returns: -1
This is a classic example of a cyclic preference. Two voters prefer 0 to 1, two prefer 1 to 2, and two prefer 2 to 0. There is no Condorcet winner.
{"cezdqcw"}
Returns: -1
Even with only one voter, there may be no Condorcet winner because of a simple tie.
{"abcd", "abcd", "abcd", "abcd", "abcd", "abcd",
"cbad", "cbad", "cbad", "cbad", "cbad",
"dbca", "cbda", "cbda"}
Returns: 1
Candidate 1 is nobody's first choice, but still wins.
{"a"}
Returns: 0
Submissions are judged against all 81 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CondorcetVoting with a public method int winner(vector<string> votes) · 81 test cases · 2 s / 256 MB per case