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

×

CUTPLANT- Editorial

6
4

PROBLEM LINK:

Div1
Div2
Practice

Setter- Stepan Filippov
Tester- Misha Chorniy
Editorialist- Abhishek Pandey

DIFFICULTY:

MEDIUM

PRE-REQUISITES:

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:

View Content

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?

  • Optimal query will have to set at least one plant to its required height. Hence, its value must be between one of the values $B_i$ such that $L\le i\le R$.
  • We further refine our first observation, claiming that the query height must be $max(B_i)$ for $L\le i\le R$. Because if its not so, one of the plants will be cut well below its required height!

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-

  • If the required height of $B_i$ is more than $B_H$.
  • If the plant height $A_i$ is less than $B_H$.

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.

  1. Make a deque/list/appropriate data structure which supports insertion and deletion at both ends.
  2. For all plants in range $1$ to $N$, do following-
  3. If my deque is not empty, and the current plant (at index $i$) being considered has a required height $B_i$ which is more than the height at the back of deque, keep popping from back of deque till height at back ($B_j$) satisfies $B_j \ge B_i$ .
  4. Now check if the height of plant at $i$, (i.e. $A_i$) is less than the required height $B_L$ at the front of deque. If yes, keep popping from front till this condition becomes false.
  5. After performing step 3 and 4, we can assure that we can make a valid query for all plants currently in the deque, because steps 3. and 4. assure that $B_i$ are stored in descending order, and that the height of final plant $(A_j)$ is sufficient enough to execute query from start to end of deque.
  6. Now check if required height of the plant ($B_j$) at back of deque is equal to required height of plant in consideration ($B_i$). If yes, then we can successfully make a query from the last element of deque to current element, saving an operation. If we find that $B_i \neq B_j$, then we cannot save an operation and must increment time needed by $1$.

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-

  1. If required height and current height of plants being considered are equal, do nothing. Else, goto 2.
  2. If this is the first element being considered, or if the required height $B_i$ of this element is not equal to the required height of previous plants, $B_z$ which we were considering, add $1$ to answer and set $B_z=B_i$ and set the index of plant being considered (index $z$) to $i$. Go back to 1. and consider next plant.
  3. If required height of this plant $B_z$ is equal to required height of previous plant being considered, get the index $y$ to that previous plant in the original array (He had made pairs of $< B[i], i> $ for this purpose). Now check if we can make a valid query from the previous plant's index $z$ to this index $y$. This checking happens in $O(\sqrt{N})$ on basis of the observations about invalid queries I mentioned earlier (i.e. if there is a $B_k$ in between which is more than $B_z$ preventing valid queries across it, or if current height $A_k$ of some plant is less than the required height $B_z$). If the query is possible, do nothing, else add $1$ to answer and set current plant of consideration to plant at index $y$. (i.e. set $B_z=B_y$ and $z=y$.)

$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 non-increasing 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:

Setter
Tester
Editorialist

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 6-7 lines for me. This question is really appreciable in this regard, and we must appreciate the setter for such an interesting question.
2. As you can see, the setter and tester have $O(N\sqrt{N})$ and $O(NLogN)$ solutions respectively. The best part of being an editorialist is you can claim the best solution for your share :D :p
3. I will like to leave out some of the apt problems on data structures which I found elegant-

This question is marked "community wiki".

asked 10 Apr '18, 20:58

vijju123's gravatar image

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

edited 20 Apr '18, 18:39

admin's gravatar image

0★admin ♦♦
19.8k350498541

fix the solution links please. They currently redirect to the (inaccessible) problem setting subdomain

(17 Apr '18, 20:39) nilesh31055★

Solution links arent in my hands. I have to wait till @admin uploads the solutions on server for you.

(18 Apr '18, 16:58) vijju123 ♦♦5★

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 co-ordinate 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.

link

answered 17 Apr '18, 18:49

sdssudhu's gravatar image

6★sdssudhu
1.1k310
accept rate: 15%

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

Can you please post the link to your solution? Also why did you use co-ordinate compression here?

(15 May '18, 19:34) sorb19974★

Solved using set of propogating updates/cuts and only updates in the range [a[i],b[i]] would propogate further. So removing all others, using lower_bound and upper_bound .

int cnt=0;
set < int > s;
int i=0;
while(i < n){
    s.erase(s.begin(),s.lower_bound(b[i]));
    s.erase(s.upper_bound(a[i]),s.end());
    if(s.size()) {
        set < int > ::iterator it = s.lower_bound(b[i]);
        if(it != s.end()) {
            a[i] = *it;
        }
    }
    if(a[i] != b[i]) {
        cnt++;
        a[i] = b[i];
        s.insert(b[i]);
    }
    i++;
}
link

answered 17 Apr '18, 23:24

pk_godara's gravatar image

4★pk_godara
261
accept rate: 50%

1

Yes, this was also one of the seen solutions. Thanks for sharing :)

(18 Apr '18, 00:19) vijju123 ♦♦5★

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.

link

answered 19 Apr '18, 00:48

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

edited 19 Apr '18, 01:02

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

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

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

Okk. You live with secret. I live with "On a birds eye view, just about nodes."

(19 Apr '18, 02:41) aryanc4035★
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) vijju123 ♦♦5★
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) taran_14076★

Googling - segment tree golden rule. Takes me here https://discuss.codechef.com/questions/103871/how-to-start-with-segment-trees :)

(19 Apr '18, 05:06) aryanc4035★
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) vijju123 ♦♦5★
showing 5 of 11 show all

Why a N^2 approach not work here? Time limit is 2 secs!!

link

answered 17 Apr '18, 18:03

ayushgoyal1703's gravatar image

4★ayushgoyal1703
222
accept rate: 0%

$O({N}^{2})$ approach needs ${10}^{10}$ instructions. Typically such solutions take between $10-20secs$ to pass.

(17 Apr '18, 18:08) vijju123 ♦♦5★

10-20 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) ayushgoyal17034★

Can We solve it by Divide and Conquer ?

(17 Apr '18, 18:31) project81★

@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) swapnilrustagi4★

I didnt saw a divide and conquer solution. @project8

(17 Apr '18, 19:58) vijju123 ♦♦5★

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

link

answered 17 Apr '18, 20:37

nilesh3105's gravatar image

5★nilesh3105
716210
accept rate: 31%

So we are all just waiting for @admin to link the solutions up xD

(17 Apr '18, 21:07) vijju123 ♦♦5★

@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) aryanc4035★

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

link

answered 17 Apr '18, 22:03

apmeyer27's gravatar image

4★apmeyer27
11
accept rate: 0%

Yes, its my favourite cause of that :)

(17 Apr '18, 22:20) vijju123 ♦♦5★

can someone help me getting 1 test case wrong. link text

link

answered 18 Apr '18, 15:03

aditya_dope's gravatar image

3★aditya_dope
1
accept rate: 0%

1 4 5 3 5 5 3 1 3 3

Your code prints 3 while only 2 queries (ranges [1,4] and [2,2]) are needed

(18 Apr '18, 16:29) vijju123 ♦♦5★

thanx a lot man found my mistake

(18 Apr '18, 16:53) aditya_dope3★

I need help, i don't know why my algorithm doesn't work.

I can explain what it does if you need. Thanks in advance :D.

My code

link

answered 20 Jun '18, 09:22

josesoto's gravatar image

4★josesoto
1
accept rate: 0%

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:

×2,657
×1,768
×1,409
×311
×289
×40
×17

question asked: 10 Apr '18, 20:58

question was seen: 5,924 times

last updated: 20 Jun '18, 09:22