As everyone talks about US Presidential Election 2024 these days, let us talk too :)
Ruritania is a small country - and nevertheless it has President and Presidential Elections.
The process is not as complicated as in USA, but follows more general pattern:
1st round every of M voters cast a single vote for some one out of N candidates2nd round every of M voters cast a single vote for some one out of these two "top" candidatesBut let's look closer on how people pick whom to vote for? Suppose, every voter assigns his/her "approval factor" (or "measure of happiness") for each candidate - a kind of "preference list". In both rounds voter checks his "preference list" and votes for the candidate who has the highest value.
For example, there are candidates Ann, Billy and Clyde. And there are 5 voters. They make the following "matrix" of preferences:
Ann Billy Clyde
Voter #1 1.0 0.3 0.2
Voter #2 0.7 0.0 1.0
Voter #3 0.7 1.0 0.0
Voter #4 0.7 0.0 1.0
Voter #5 0.7 1.0 0.0
You see, here Billy and Clyde are some radical persons - because some voters are their devote followers (1.0) and others really hate them (0.0).
Meanwhile Ann is less or more positively approved by everyone.
In the first round Billy and Clyde will get 2 votes each, while Ann gets only 1 and doesn't pass to the next round. In the second
round Billy gets elected with 3 vs 2 votes. He makes 2.3 points of "total happiness" in population.
However "total approval/happiness" would be 3.8 if Ann were president. In other words, even proper following certain democratic
procedure doesn't immediately mean the optimal person is elected. Probably this is related to
Arrow's Theorem.
Your goal is to check records for elections of many past years and, judging by matrices of preferences, calculate cases when, like in this one, the person elected was not actually the best choice in the sense of maximizing population happiness.
Input data: contains total number of elections T to be reviewed in the first line.
Next T pairs of lines will follow.
In each pair the first line contains year number, number of voters and candidates.
The second line of a pair contain "preference matrix" as a space-separated arrays of "approval factors" given by every of voters - these arrays
themselves separated with semicolon. You'll be able to figure out the number of candidates and voters from this format.
Answer: should give year numbers (in order) when elections failed to pick for the President the person who would maximize total happiness.
Example:
input data
5
1967 5 3
1.0 0.3 0.2; 0.7 0.0 1.0; 0.7 1.0 0.0; 0.7 0.0 1.0; 0.7 1.0 0.0
1970 5 3
0.515 1 0.661; 0.073 1 0.31; 0.117 1 0.662; 0.025 1 0.001; 1 0.024 0.012
1973 7 4
0.945 0.731 1 0.542; 0.272 0.11 0.042 1; 0.335 1 0.045 0; 1 0.005 0.783 0.323; 0.247 0.014 0.664 1; 1 0.005 0.018 0.071; 0.022 0.058 0.294 1
1976 7 4
0.498 0.004 1 0.035; 0.395 0.146 1 0.052; 0.165 0.706 1 0.28; 1 0.863 0.853 0.043; 0.529 0.009 1 0.25; 0.408 0.232 1 0.064; 0.316 0.086 1 0.064
1979 6 3
1 0 0.522; 0.474 1 0; 1 0.161 0.175; 0.003 0.448 1; 1 0.589 0.943; 0.064 0.085 1
answer:
1967 1973 1979
To simplify the matter you may be sure that both voting rounds will never present "tie" (equal number of votes) for key candidates.