FLIPCOIN lazy propagation help

help
, , ,
1

can anyone tell me why this approach is giving me WA https://www.codechef.com/viewsolution/16576631
while this approach is giving me AC https://www.codechef.com/viewsolution/16576566
why the first approach is wrong thanks in advance
question link https://www.codechef.com/problems/FLIPCOIN

2

It seems that you have assumed coins are only flipped once from tails to heads. But a coin that has been flipped to heads can be flipped again, which makes it tails. Of course it can be flipped again in the future. Your lazy propagation should be designed to handle that.

3

hellow @meooow bhaiya can you explain where i am not flipping the heads to tail

4

@manaranjanfav

[Here’s][1] your code in which i made the required changes of 2 lines in update and query part each and got AC.

Basically what i did was, changed from

if(start!=end) 
     {
      lazy[2*index+1]=1;
      lazy[2*index+2]=1; 
     }

to

if(start!=end) 
     {
      lazy[2*index+1]=!lazy[2*index+1];
      lazy[2*index+2]=!lazy[2*index+2]; 
     }

Because in your code you are always assigning 1 to the child nodes while they can also be 0(head or tail and not only head or only tail) so i am using ! operator as,
!1 = 0 and !0 = 1 .

Upvote if this solves your query.
[1]: https://www.codechef.com/viewsolution/16578109

1 Like