Elections and Happiness

Problem #437

Tags: unlabeled

Who solved this?

No translations... yet

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:

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

Problem Statement

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 3 5
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 3 5
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 4 6
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 4 7
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 3 6
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.

You need to login to get test data and submit solution.