PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
You have an array A.
You can perform the following operation:
- Choose any subarray of A that has a majority element.
Let M be this majority element.
Set all the elements of the subarray to M.
Find the lexicographically smallest possible final array A.
EXPLANATION:
The key observation here that simplifies the problem greatly is that, if there exists a subarray [L, R] of length \gt 3 with majority M, then there must also exist a subarray [l, r] of length 3 with majority M, and L \leq l \leq r \leq R, i.e. the smaller subarray is contained in the larger one.
Proof
This is surprisingly simple to prove.
Let’s look at the first three elements of our subarray.
If M is a majority among these three, great - we’ve found what we want.
Otherwise, throw out these three elements and continue on.This works because, if M was not the majority of those three elements, we’d have discarded at most one copy of M and at least two elements that are not M - so the remaining subarray will still have M as its majority.
This process can be repeated till there are \leq 3 elements remaining.
Note that we know M is the majority of these \leq 3 elements.Now,
- If there are 3 elements remaining, we know M is its majority so we’re done.
- If there are 2 elements, they must both equal M. Simply include the previous element as well to obtain a length 3 subarray with majority M.
- If there’s only one element, it must equal M.
Now, look at the previous step, where there were four elements and M was the majority - meaning at least three of the four elements were M.
This in particular means that among the last three elements, at least two are M, so we’re again done.
Note that once we have this smaller subarray of length 3 with majority M, the operation on the larger subarray can be simulated using it: operate on the small subarray first to obtain three occurrences of M, then we can repeatedly extend these occurrences either left or right one step by choosing an appropriate length-3 subarray.
So, it’s enough to care about subarrays of length 3.
Consider some subarray [i, i+2] that has a majority element M.
Observe that we can use this subarray to “propagate” the value M to either side of the subarray by repeatedly choosing windows of size 3 - but we’re also fairly restricted in that this operation of painting a segment with M is the only thing we can do.
Since we’re aiming for lexicographic minimization, this gives us a fairly straightforward greedy solution.
For each i from 1 to N, we want to make A_i as small as possible: even at the cost of everything after it.
So, we have the following algorithm:
- Iterate i in order from 1 to N.
- When at i, let mn_i denote the minimum value of a majority element in a length-3 subarray that ends at or after index i.
- If mn_i \geq A_i, nothing needs to be done.
- If mn_i \lt A_i though, it’s optimal to replace A_i with mn_i.
To do the last step quickly, let L be the leftmost index \geq i-2 such that the subarray [A_L, A_{L+1}, A_{L+2}] has mn_i as its majority element.
We can then do the following:
- This subarray must be used to overwrite A_i.
So, everything in [i, L+2] will become mn_i. - Once this is done, we can also consider extending beyond index L+2.
Specifically, let R \gt L+2 be the smallest index such that A_R \lt mn_i.
It’s then optimal to just give everything in [L+2, R-1] also the value mn_i. - Once this is done, observe that index R itself will not have its value changed; and by construction so far, it’s never optimal for any index \lt R to overwrite A_R either.
Essentially, the suffix after R becomes an independent problem, so we can just set i = R+1 and continue the process.
The slow parts of the above algorithm are finding mn_i and L for a fixed i.
This is easy to optimize: mn_i is just a suffix minimum, and L can be tracked while updating mn_i as well since it’s functionally just the leftmost index of the suffix minimum.
We don’t really need to optimize the process of finding R once L is known, since we’re going to overwrite everything till R and skip to R+1 anyway.
This means we can simply bruteforce the process of finding R once mn_i and L are known for i.
TIME COMPLEXITY:
\mathcal{O}(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; cin >> n;
vector a(n, 0);
for (int &x : a) cin >> x;
auto check3 = [&] (int i) {
if (i+2 >= n) return n+1;
if (a[i] == a[i+1] or a[i] == a[i+2]) return a[i];
if (a[i+1] == a[i+2]) return a[i+1];
return n+1;
};
vector suf(n, n);
for (int i = n-3; i >= 0; --i) {
suf[i] = suf[i+1];
int m = check3(i);
if (m == n+1) continue;
if (m <= check3(suf[i])) suf[i] = i;
}
auto solve = [&] () {
for (int i = 0; i < n; ++i) {
int j = suf[max(0, i-2)];
if (i > 0 and check3(i-1) <= check3(j)) j = min(j, i-1);
if (i > 1 and check3(i-2) <= check3(j)) j = min(j, i-2);
int mn = check3(j);
if (j >= n or mn >= a[i]) continue;
int r = j+3;
while (r < n and a[r] > mn) ++r;
for (int x = i; x < r; ++x) a[x] = mn;
i = r;
}
};
solve();
for (int x : a) cout << x << ' ';
cout << '\n';
}
}