PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
Greedy algorithms
PROBLEM:
You’re given an array A. Each element of A is either -1 or a positive integer.
You can rearrange the positive elements of A among themselves, however you wish.
After rearrangement, the following will happen for each person i:
- If A_i \gt 0, person i will vote for person A_i.
- Otherwise, let f_v denote the number of indices \lt i such that A_i = v.
- If there’s a unique v for which f_v is maximum, person i will vote for this v.
- Otherwise, person i won’t vote.
You’re given X.
Is it possible to make X the unique winner of the election?
EXPLANATION:
Let’s call indices with A_i \gt 0 “fixed” indices, while those with A_i = -1 will be called “flexible” indices.
Observe that the first person to vote for X must be at a fixed index - because a flexible index is never going to vote for X when X has 0 votes (and so cannot be the unique maximum).
In particular, if X does not appear among the non-zero elements of A at all, it’s impossible for X to ever receive any votes.
This means X certainly cannot win, so we can immediately say the answer is No.
So, let’s consider the situation where we do have some copies of X to use.
It’s in our best interest to make as many of the -1's vote for X as possible.
Thus, naturally, it’s optimal to just place all copies of X as quickly as we can: if there are c_X copies of X in total we just place them in the leftmost c_X positions that initially contained positive elements.
Now, we need to arrange the other elements in the remaining positions.
Again, it’s ideal if we’re able to make as many people vote for X as possible.
This means we should try to avoid making any other value reach the frequency of X; since as long as X has the highest frequency, we can ensure that the -1 votes will continue to go to X.
The simplest way to ensure this goes on for as long as possible, is to ‘balance’ the frequencies of the other elements.
That is,
- First, place one copy of each remaining element.
- Only after that, place the second copy of each remaining element.
- Only after that, place the third copy of each remaining element.
\vdots
It’s not hard to see that this is optimal in both maximizing the number of votes X receives, as well as minimizing the number of votes anybody else receives.
Once the optimal arrangement has been built, tally the total votes received by everyone, and then check if X is the unique winner.
Since A_i \le 100, this entire algorithm can be implemented in \mathcal{O}(N\cdot 100) time by storing appropriate frequency arrays and iterating across them when needed.
Alternately, a data structure like a priority queue or set allows for a complexity of \mathcal{O}(N\log N).
TIME COMPLEXITY:
\mathcal{O}(N\log N) or \mathcal{O}(100\cdot N) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n, x; cin >> n >> x;
vector a(n, 0);
for (int &y : a) cin >> y;
array<int, 101> have{};
for (int i = 0; i < n; ++i) {
if (a[i] != -1) {
++have[a[i]];
}
}
if (have[x] == 0) {
cout << "No\n";
continue;
}
array<int, 101> votes{}, freq{};
for (int i = 0; i < n; ++i) {
if (a[i] == -1) {
int mx = ranges::max(freq);
int ct = 0, who = 0;
for (int j = 0; j <= 100; ++j) {
if (freq[j] == mx) {
++ct;
who = j;
}
}
if (ct == 1) ++votes[who];
}
else {
if (have[x] > 0) {
a[i] = x;
--have[x];
}
else {
int mn = -1;
for (int j = 0; j <= 100; ++j) {
if (have[j] == 0) continue;
if (mn == -1 or freq[j] < freq[mn]) mn = j;
}
a[i] = mn;
--have[mn];
}
++votes[a[i]];
++freq[a[i]];
}
}
int mx = ranges::max(votes);
int ct = 0, who = 0;
for (int j = 0; j <= 100; ++j) {
if (votes[j] == mx) {
++ct;
who = j;
}
}
if (ct == 1 and who == x) cout << "Yes\n";
else cout << "No\n";
}
}