You are not logged in. Please login at www.codechef.com to post your questions!

×

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

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

View Content

Tester

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".

asked 26 May '18, 17:14

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 12 Jun '18, 17:49

admin's gravatar image

0★admin ♦♦
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) rj254★
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) vijju123 ♦♦5★

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

link

answered 26 May '18, 23:11

sarthakmanna's gravatar image

6★sarthakmanna
1.0k115
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) vijju123 ♦♦5★

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) sarthakmanna6★

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

(27 May '18, 15:12) vijju123 ♦♦5★

Can you share it?

(27 May '18, 19:54) sarthakmanna6★
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"<<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 :p

(27 May '18, 20:07) vijju123 ♦♦5★

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

link

answered 27 May '18, 00:56

kukreja_vlk's gravatar image

3★kukreja_vlk
604
accept rate: 22%

edited 27 May '18, 00:56

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)

link

answered 28 May '18, 15:28

adecemberguy's gravatar image

2★adecemberguy
725
accept rate: 12%

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 !!!!

link

answered 30 May '18, 12:11

srvptk's gravatar image

4★srvptk
102
accept rate: 0%

edited 30 May '18, 12:14

Hackerman.....XD

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

(30 May '18, 14:55) sarthakmanna6★

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) vijju123 ♦♦5★
1

hahaha @vijju
nice hack....
nice hack @srvptk too.. :)

(31 May '18, 20:28) l_returns5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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