PROBLEM LINK:Setter Hasan Jaddouh DIFFICULTY:EASYMEDIUM PREREQUISITES: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_{i1}>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 datastructures 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 $1D$ and $2D$ array, then stop. Go to prerequisites 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
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 $N2$ (Why?) $\implies$ We only need to cleverlysimulate for first $N2$ days. We note that if we use arrays, then frequent reallocation, change of indexes or looping over already "deleted" elements will take up lot of time. We, hence, use stack, which supports 
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
In worst case, when only $1$ element is deleted from the array each day, this will traverse the entire array $N2$ times, which means its complexity is $O({N}^{2})$ What @kingofnumber 's implementation does is
Essentially, he calculates answer for all deleteable 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 Secondtopmost 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" (Secondtopmost 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
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. Editorialist's Solution will be put up on demand. CHEF VIJJU'S CORNER :D1. Regarding claim that maximum days upto which an element is deleted is $N2$. 2. Prove that there will be at least two $0's$ in the solution 3. Alternate explanation of setter's solution 4. Setter's Notes 5. Tester's Notes 6. Some similar problem on stack for practice
This question is marked "community wiki".
asked 26 May '18, 17:14

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
Your code is very poorly formatted and illstructured. 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
Got till pretest 8 there XD. For next problem, we submitted a very "lol" solution which godknows 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 :p
(27 May '18, 20:07)

@vijju123 The editorial link on the Practice page is not correctly redirecting. answered 27 May '18, 00:56

Little space optimization can be made in tester solution by removing answered 28 May '18, 15:28

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