Nlogonian elections are coming up soon and there are many candidates running for President of one of the greatest nations on Earth.
The voting system used in Nlogonia is quite out of the ordinary. Each person votes by making a list of all candidates, in order of preferences of the voter. This means that the first candidate in the list is the one whose proposals please the voter most, and the last candidate in the list is the one whose proposals please the voter least.
Suppose that there are exactly five voters $1, 2, 3, 4$ and $5$, exactly five candidates $A, B, C, D$ and $E$, and the voters voted as shown in the following table:
To determine the winner, the Electoral Commission first makes a draw, called Election Ordering, which contains all the candidates in a certain order. Then each candidate is evaluated following the Election Ordering, until one of them is elected as President. For this to happen, the current evaluated candidate must be the preferred still-running candidate for more than half of the voters.
To make the election system clearer, continuing the example above, suppose that the result of the Election Ordering is $C, D, A, E$ and $B$. To determine the winner the Electoral Commission would perform the following steps:
- The first candidate evaluated is $C$. As this candidate is the preferred candidate for just two of the
five voters ($1$ and $3$), then $C$ is eliminated.
- Next candidate evaluated is $D$, who is the preferred still-running candidate for only two voters ($1$ and $5$). Thus, candidate $D$ is also eliminated.
- Candidate $A$ is evaluated next. Since this candidate is the preferred still-running candidate for three of the five voters ($1$, $4$ and $5$), candidate $A$ is elected as President and the voting ends.
One of the candidates has managed to corrupt some members of the Electoral Commission, and can
now decide what the result of the Election Ordering will be. Also, thanks to various social networks
analysis, the candidate knows the list that each voter will vote. The only thing the candidate needs to
win the election now is to figure out a proper Election Ordering. As this is not an easy task, someone
from the candidate staff anonymously hired you to find an ordering that makes the candidate win.
Hurry up, because the draw will occur within the next few hours.