IOIVoting
SRM 808 · 2021-06-23 · by misof
Problem Statement
The International Olympiad in Informatics (IOI) is currently in progress. To honor this competition, our problems for this round have IOI-flavored stories.
When taking an informal vote to choose among N options (numbered from 0 to N-1), the General Assembly (GA) of the IOI sometimes uses a voting system that allows the voters to express preferences.
First, the votes are collected. The output of these votes is an N times N matrix: for each pair of options (i, j) the number p[i,j] of people who prefer i over j.
You are given the contents of this matrix in the
Note that not everyone expressed their preferences on all options, so the values in votes can be arbitrary (except for the main diagonal which is guaranteed to contain zeros). In particular, the preferences of the voters are not necessarily transitive.
The results of the election are evaluated in a sequence of steps, as explained below.
We say that voters prefer option A over option B if p[A,B] > p[B,A].
We say that option A can defeat option B if there is a sequence C1 = A, C2, ..., C(k-1), Ck = B of options such that voters prefer C1 over C2, C2 over C3, ..., and C(k-1) over Ck. The sequence A = C1, C2, ..., Ck = B is called an argument that A can defeat B. The argument can be arbitrarily long.
Note that sometimes one argument shows that A can defeat B but there can also be another argument that shows that B can defeat A.
The strength of direct preference of option A over option B is equal to p[A,B] - p[B,A]: the difference between the number of votes "A is better than B" and votes "B is better than A".
The strength of an argument is the minimum strength of direct preferences along the sequence: that is, the minimum over all valid i of the strength of the direct preference of Ci over C(i+1).
For any two options A, B, let S(A,B) be the strength of the strongest argument that A can defeat B -- i.e., the maximum of strengths of all arguments that show that A can defeat B. If there are no such arguments, S(A,B) is defined to be zero.
We say that option A is at least as powerful as option B if S(A,B) >= S(B,A).
We say that option A is a potential winner if A is at least as powerful as each of the other N-1 options.
Return a sequence of all potential winners. The sequence must be sorted in ascending order.
Constraints
- N will be between 1 and 50, inclusive.
- votes will have exactly N*N elements.
- Each element of votes will be between 0 and 9,999, inclusive.
- For each i, votes[i*N+i] will be 0.
5
{ 0, 20, 26, 30, 22,
25, 0, 16, 33, 18,
19, 29, 0, 17, 24,
15, 12, 28, 0, 14,
23, 27, 21, 31, 0 }
Returns: {4 }
The voters prefer option 1 over option 0: we have p[1,0] = 25 which is greater than p[0,1] = 20. Thus, option 1 can defeat option 0. One possible argument is simply the sequence {1, 0}. The strength of this argument is 25-20 = 5. However, option 0 can also defeat option 1. One possible argument is the sequence {0, 3, 2, 1}. Voters prefer option 0 over option 3 (30 votes against 15), they prefer option 3 over option 2 (28 votes vs. 17), and they prefer option 2 over option 1 (29 vs. 16). The strength of this argument is min( 30-15, 28-17, 29-16 ) = 11. It can be shown that the arguments shown above are (not necessarily unique) strongest possible arguments for those pairs of options. Thus, S(1,0) = 5 and S(0,1) = 11. Already from these two values we see that option 1 cannot be a potential winner. Here, the only potential winner is option 4: we have S(4,0) >= S(0,4), S(4,1) >= S(1,4), S(4,2) >= S(2,4), and S(4,3) >= S(3,4).
4
{0, 1, 1, 1,
1, 0, 1, 1,
1, 1, 0, 1,
1, 1, 1, 0}
Returns: {0, 1, 2, 3 }
All options are tied. No option can be shown to defeat any other option. Hence, for each two options A, B we have S(A,B) = 0, and therefore each option is a potential winner.
1
{0}
Returns: {0 }
One option, no votes. The statement "option 0 is at least as powerful as each of the other zero options" is still vacuously true, so option 0 is a potential winner.
4
{ 0, 10, 11, 12,
13, 0, 14, 15,
97, 98, 0, 99,
16, 17, 18, 0}
Returns: {2 }
One of the nice properties of this system is that if voters prefer an option X over each of the other options, option X is sure to be the only potential winner. But, as we saw in Example 0, sometimes there is no such option and the system still produces only one potential winner.
5
{ 0, 0, 0, 0, 0,
3, 0, 3, 99, 3,
0, 0, 0, 0, 0,
4, 99, 5, 0, 6,
0, 0, 0, 0, 0}
Returns: {1, 3 }
Voters prefer each of the options 1 and 3 over each of the options 0, 2, 4, but other than that they have no preferences. In particular, they are indifferent between options 1 and 3, and both of those end being potential winners.
Submissions are judged against all 91 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IOIVoting with a public method vector<int> winners(int N, vector<int> votes) · 91 test cases · 2 s / 256 MB per case