Valentine's Day '19 S1 - Voting

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 128M

Problem type

At the annual Valentine's Day dance, a vote takes place to determine King and Queen Valentine!

The event organizers have decided to use the alternative vote to determine the winner of this contest.

In the alternative vote system, voters can rank their candidates rather than simply picking a single candidate.

Votes are tallied in the following way:

  1. Count the voters' first choices.
  2. Eliminate last place candidate by lowest number of votes. If there are multiple with the lowest number of votes, remove the candidate that appeared earliest in the input.
  3. Move each eliminated vote to its next choice. If the next choice is eliminated, move it to the candidate after. Continue moving until a candidate is not eliminated.
  4. Repeat 2 and 3 until there is a single candidate left.

If at any point, a voter runs out of ranked candidates, the voter is removed.

Can you determine the winner of the vote?

Input Specification

The first line will contain two integers, N, M (1 \le N \le 20, 1 \le M \le 10^4), the number of candidates and the number of voters, respectively.

The next N lines will contain a single string of letters, indicating a candidate name. It is guaranteed that a candidate's name is less than or equal to 20 characters.

The next M lines will contain an integer X (1 \le X \le 20), indicating the number of candidates that the voter ranked followed by X space separated strings of candidate names, where the jth candidate is the jth choice of the voter. It is guaranteed that each candidate exists.

Output Specification

A single string, the winner of the vote. It is guaranteed there will always be a winner.


Subtask 1 [20%]

N, M \le 9

Subtask 2 [80%]

No additional constraints.

Sample Input 1

2 3
2 Fox Rabbit
2 Rabbit Fox
2 Rabbit Fox

Sample Output 1


Explanation for Sample 1

Rabbit earned a majority of first choice votes, so he wins.

Sample Input 2

4 8
3 Red Yellow Blue
4 Red Blue Pink Yellow
4 Red Blue Pink Yellow
2 Blue Pink
2 Yellow Pink
1 Pink
1 Pink
2 Yellow Blue

Sample Output 2


Explanation for Sample 2

The first choices tally to:

Yellow: 2
Pink: 2
Blue: 1
Red: 3

In round one, Blue is eliminated and Blue's vote goes to Pink. (Yellow=2, Pink=3, Red=3)

In round two, Yellow is eliminated. Only one Yellow voter had a second preference, and it goes to Pink. (Pink=4, Red=3)

Now, Pink has the majority of votes so Pink wins.


There are no comments at the moment.