×

# WEAKMID- Editorial

Tester- Jakub Safin
Editoiralist- Abhishek Pandey

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-

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.

View Content
View Content

Editorialist's Solution will be put up on demand.

# CHEF VIJJU'S CORNER :D

1. Regarding claim that maximum days upto which an element is deleted is $N-2$.

View Content

2. Prove that there will be at least two $0's$ in the solution

3. Alternate explanation of setter's solution

View Content

4. Setter's Notes-

View Content

5. Tester's Notes-

View Content

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. :)
This question is marked "community wiki".

15.5k12066
accept rate: 18%

19.8k350498541

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

(29 May '18, 12:06) 4★
1

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

(29 May '18, 21:02)

 1 Well, well, well... My brute force solution: https://www.codechef.com/viewsolution/18664537 Then, I don't know why, but I tried this approach: https://www.codechef.com/viewsolution/18664962 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 answered 26 May '18, 23:11 1.0k●1●15 accept rate: 38% 1 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! :) (26 May '18, 23:22) 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. (27 May '18, 03:06) Lol, thats funny XD. Reminds me of a very funny incident XD (27 May '18, 15:12) Can you share it? (27 May '18, 19:54) 1 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"<
 0 @vijju123 The editorial link on the Practice page is not correctly redirecting. answered 27 May '18, 00:56 60●4 accept rate: 22%
 0 Little space optimization can be made in tester solution by removing vector 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) answered 28 May '18, 15:28 72●5 accept rate: 12%
 0 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 !!!! answered 30 May '18, 12:11 4★srvptk 10●2 accept rate: 0% Hackerman.....XD Have seen all your submissions. You've really worked hard for drawing this conclusion. (30 May '18, 14:55) Sir yes Sir !!! I really made a lot of submissions. (31 May '18, 08:55) srvptk4★ This is a very correct place to apply "Binary Search" :p :p XD You can find the exact value of $max(N)$ in $\lceil log_2N \rceil$ submissions :) (31 May '18, 20:10) 1 hahaha @vijju nice hack.... nice hack @srvptk too.. :) (31 May '18, 20:28)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×862
×191
×173
×172
×102
×12

question asked: 26 May '18, 17:14

question was seen: 889 times

last updated: 12 Jun '18, 17:49