FLIPCOIN - the definite topic for us to learn Segtrees!!

general
11

@shubham99

ST[node] = (end-start+1) - ST[node];

This denotes the flipping of coins in range. Like it’s already stated
new heads = total coins in curr node - no of old heads

12

Can anyone plz help me out…i am getting time limit exceeded here is my code
https://www.codechef.com/viewsolution/15551011

Thanks in advance.

13

Hello all,

Can someone please help me with some sample test cases to test this code with? I tried lots of test cases but I can’t seem to get it accepted. It appears to pass all the cases I have designed.

https://www.codechef.com/viewsolution/16573912

Regards,
Ruddra

1 Like
14

Can this be done using Binary Indexed tree?

15

this is nice :slight_smile: So my “high-level” explanation is not very wrong :smiley:

16

@u_seem_surprsd, what is the node passed to the query and update functions when we call them?

Do we use the value of the start point of query as node?

I really want to use this pseudo-code along with both our explanations to finally crack this and also build several topics with detailed solutions for other problems here and on SPOJ, maybe this will be possible with your help

17

@kuruma whenever we make an update or query we give the starting node of the segment tree eg : updateLazy(1, 0, N-1, 3, 11).The ST here is built like ST[1, 2, 3, 4, 5, 6, 7…]

                          1 [0...N-1]

     2 [0....N/2]                            3 [(N/2)+1....N-1]

4 [0...N/4]       5 [(N/4)+1...N/2]   *****

here the node keeps track of intervals, and when querying we go down the tree looking for the interval we need. link to my solun : CodeChef: Practical coding for everyone

1 Like
18

Thanks a lot, this is slowly starting to make sense :smiley:

19

Why do we need to keep track of how many flips were made?

20

CAn anyone explain why have we done this ?

ST[node] = (end-start+1) - ST[node];

I understand we are updating the seg tree here but why are we subtracting the value (end - start +1).

21

I have solved it.

23

Hi there, this was really a very good video. Thanks for making it.
https://www.youtube.com/results?search_query=flip+coin+codechef

25

There’s no segtree solution for flipcoin in python, the one I tried (iterative, algorithm from codeforces) gave TLE. Did anybody manage to get an AC in python3 using segtree or are the constraints too tight?

User @alexthelemon has a solution using BIT so I’m looking to figure that out.

27

A good resource for learning segment trees

1 Like
28
29
30 
	lazy[node<<1] = 1-lazy[node<<1];
	lazy[(node<<1)+1] = 1- lazy[(node<<1)+1] ;

@grimmjowwww what are we doing by this ??

31

Great! Interesting how you have used the condition for lazy update → (end-start+1) - ST[node]
Is it possible for any range based problem to have a suitable condition for lazy update?

32

Hello,can you please help me, i am not able to spot my mistake in the code.
https://www.codechef.com/viewsolution/48669530
Thanks in advance.

33

I am not able to find my mistake in the code.
Can anyone please help me out.
Thanks in adavance.
https://www.codechef.com/viewsolution/48669530