# SPOJ GM PLANTS PROBLEM

Hey Community
I was practicing questions on segment tree and I come across this question ,

I know that i need to make 3 segment tree here each for every coordinate but i am unable to proceed further . I have checked out some github solutions as well but unable to understand . If anyone can tell the algorithm it will be highly appreciated . Also this is a very interesting question so all those who love fancy problem statements this is your type of question . Thanks in Advance

1 Like

This can be done by lazy propagationâ€¦ similar to FLIPCOIN problemâ€¦
In flipcoin we have two similar segment trees where one is lazy tree and one is seg treeâ€¦ Try searching for lazy propagation for flip coin and you will get its solutionâ€¦ here is my solution for FLIPCOIN in case if you need to take a referenceâ€¦

Talking about your question consider it as three test case of FLIPCOIN per test case(of GM plants)â€¦ a
as you nicely said each for each coordinateâ€¦ now by this you will know how many x co-ordinates were flipped from given rangeâ€¦ then how many yâ€¦ and how many zâ€¦ and from that you can count red plants easilyâ€¦

Do let me know if u need more explanation on lazy propagation for FLIPCOIN or you didnâ€™t understood any part in my explaination or in lazy propagationâ€¦ According to my suggestion first understand FLIPCOIN and then you can easily solve GM plantsâ€¦

and i would like to point out that here no need to build the segtreeâ€¦ as making all elements of the segtree array 0 will doâ€¦

If you get FLIPCOIN then you just need to find formula or method for computing red plants if I gave you that number of x coordinates flipped(color changed) and number of y and number of zâ€¦ (They will have only flip or no flipâ€¦ as flip of flip is equal to no flip)

@l_returns I tried this question and when i code this one : https://www.codechef.com/viewsolution/18634489

This is pretty much similar to your solution but my segment tree has some issues you can see it if you print the entire tree and i am getting wrong answer . Can you pinpoint where is the mistake.

okayâ€¦ let me checkâ€¦ btw was my explanation proper ?

I have tried flipcoin right now . After this I will use it for the question I asked and will let you know if I understand your explanation . Btw thanks for flipcoin question it really helped me understanding lazy segment trees a lot

okay welcome

are you able to find the mistake

#1)

# the printing loop in comment has seg[i] which should be seg[j]

#2)
remove
` seg[si]=query(ss,mid,l,r,2*si+1)+query(mid+1,se,l,r,2*si+2); return seg[si]; `
#and replace it with

`````` return query(ss,mid,l,r,2*si+1)+query(mid+1,se,l,r,2*si+2);

``````

#3)

### In flip functionâ€¦

#replace
`seg[si]=flip(ss,mid,l,r,2*si+1)+flip(mid+1,se,l,r,2*si+2);`
#with

``````   flip(ss,mid,l,r,2*si+1);
flip(mid+1,se,l,r,2*si+2);
seg[si]=seg[2*si+1]+seg[2*si+2];

``````
1 Like