PROBLEM LINK:Setter Stepan Filippov DIFFICULTY:MEDIUM PREREQUISITES:Square Root Decomposition, or Segment Trees, or Data Structures such as Deque PROBLEM:Given an array $A[]$ representing height of plants, and another array $B[]$ representing the required height of plants, find minimum time taken to convert array $A[]$ to array $B[]$ using the specified operation. The operation is, choose valid indexes $L$ and $R$ and a target height $H_i$ and cut all plants in the range to height $H_i$. Their initial height must be $\ge H_i$ for this to be valid. QUICK EXPLANATION:We can clearly see that the only way of saving time is to make a valid operation in which maximum number of plants need to be cut to same height $B_i$. The problem hence boils down to, making the optimal query by finding such $L$ and $R$ and checking if its valid or not. The case where answer is not possible is trivial to check. EXPLANATION:So, as some of you might have perceived, we will be discussing three approaches here. First we will discuss my approach which is $O(N)$, and then we will see Misha's (tester) $O(N\sqrt{N})$ approach and finally discuss how we can convert/optimize it to become $O(NlogN)$ approach of the setter. 1. Editorialist's Solution The very first thing we see is if the answer is possible or not. Clearly, no answer is possible if for some plant $i$, its current height $A_i$ is less than the required height $B_i$. If its possible, we proceed further. First I will try to give the intuition. See what the problem demands. How can we save time? We can save time for every valid query which sets multiple plants to same required height $B_i$. Hence the problem boils down to proper identification of $L$ and $R$ for the query, and checking if such a query can be made or not. The first problem which we face in brute force is that, to verify the query is possible, we might have to check all plants and their required heights in range of $L$ to $R$. Not to mention getting exact $L$ and $R$ for query might seem problematic to some. Perhaps we can make some observations first to make our life simpler?
Also, imagine if we "have got the required $L$ and $R$" where we got multiple plants which are to be set to same height $B_H$ and are checking if the next element can be included in the range. When will we discard this element at index $i$ from being inside the valid query? We will do so if
With these two principles in mind, lets move towards the solution. I will first describe my algorithm, and then we will discuss what it does, and why is it correct.
Why is this correct? Notice that, we maintain the condition that, element is in the deque only if its possible to make a query from plant $B_L$ at start of deque to plant at end of deque/plant being considered right now ($B_R$ or $B_i$). This is possible because $B_i$ gets stored in descending order in deque. Then, we also check before adding a plant if its possible to execute a query from start of deque to it by making sure that the current height of plant being added ($A_i$) is enough to support query for plant at index $L$ (i.e. $A_L$). $L$ and $R$ are, obviously, starting and ending range of query. Why descending order? We will discuss this in Setter's approach as well. I will mention my intuition here. Lets take a simple example, we have this configuration of elements in array $B[]$ such that $B[]=\{B_j,B_i,B_j\}$ with $B_j < B_i > B_j$. Can we make a query from $B_j$ at left of $B_i$ to $B_j$ at right of $B_i$ to save time? No, we cannot as it would cut plant $A_i$ to a height less than $B_i$. Hence, once we encounter a $B_i$, we can safely eliminate all previous $B_j$ which are smaller than $B_i$ as we cannot make a query from them across $B_i$. Also, any queries which could had been done before $B_i$ had already been considered when we added the element $B_j$ and every other element thereafter. Hence, the algorithm is correct. $Time$ $Complexity$ $O(N)$ Tester's Aprroach The tester follows Square root decomposition. If you got the intuition (even if only a little) of my solution, then this one is even easier. What Misha did after taking input is, he made two buckets. First bucket $sqa[]$ stores minimum height of plant $A_i$ in the range of bucket, and second bucket $sqb[]$ stores the maximum of the required heights height $B_i$ in range of bucket. Then, he checks if the configuration is valid or not. While doing so, he also makes a vector of pairs, which stores $< B[i], i> $. He sorts this vector in descending order. Now, he does the following
$Time$ $Complexity$ $O(N\sqrt{N})$ Setter's Solution Basically, the change is in his' and tester's solution is in the step where we check the possibility of queries. He optimizes the step where we check if the query is valid or not. What he observed was, that, consider two queries which set height of plants (in some range) to $H_i$ and $H_j$. Now, suppose $H_i$ happens after $H_j$, and $H_i > H_j$. He observed that, we can swap the order of these two queries, i.e. execute query $i$ before query $j$ without any effect on the final answer. This is because, any plants getting affected by both query $i$ and query $j$ can be ultimately reduced to height $H_j$ because $H_i > H_j$. He uses this to argue that, there always exist a solution where queries are executed in nonincreasing order of heights $H_q$. That is, he will execute query which with greatest height $H_q$ first, &etc. This also justifies tester's step of sorting the vector on basis of required heights $B_i$, as each optimal query will make height ($A_i$) of at least one plant equal to its corresponding required height $B_i$. With this clear, the only difference comes in checking if the query is valid or not. If we closely see what tester did, and what my definitions say about invalid queries, we can reduce it to finding maximum required height $B_i$ in the range of $[L,R]$ and minimum current height $A_i$ in the range $[L,R]$ where $[L,R]$ are the range of query. This can be easily done via appropriate data structure like Segment Tree & similar. $Time$ $Complexity$ $O(NLogN)$ SOLUTION:Commented Solution of Editorialist CHEF VIJJU'S CORNER:1. This is a very fit data structure problem, and is really beautiful in this way. There are very little problems where you can solve the question elegantly using the apt data structure. The correct code of algorithm with deque was hardly 67 lines for me. This question is really appreciable in this regard, and we must appreciate the setter for such an interesting question.
This question is marked "community wiki".
asked 10 Apr '18, 20:58

I solved this one a bit differently. My main observations were same as in @vijju123 's and the setter's solution. But another observation I made is that for reducing a plant to height x only a cut of height x matters. It is because you may cut any number of times you want but until the height of cut is x it requires atleast 1 more cut. Hence what I did was I stored all the lengths in a vector(after coordinate compression). Then I calculated next greatest element with respect to array B(using stack). Now after this just traverse all the vectors and check what all indices can be grouped together in a single cut. The answer is number of different cuts that have to be made. answered 17 Apr '18, 18:49
Yup, I knew of that solution as well, but the deque solution was very simple to code, explain and understand, hence I chose this one. After all, I cant (and shouldnt!) discuss all the possible solutions myself, isnt it :) xD
(17 Apr '18, 19:07)
Can you please post the link to your solution? Also why did you use coordinate compression here?
(15 May '18, 19:34)

Solved using
answered 17 Apr '18, 23:24

If someone wants to visualise @vijju123 's O(n) soln working. https://ideone.com/Sxb6w8 . I have added enough printf statements after each operation such that it can be visualized. P.S. I was able to understand this only when run printed everything. answered 19 Apr '18, 00:48
1
I accidentally gave @admin wrong link and didnt realize it till now. I had a commented solution for easier understanding. Will update editorial to add that. Thank you for your initiative aryan :)
(19 Apr '18, 01:12)
1
The base of the solution is that, we are maintaining in the deque elements in form such that we can execute query from one part of deque to another. In case of any violation, we remove the required elements. You can also look at tester square root solution  it feels a lot more natural in thinking as well :) One of my incentives to give 3 approaches. Even if one of them is understood, then editorials job is done. Rest can be left for interested ones :)
(19 Apr '18, 01:19)
1
square root was the one which I used during the contest. And what I feel is that square root and Segment Trees goes hand in hand. With proper choice of bucket size. Question can be done using square root which is intended for Segment Trees. If time limit is not very tight. :)
(19 Apr '18, 01:37)
Thats true, though I feel Segment tree is more intuitive if you know the golden rule for it. Square root always tends to give me implementation headaches xD
(19 Apr '18, 01:44)
Can you please provide us Golden Rule ?? Because I always get intuitive for Square Root. And end up implementing it. And find soln with segment tree used.
(19 Apr '18, 01:48)
1
Its a secret which I found after digging 10 blogs on seg tree :p . On a birds eye view, just about nodes.
(19 Apr '18, 02:34)
Okk. You live with secret. I live with "On a birds eye view, just about nodes."
(19 Apr '18, 02:41)
2
Nah, I wanted to see what you'd say on that :p I have no right to keep it secret since I came to know it because someone else shared :) "Its all about defining relationship between child and parent nodes. What data should I store, so that using that, if I have data of child nodes, I can derive data of parent node. The base cases, are leaves, and are trivial. If we get the relation, we can advance from leaf to next leve, from there to next...and hence to the root. You can, surely, make ad hoc solution, but this is the concept of segment tree which will help you throughout :) "
(19 Apr '18, 03:19)
1
I guess i have read these lines from the same source as vijju123 PS: Nice concept "Chef vijju's corner". Your editorials are such a beauty.
(19 Apr '18, 04:09)
Googling  segment tree golden rule. Takes me here https://discuss.codechef.com/questions/103871/howtostartwithsegmenttrees :)
(19 Apr '18, 05:06)
1
Awwwh. Thank you @taran_1407 . Its a big compliment hearing you liked them :). Yup, Chef Vijju's Corner started from my first editorial which I wrote for ICPC Amritapuri ones because practically I was a free soul there. @admin and @dpraveen mentored me a lot, and they let me have my scope of creativity. Since then, I try to mention anything  which I cant mention in official part due to length issues in bonus section. I feel it might be useful to some :) Nice catch @aryanc403 xD xD. Very impressive! :D
(19 Apr '18, 16:04)
showing 5 of 11
show all

Why a N^2 approach not work here? Time limit is 2 secs!! answered 17 Apr '18, 18:03
$O({N}^{2})$ approach needs ${10}^{10}$ instructions. Typically such solutions take between $1020secs$ to pass.
(17 Apr '18, 18:08)
1020 secs for a N^2 approach?? But didn't in 1 sec we can do like 10^5 to 10^6 iterations?
(17 Apr '18, 18:30)
Can We solve it by Divide and Conquer ?
(17 Apr '18, 18:31)
@ayushgoyal1703 You can easily do 10^7 iterations in under a second  provided you each iteration does not consist of too many statements requiring heavy computation. 10^10 is 1000 times 10^7, so it's only normal that 10^10 would take much more 2 seconds to finish.
(17 Apr '18, 19:53)
I didnt saw a divide and conquer solution. @project8
(17 Apr '18, 19:58)

By solution was same as the editorialist one but I took the lazy route and used a set<> instead so that I didn't have to think about front and back :D The $O(N \sqrt N)$ looks interesting though and is probably a more generic one answered 17 Apr '18, 20:37
So we are all just waiting for @admin to link the solutions up xD
(17 Apr '18, 21:07)
@nilesh3105 https://www.codechef.com/viewsolution/18279391 You can look at it here. Although there is code copy pasted trice and poorly commented. But its sqrt decomp. If you want exactly O(Nsqrt(N)). Just do a change in value of C in first line.
(18 Apr '18, 17:34)

Once I submitted my final queue/stack solution I couldn't believe how simple it was. I love the problems that take a long time to understand but end up being elegant and clean. My solution: https://www.codechef.com/viewsolution/18275106 answered 17 Apr '18, 22:03

fix the solution links please. They currently redirect to the (inaccessible) problem setting subdomain
Solution links arent in my hands. I have to wait till @admin uploads the solutions on server for you.