PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: pols_agyi_pols
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Binary search
PROBLEM:
You’re given an array A. You can perform the following operation on it:
- Choose any subarray of A with length \gt 1, and replace it with its median.
For each i = 1, 2, 3, \ldots, N, find out whether there exists a sequence of operations such that A_i is the last remaining element.
EXPLANATION:
Since we’re allowed to choose subarrays of length \geq 2, let’s first look specifically at what operating on a subarray of length 2 does.
If we choose a subarray containing the two elements x and y, their median is just \min(x, y).
So, we replace the two elements x and y with \min(x, y).
Another way to see this is that we essentially delete the single element \max(x, y) from the array.
This is a useful operation to have, so keep it in mind.
Intuitively, it allows us to delete “large” numbers if necessary.
Further, note that deleting “large” numbers reduces the median of the array.
Now, let’s fix an index i, and try to decide when A_i can be the final element.
Suppose c_1 elements of A are \lt A_i, and c_2 of them are \geq A_i.
Note that c_1 + c_2 = N.
Then,
- If c_1 \lt c_2, the median will be \geq A_i.
This is useful, since we’re able to delete large numbers.
So, if the median is \gt A_i, we can simply repeatedly delete the maximum element.
This will eventually make the median exactly equal to A_i, at which point we can replace the entire array with its median and be done. - If c_1 \geq c_2, the median of A will be \lt A_i, which is not ideal.
Our goal is thus to reach a state where c_1 \lt c_2 by performing some sequence of operations - if we can never reach this, it’s impossible to make A_i the median.
So, ideally, we want to make c_1 as small as possible.
One simple way to do that is to choose any subarray of length \gt 1 containing only elements that are \lt A_i, and replace them with their median.
This will delete all but one of them (while not changing c_2 at all), so if we chose a subarray of length x, c_1 will reduce by x-1.
Suppose we perform this operation till we no longer can - that is, any two elements that’re \lt A_i are separated by at least one element that’s \geq A_i.
In this array, if c_1 \lt c_2, we’ve achieved our goal.
If c_1 \geq c_2 even now, it’s impossible to make c_1 \lt c_2 no matter what we do.
This is because deleting any number of “small” elements requires us to delete at least as many “large” elements as well due to the small elements being separated, so the difference between them cannot improve.
We now have a rather simple way to check whether A_i can be the final value or not, in linear time:
- Compress all blocks of elements \lt A_i into a single element.
- Let c_1 be the number of elements \lt A_i, and c_2 be the number that are \geq A_i.
Simply check whether c_1 \lt c_2.
In particular, note that this check depends only on the value of A_i, and not on its position in A at all.
So, rather than determining which indices can be the final element, we can instead try to determine which values can be the final element.
It’s now not hard to see that if x can be the median, so can any integer \leq x that’s in the array.
Why?
Suppose x can be the median, meaning c_1 \lt c_2 after shrinking blocks of small elements into a single one.
Consider what happens when looking at x-1 instead.
- c_2 will increase by the number of occurrences of x-1 in the array.
- Each occurrence of x-1 in the array will, at best, break one block of small elements into two.
So, each occurrence of x-1 in the array will increase c_1 by at most 1.
Since c_1 \lt c_2 initially, and c_1 doesn’t increase more than c_2 does, the inequality still holds.
This proves the correctness of binary search.
This allows us to binary search to find the largest x that can possibly be the median — say, M.
Since the check for a single x takes \mathcal{O}(N) time, finding M can be done in \mathcal{O}(N\log \max(A)) time (or \mathcal{O}(N\log N) if you compress elements).
Once M is known, simply output 1 for every index i such that A_i \leq M, and 0 for the others.
TIME COMPLEXITY:
\mathcal{O}(N\log \max(A)) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll kitne_cases_hain;
kitne_cases_hain=1;
cin>>kitne_cases_hain;
while(kitne_cases_hain--){
ll n;
cin>>n;
ll a[n];
pair <ll,ll> p[n];
for(int i=0;i<n;i++){
cin>>a[i];
p[i]={a[i],i};
}
sort(p,p+n);
ll cnt[n+2]={};
ll ans[n]={};
ll last=-1;
ll cntg=n;
ll cnts=0;
vector <ll> v;
for(int i=0;i<n;i++){
if(p[i].first!=last){
for(auto it:v){
cntg--;
if(cnt[it-1]==cnt[it+1] && cnt[it-1]==0){
cnts++;
}
if(cnt[it-1]==cnt[it+1] && cnt[it-1]==1){
cnts--;
}
cnt[it]=1;
}
v.clear();
if(cntg>cnts){
ans[p[i].second]=1;
}
}else{
ans[p[i].second]=ans[p[i-1].second];
}
v.push_back(p[i].second+1);
last=p[i].first;
}
for(int i=0;i<n;i++){
cout<<ans[i];
}
cout<<"\n";
}
return 0;
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
mxadj = 0
for i in range(n-1): mxadj = max(mxadj, min(a[i], a[i+1]))
lo, hi = 1, 10**9
while lo < hi:
mid = (lo + hi + 1)//2
more, less = 0, 0
for i in range(n):
if a[i] >= mid: more += 1
else:
if i == 0 or (a[i-1] >= mid): less += 1
if more > less: lo = mid
else: hi = mid-1
ans = [0]*n
for i in range(n):
if a[i] <= lo: ans[i] = 1
print(''.join(str(x) for x in ans))
.