WEAKMID- Editorial

PROBLEM LINK:

Div1
Div2
Practice

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. :slight_smile:

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-

  1. For all days from 1 to N-2, traverse the array from left to right, checking for condition.
  2. If condition is true, i.e, element can be deleted, delete it and update answer.
  3. 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-

  1. For the entire length of array, N, do the following-
  2. If stack has only 1 element, push this element and go back to 1.
  3. 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.
  4. 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.

Setter

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);
} 

Tester

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 :smiley:

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. :slight_smile:
3 Likes

Well, well, well…

My brute force solution: CodeChef: Practical coding for everyone

Then, I don’t know why, but I tried this approach: CodeChef: Practical coding for everyone

Bingo! How could such a solution even fetch a single green row?

Now… My secret weapon… Toss…

Finally, finally, finally, on the 12th submission…
https://www.codechef.com/viewsolution/18665708

I could not control my laughter for a minute…XD

1 Like

@vijju123
The editorial link on the Practice page is not correctly redirecting.

Little space optimization can be made in tester solution by removing vector<bool> to_rem and instead using something like this :=> nxt[p] = n; prev[n] = p; inside this if block if(n < N && p >= 0) (CTRL-F} to find)

Size of input of test case 5 is 99983 … So according to the two solutions of Sarthak
Pass all the solutions having size not equal to 99983 through solution 1 and the one having size n=99983 will be passed through solution 2 … And you will get 100 points … ;D… Now its hacked !!!

Your code is very poorly formatted and ill-structured. Its hard to see whats the point you’re trying to make. Can you at least put comments in there or perhaps describe it here? Thanks! :slight_smile:

1 Like

You need not go through the whole code. I tried to point out that, with the first solution, I couldn’t pass Task 5 only. With the second solution, I could clear Task 5 and 6 but failed to clear the rest.

So, I designed my code to randomly assign the task to either solution 1 or 2. This solution would fail most of the time because if any task other than Task 5 or 6 is assigned to Sol 2, it would give a WA. Also, if Task 5 is assigned to Sol 1, it would give a TLE.

Therefore, I submitted the same code again and again, hoping for the perfect match for each task. The 12th submission made my day.

Lol, thats funny XD. Reminds me of a very funny incident XD

Can you share it?

There was a particular CF contest happening that day. Me and my roomies were like “Too tired to participate seriously”, so we all made a fake account and had a fun time. Now, problem A was a Yes/No Problem, so we did like-

if (rand()%2==0)
   cout<<"Yes"<<endl;
else 
   cout<<"No"<<endl;

Got till pretest 8 there XD.

For next problem, we submitted a very “lol” solution which god-knows how passed. And then we tried to hack a already correct solution and lost 500 points. But at the end of contest we thoroughly enjoyed ourselves :stuck_out_tongue:

1 Like

I am curious about sqrt(n) solutions mentioned in testers notes, can you add that too with explanation ? @vijju123 @xellos0

He just said that it could be a possibility. Will have to analyze more solutions to see if anyone did square root. Or gimme some time to think :slight_smile:

1 Like

Hackerman…XD

Have seen all your submissions. You’ve really worked hard for drawing this conclusion.

Sir yes Sir !!!
I really made a lot of submissions.

This is a very correct place to apply “Binary Search” :stuck_out_tongue: :stuck_out_tongue: XD

You can find the exact value of max(N) in \lceil log_2N \rceil submissions :slight_smile:

hahaha @vijju
nice hack…
nice hack @srvptk too… :slight_smile:

1 Like