PROBLEM LINK:
Setter- Hasan Jaddouh
Tester- Jakub Safin
Editoiralist- Abhishek Pandey
DIFFICULTY:
EASY-MEDIUM
PRE-REQUISITES:
Clever Simulation, Data strunctures, namely Stacks
PROBLEM:
We have an array A of length N. Every day, the elements which are less than both of its neighbors (i.e. A_i such that A_{i-1}>A_i< A_{i+1} disappear. We have to tell for each element, when will it disappear from the array.
QUICK EXPLANATION:
Key Trick- Deciding the appropriate data structure, such as stack.
One of the ideal data-structures to solve this problem is stack. We traverse from left to right, simulating the process as given. Taking care of conditions, like when an element disappears, what day to assign etc. is good enough to fetch an AC.
EXPLANATION:
This is a data structure problem. The editorial will describe the solution using stack, based on setter’s approach. Other implementations are also possible.
There will be only a single section in this editorial, describing the full solution. Solutions of (Why?) are in Chef Vijju’s corner, as usual. 
1. Setter’s Solution-
If the only data structure you knew were 1-D and 2-D array, then stop. Go to pre-requisites and learn stack. This is a data structure problem, so reading this editorial without knowing the basics of stack will be of no use.
The code used by setter, is extremely simple, and elegant. Quoting it-
for(int i=0;i<nn;i++){
int day=1;
while(g > 1 && st[g-2] > st[g-1] && st[g-1] <arr2[i]){
day=max(day,dy[g-1]);
if(g > 1)
sol2[idd[g-1]] = day;
g--;
day ++ ;
}
st[g] = arr2[i];
idd[g] = i;
dy[g] =day;
g++;
}
This is a just a simulation (although a clever one!) of whats asked, so there is no need for proof of correctness (of concept).
First thing we should ask is, what can be the maximum number of days upto which elements are deleted? We can say that it is N-2 (Why?)
\implies We only need to cleverly-simulate for first N-2 days.
We note that if we use arrays, then frequent re-allocation, change of indexes or looping over already “deleted” elements will take up lot of time. We, hence, use stack, which supports -
- Checking element at top.
- O(1) deletion of top element.
- Checking if its empty &etc.
The setter has implemented his own stack using array.
To contrast on what is clever in his simulation, let me compare it with a standard one.
A standard/normal simulation will go like-
- For all days from 1 to N-2, traverse the array from left to right, checking for condition.
- If condition is true, i.e, element can be deleted, delete it and update answer.
- Repeat until no more elements are deleted in an iteration.
In worst case, when only 1 element is deleted from the array each day, this will traverse the entire array N-2 times, which means its complexity is O({N}^{2})
What @kingofnumber 's implementation does is-
- For the entire length of array, N, do the following-
- If stack has only 1 element, push this element and go back to 1.
- If stack has more than 1 element, check if the element at top of the stack can be deleted. If yes, delete it, update answer. Now check if the new element at top can be deleted or not. If yes, delete it as well, updating the answer. Keep doing this until no more elements can be deleted.
- Insert A_i into the stack. Go to step 1.
Essentially, he calculates answer for all delete-able elements, between the two bigger elements then and there. Once an element is deleted from stack, its not wasting any more operations in traversing it etc. He just iterates over the array once, before adding any element to the stack, checks if the element at top of stack (which will be between Second-topmost element of stack, and current element A_i). It will calculate answer for all elements possible. Once no more deletions are possible w.r.t. current “boundary elements” (Second-topmost element at stack and A_i), he pushes A_i to the stack.
We can clearly see that, each element is pushed into the stack once, and hence deleted at most once as well. No useless iterations are done, as an element is visited only if-
- Its the current element at top of stack. Its done in O(1)
- All elements pushed after this element are deleted and we’re checking if this can be deleted as well. If yes, we will delete it, and continue the check, else we will immediately terminate the search. O(X) where X= Number of deleted elements.
The elements which remain in stack, at the end of simulation, will not be deleted no matter the number of days. For them, the answer is 0.
By above, we prove that the complexity of setter’s code is O(2*N)\equiv O(N)
SOLUTIONS:
For immediate availability of setter and tester’s solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them.
Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int T;
int n,nn;
int arr[100100];
int idx[100100];
int sol[100100];
int tmp[100100],s=0;
int tmp_idx[100100];
int sol2[100100];
int arr2[100100];
int st[100100],g=0;
int dy[100100];
int idd[100100];
int sm_n=0;
int main(){
//freopen("05.txt","r",stdin);
//freopen("05o.txt","w",stdout);
T=readIntLn(1,1000);
while(T--){
//cin>>n;
n=readIntLn(1,100000);
for(int i=0;i<=n;i++){
sol2[i]=0;
}
sm_n += n;
s=g=0;
assert(sm_n<=100000);
nn=n;
for(int i=0;i<n;i++){
//cin>>arr[i];
if(i==n-1){
arr[i]=readIntLn(1,1000000000);
} else {
arr[i]=readIntSp(1,1000000000);
}
arr2[i] = arr[i];
idx[i]=i;
}
/*bool found=true;
int cnt=0;
while(found){
found=false;
cnt++;
s=0;
for(int i=0;i<n;i++){
if(i>0 && i<n-1 && arr[i-1] > arr[i] && arr[i] < arr[i+1]){
sol[idx[i]] = cnt;
found=true;
} else {
tmp[s]=arr[i];
tmp_idx[s] = idx[i];
s++;
}
}
for(int i=0;i<s;i++){
arr[i] = tmp[i];
idx[i] = tmp_idx[i];
}
n= s;
}
for(int i=0;i<nn;i++){
cout<<sol[i]<<" ";
}
cout<<endl;*/
for(int i=0;i<nn;i++){
int day=1;
while(g > 1 && st[g-2] > st[g-1] && st[g-1] <arr2[i]){
day=max(day,dy[g-1]);
if(g > 1)
sol2[idd[g-1]] = day;
g--;
day ++ ;
}
st[g] = arr2[i];
idd[g] = i;
dy[g] =day;
g++;
}
for(int i=0;i<nn;i++){
cout<<sol2[i]<<" ";
}
cout<<endl;
}
assert(getchar()==-1);
}
Click to view
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge
using cat = long long;
#ifdef DONLINE_JUDGE
// palindromic tree is better than splay tree!
#define lld I64d
#endif
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int T;
cin >> T;
for(int t = 0; t < T; t++) {
int N;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; i++) cin >> A[i];
vector<int> nxt(N), prev(N);
for(int i = 0; i < N; i++) nxt[i] = i+1, prev[i] = i-1;
vector<int> rem, ans(N, 0);
vector<bool> to_rem(N, false);
for(int i = 1; i < N-1; i++) if(A[i-1] > A[i] && A[i+1] > A[i]) {
rem.push_back(i);
to_rem[i] = true;
}
for(int d = 1; d <= N-2; d++) {
vector<int> rem_nxt;
for(int i = 0; i < (int)rem.size(); i++) {
ans[rem[i]] = d;
int n = nxt[rem[i]], p = prev[rem[i]];
if(n < N && p >= 0) {
prev[n] = p;
nxt[p] = n;
int pp = prev[p];
if(pp >= 0 && A[pp] > A[p] && A[n] > A[p] && !to_rem[p]) {
rem_nxt.push_back(p);
to_rem[p] = true;
}
int nn = nxt[n];
if(nn < N && A[p] > A[n] && A[nn] > A[n] && !to_rem[n]) {
rem_nxt.push_back(n);
to_rem[n] = true;
}
}
}
rem = rem_nxt;
}
for(int i = 0; i < N; i++) cout << ans[i] << ((i == N-1) ? "\n" : " ");
}
return 0;}
// look at my code
// my code is amazing
Editorialist’s Solution will be put up on demand.
CHEF VIJJU’S CORNER 
1. Regarding claim that maximum days upto which an element is deleted is N-2.
Click to view
Assume worst case. Say, only 1 element is deleted every day. After N-2 days, we will be left with only 2 elements, with no element in between. By the rule, we can only delete elements in between of two larger elements. Hence, these 2 elements cannot be deleted.
2. Prove that there will be at least two 0's in the solution
3. Alternate explanation of setter’s solution
Click to view
Take it like this. For all i from i=0 to N-1 , he first checking if he can delete any element. If yes, he deletes it. A deleted element will, after deletion, waste no more operations as its gone. At max, an element can be deleted only once. Hence this makes the scenario “His solution is O({N}^{2}) impossible” as that’d mean all N elements are being deleted N times. Because he is quickly calculating answers wherever possible, deleting elements wherever possible while pushing elements in the stack, he is avoiding wastage of operations. The “one element is deleted only once” keeps his solution linear as he traverses the array.
4. Setter’s Notes-
Click to view
We will need to use stack. Let’s iterate over the array from left to
right. Let’s insert in it the first and second elements. Now starting
from third element we check if the top element in stack is less than
both new element and second-top element in stack then we remove it
from stack and the answer to that number is max of two numbers (say a and b) plus 1,
The first number, a, is the number of days until the top element in stack
became adjacent to second top, the second number, b is number of days
required that the new element became adjacent to the top element in
stack.
Now we continue removing the top element of stack as long as it’s less
than both new element and second top element in stack, after we stop
we insert the new element into stack.
5. Tester’s Notes-
Click to view
WEAKMID is solvable by clever simulation. The current state of the array can be kept as a linked list - deleting and checking adjacent elements is O(N). If we have the list of elements deleted on day d, we can delete them and check for each of their adjacent elements if they should be deleted on day d+1. Since there are only as many adjacent elements as deleted elements in any step, it’s O(number of deleted elements) = O(N).
Some sqrt solutions should also be possible, since in each step, either > \sqrt{N} elements are deleted or < \sqrt{N} relevant things change in the array.
6. Some similar problem on stack for practice-
- CUTPLANT - This problem’s editorial also has more reference problem.
- More will be added soon. Request communities’ help here.
