Hey Community

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

link

http://www.spoj.com/problems/IOPC1207/

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

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

#Here is your accepted solution

thanks @l_returns it actually worked but can you explain me why flip function that is 3rd mistake is required to be changed . I mean what was the issue in just writing this seg[si]=flip(ss,mid,l,r,2*si+1)+flip(mid+1,se,l,r,2*si+2);

@kunal12libra I am also looking for the reason why 3rd mistake needs update :)â€¦

but it was my hard work of bug finding in this type of codes which showed me the mistakeâ€¦

but I really donâ€™t know why previous didnâ€™t workedâ€¦

I had got same error once when I used lazy segtree and then Got AC after this changeâ€¦ Hence It was my observationâ€¦

best of luck for GM plants problem thoughâ€¦

now u must be able to solve gm plants by yourself