SPOJ GM PLANTS PROBLEM

general
,
1

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
2

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…

3

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…

4

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)

5

@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.

6

okay… let me check… btw was my explanation proper ?

7

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

8

okay welcome

9

are you able to find the mistake

10

#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
11

#Here is your accepted solution

12

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,2si+1)+flip(mid+1,se,l,r,2si+2);

13

@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…

14

best of luck for GM plants problem though…

15

now u must be able to solve gm plants by yourself :slight_smile: