PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy-Medium
PREREQUISITES:
None
PROBLEM:
There’s a ranked-choice voting system of N people and M candidates.
Each person gives M-1, M-2, \ldots, 2, 1, 0 votes to the M candidates, in some order.
The candidates are ordered in descending order of votes received, with ties broken in ascending order of index.
Check if the election is unstable: that is, does there exist a set of at most two candidates such that removing them from the elections entirely and recomputing votes will result in an order that’s not a subsequence of the initial order?
If such a set exists, also find any one.
EXPLANATION:
Let A denote the initial order of the candidates. This can be computed in \mathcal{O}(NM + M\log M) by simply simulating the process.
We’re allowed to remove either one or two people.
Removing one person is quite easy to check: fix the person who’s removed (M choices), recompute the order (\mathcal{O}(NM + M\log M) time), and check if the new order is a subsequence of A (\mathcal{O}(M) time).
This is a total complexity of \mathcal{O}(NM^2) which is fast enough since N and M are both \leq 500.
So, we only need to put effort into thinking about how removing two candidates changes things.
Let S_i denote the total number of votes obtained by the i-th candidate, before any removals.
Now, suppose candidate x is removed. Then,
- If x appears before i in some preference order, after the removal of x the votes obtained by i in this order will remain exactly the same.
- If x appears after i in some preference order, after the removal of x the votes obtained by i in this order will reduce by exactly 1.
In particular, observe that when we remove two candidates x and y, the changes they introduce are independent of each other.
That is, the change to S_i when both x and y are removed, equals the sum of changes brought about by x and y individually.
Let \text{ch}[x][i] denote the overall change to the value S_i if x is removed.
All the \text{ch}[x][i] values can be precomputed in \mathcal{O}(NM^2), by iterating over every preference order and then every pair of elements within that order.
Now, let’s fix x and y to be the candidates that are removed.
For each i, S_i changes to S_i + \text{ch}[x][i] + \text{ch}[y][i].
Once the new values of S_i are computed, find the new order of elements and check if it’s a subsequence of A - if it isn’t, (x, y) is a valid pair.
This method has a complexity of \mathcal{O}(M^3\log M).
For something a bit faster, observe that there’s in fact no need to sort again at all: if the order is broken, then some two adjacent elements of A will be out of order (“adjacent” here ignoring x and y, of course).
So, we only need to compare the values of each pair of adjacent elements in A, which takes \mathcal{O}(M) time, for \mathcal{O}(M^3) overall.
TIME COMPLEXITY:
\mathcal{O}(M^2 \cdot (N + M)) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
int n,m; cin >> n >> m;
int a[n+5][m+5];
rep1(i,n) rep1(j,m) cin >> a[i][j];
vector<int> votes(m+5);
rep1(i,n){
rep1(j,m){
votes[a[i][j]] += m-j;
}
}
vector<pii> ord;
rep1(i,m) ord.pb({votes[i],-i});
sort(rall(ord));
trav(p,ord) p.ss = -p.ss;
int delta[m+5][m+5];
memset(delta,0,sizeof delta);
rep1(j,m){
rep1(i,n){
bool came = false;
rev(k,m,1){
if(a[i][k] == j){
came = true;
}
else{
delta[j][a[i][k]] += came;
}
}
}
}
// del 1
rep1(j,m){
pii pp = {inf1,inf1};
bool change = false;
for(auto [v,x] : ord){
if(x == j) conts;
pii px = {v-delta[j][x],-x};
if(px > pp){
change = true;
break;
}
pp = px;
}
if(change){
cout << 1 << endl << j << endl;
return;
}
}
// del 2
rep1(j,m){
for(int k = j+1; k <= m; ++k){
pii pp = {inf1,inf1};
bool change = false;
for(auto [v,x] : ord){
if(x == j or x == k) conts;
pii px = {v-delta[j][x]-delta[k][x],-x};
if(px > pp){
change = true;
break;
}
pp = px;
}
if(change){
cout << 2 << endl;
cout << j << " " << k << endl;
return;
}
}
}
cout << -1 << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}