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

general
8

we are subtracting because we want to get the total no. of elements in the range.

9

Hi,

I made a video editorial on segment trees and how they solve this question. You can have a look at it here:

Segment Tree - Range Queries with Lazy Updates - YouTube

Cheers!

5 Likes
10

Hey,

Could someone please help me, I just read about segment tree and did this problem using segment tree. But I am getting time limit exceeded.
Here is my code:
http://code.geeksforgeeks.org/7dCRT4

Thanks in advance.

Vipul

1 Like
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] ;

@u_seem_surprsd what are we doing by this ??