Valentine's Day '19 S1 - Voting

View as PDF

Submit solution


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

Author:
Problem type

At the annual Valentines 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 candidate after. Continue moving until a candidate that 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.

Subtasks

Subtask 1 [20%]

N, M \le 9

Subtask 2 [80%]

No further constraints.

Sample Input 1

2 3
Rabbit
Fox
2 Fox Rabbit
2 Rabbit Fox
2 Rabbit Fox

Sample Output 1

Rabbit

Explanation for Sample 1

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

Sample Input 2

4 8
Yellow
Pink
Blue
Red
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

Pink

Explanation for Sample 2

The first choices tally to

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

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

On 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.


Comments

There are no comments at the moment.