I have understood the 2 lemmas in the editorial: https://discuss.codechef.com/questions/91508/mixflvor-editorial
I am not able to understand why the setter wants to use 2 stacks in the first place and what exactly he does with those two stacks. Could someone please explain the editorial after the 2 lemmas part.Also, would it be possible to solve it just by keeping a start and stop pointer without any stack and still get AC?
gonecase
when he says-
"we can easily supporting add new elements and deleting the element which is added most recently by using stack "
he meant that stacks are fit for our purpose here as with .push() function he can add a new element in it and with .pop() he can remove the latest/most-recently-added element.
What I got from reading is that he made two stacks headed (named) forward and backward. Whenever he felt need to add new element, he added it to “forward” stack, and when he felt need to pop element, he’d pop it from “backward” stack. [Remember- pop will always remove the most recent element in both, forward and backward stack]. If backward stack is empty, he’d move all elements of forward stack to backward stack, from top (1 by 1), and as a consequence of it, the order in backward stack would be reverse of what it originally was in forward stack.
(Eg- Lets say in forward stack order was {1,2,3} [with first element being at top and last at bottom]. Now, we put elements from here to backward stack, starting from top.
First step- Forward stack {2,3} backward stack {1}
Step 2 - Forward stack {3} backward stack {2,1} (elements are added from top of stack. Hence, older element gets push down.)
Step 3 Forward stack {}, backward stack {3,2,1}
Then he talked about how pop() function removes most recently added element and then he talks about implementing its full solution (that para was ambiguous to me, getting many interpretations. So I am not explaining it in my answer, sorry for that bud.)
1 Like