You are not logged in. Please login at www.codechef.com to post your questions!

×

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

0
3

I know it can be solved using Binary Indexed Trees. I read them, but still haven't been able to find a solution. Can someone explains me the algo, please.... :)

asked 01 Sep '14, 22:32

out_of_the_box's gravatar image

3★out_of_the_box
1111
accept rate: 0%

edited 02 Sep '14, 20:22

kuruma's gravatar image

3★kuruma
17.7k72143209


13

So let's start by creating 2 arrays that store the segment tree and the flag value for lazy update ST[size], lazy[size], the size here can be calculated by a certain formula for the no of nodes that our segment tree will contain, which you can look up, by a general idea you can take size = 3*10^6 for N = 10^6. Note that the coins are numbered from 0 to N-1.

The children of the current node in the segment tree are (2*currentNode), (2*currentNode+1).

Initially those arrays will contain 0(all coins are kept tails up). Before understanding the update function, I am going to talk about the query function, lets assume that we have updated certain no of queries in our segment tree, then our query function is going to look something like this :

Note : that this does not contain the lazy part.

//normal query int query(int node, int start, int end, int L, int R){ if(L > end || R < start) return 0; if(start >= L && end <= R) return ST[node]; int x = query(node<<1, start, (start+end)>>1, L, R); int y = query((node<<1)+1, ((start+end)>>1)+1, end, L, R); return x+y; }

node : it is the current node in the segment tree

start : it is the starting index of our the coins we consider in the current node.

end : it is the ending index of our the coins we consider in the current node.

eg : if node = 1(i.e the initial node in the segment tree), then start = 0, end = N-1.

L, R : they are the indices of the query that we need to perform.

As it is clear from the function we check the start and the end index if they are within the query that we need we return the current node, else we recurse furthur to the two children of the current node and return their sum.

Now lets move on to the lazy update part :

//query with lazy propogation int queryLazy(int node, int start, int end, int L, int R){ if(L > end || R < start) return 0; if(lazy[node] == 1){ //i.e update curr node if lazy has been set previously ST[node] = (end-start+1) - ST[node]; //updating seg tree node if(start != end){ //i.e if not a leaf then mark children lazy[node<<1] = 1-lazy[node<<1]; lazy[(node<<1)+1] = 1-lazy[(node<<1)+1]; } lazy[node] = 0; } if(start >= L && end <= R) return ST[node]; int x = queryLazy(node<<1, start, (start+end)>>1, L, R); int y = queryLazy((node<<1)+1, ((start+end)>>1)+1, end, L, R); return x+y; }

So now while going down the segment tree if we find that a certain node has been set to 1, i.e we need to update it. Updating can depend on the question here update is easy we need to flip all the coins in the current range , i.e no of new heads = total coins in curr node - no of old heads. No we flip the flag value of the children of our current node.

Note : The query part still takes the same time as the normal query would, we just check for lazy flag and accordingly manipulate our answers at the current node if needed.

Now lets move to the update function.

//normal update void update(int node, int start, int end, int L, int R){ if(L > end || R < start) return; if(start >= L && end <= R) ST[node] = (end-start+1) - ST[node]; update(node<<1, start, (start+end)>>1, L, R); update((node<<1)+1, ((start+end)>>1)+1, end, L, R); ST[node] = ST[node<<1] + ST[(node<<1)+1]; }

The update function is pretty much like the query function we go down the segment tree update the no of tails in the current node(if within range) and go down until we reach the leaves of the tree. Now notice for a segment (L, R) to update we need to update (L, R) and all its corresponding children and their children and so on.... That is a lot of work going down upto the leaves of the segment tree and updating them, so the idea of lazy update is update the node when we need to and leave all its children the way they are, so for that we just need to have a flag value that remembers that we need to perform update on a certain node, we don't actually update the node untill we need to.

So the update function with lazy propogation would look like :

void updateLazy(int node, int start, int end, int L, int R){ if(lazy[node] == 1){ //i.e update curr node if lazy has been set previously ST[node] = (end-start+1) - ST[node]; if(start != end){ //i.e if not a leaf then mark children lazy[node<<1] = 1-lazy[node<<1]; lazy[(node<<1)+1] = 1-lazy[(node<<1)+1]; } lazy[node] = 0; } if(L > end || R < start) return; if(start >= L && end <= R){ //segment inside range hence update ST[node] = (end-start+1) - ST[node]; if(start != end){ //i.e if no leaf then mark children lazy[node<<1] = 1-lazy[node<<1]; lazy[(node<<1)+1] = 1-lazy[(node<<1)+1]; } return; //we donot go down the tree and update every node } update(node<<1, start, (start+end)>>1, L, R); update((node<<1)+1, ((start+end)>>1)+1, end, L, R); ST[node] = ST[node<<1] + ST[(node<<1)+1]; }

Here the first if condition checks if the lazy node had been set previously or not. Then the 3rd if condition is where we check if we have found the segment in the range, and update this segment and instead of recursing down the tree all the way to the leaves we just flip the flag values of the children so if we were ever to query the children we could update them first and then return the answer.

Note : we only need the queryLazy, updateLazy functions to solve the question the normal query and update were just to make the understanding simple. Also that the update part depends on the question and often can be quite complex.

link

answered 02 Sep '14, 23:55

u_seem_surprsd's gravatar image

5★u_seem_surprsd
527147
accept rate: 25%

edited 03 Sep '14, 00:11

this is nice :) So my "high-level" explanation is not very wrong :D

(03 Sep '14, 00:38) kuruma3★

@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

(03 Sep '14, 17:02) kuruma3★

@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 : http://www.codechef.com/viewsolution/3968902

(04 Sep '14, 00:03) u_seem_surprsd5★

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

(04 Sep '14, 03:11) kuruma3★

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

(25 Dec '15, 01:20) shubham992★

@stasszczesniak why don't you try to explain it trough here so everyone can learn a few new things?

I have a very hard time and difficulty with coding Segment Trees myself, but, to solve this problem, you basically need two things:

  • Understand that you need to update a range of elements and not simply a single element;
  • Understand what needs to be done in the query function;

Like I said, I have read many, many things on segment trees but, never really could implement them properly on my own, so this will be a somewhat theoretical explanation... If something is wrong, please try to correct it.

First of all, it matters to say that segment trees are nice fucking awesome because they allow you to answer range queries, like how many coins between A and B are heads up in logarithmic time instead of linear time in the size of the interval (B-A+1 for this purpose).

For the sake of an example, let's consider just a static array where single updates are performed. How would we go about solving this problem in the first place?

It's not so hard if we are aware of the basic strcture of a segment tree and if we can map this into something we are familiar with.

Let's consider now the static array with the following coins, where H means heads and T means tails.

[H, T, H, H, T, T, T]

(note: this is actually one of the things I can't seem to know how to fix, but, when the original array you have has a size which is not power of 2, I don't really know how to build up all the nodes.)

If we want to count how many coins in a range are Heads up, we can map this into a well known problem for segment trees:

If Heads = integer number 1 and Tails = integer number 0 then the answer we are looking for is simply the sum of all numbers in range (A,B), right?

Then when building the "internal" nodes of the segment tree, this is the info we will store on the nodes: the sum of its descendents.

We now have:

[1, 0, 1, 1, 0, 0, 0]

To build the tree, we group the nodes in pairs, recursively storing the desired information on the new nodes:

          [3]

     [3,         0]

  [1,   2,    0,   0]

[1, 0, 1, 1, 0, 0, 0]

At each level we have the sum of the 2 elements which are below it, with the last 0 being "carried up" since the size is not a power of 2. Not sure if this is correct.

Let's assume our original array is indexed from 0 to 6.

We now have query(2,6).

Answer is 2.

Instead of going trough the 5 values on the original array, we can go up in the tree.

Why is this better?

Well since a binary tree built over N nodes has height of at most log2(N) then it takes us time at most log2(6-2+1) to answer our original query. A lot better than 6-2+1 dont you think?

How the "go up in the tree" is done in practice still confuses me a bit, to be honest, but, at least this makes sense to me so maybe it makes sense to you too.

Now, as you see, if we change a single value, we can simply change it on the original array and then update only the internal nodes on which this update is going to reflect, taking us log2(N) time to "reset" the tree for a single update.

EXAMPLE: we flip coin 5, so now original array is:

[1, 0, 1, 1, 0, 1, 0]

After the update of the internal nodes we have now (notice that the updated nodes are in bold):

             [**4**]

         [3,         **1**]

      [1,   2,    **1**,   0]

    [1, 0, 1, 1, 0, **1**, 0]

On this problem, we have a range which can be updated instead of a single element.

Based on the above drawing you can see now that when updating a range the main problem we face is that on the higher levels of the tree, an internal node can be updated several times.

As such instead of performing multiple updates to a single internal node (like you know, doing several single updates multiple times which would take linear time on the number of updates) we can mark some of the nodes as lazy. We do this presumably from all I've seen, by adding a flag on each node which marks the number of times it will be updated and then according to the values of these flags we go up in the tree one more time and update all the nodes taking still logarithmic time to update a range (maybe this is total bullshit idk really).

How to implement this....No idea....What can I say I'm a theory kind of guy xD

I've been lately reading and re-reading this over and over: http://discuss.codechef.com/questions/49339/equake-editorial

but, I still haven't managed to code anything on my own...

Hope this can help you or at least motivate someone more skilled to add some insights to this...

Best,

Bruno

link

answered 02 Sep '14, 20:20

kuruma's gravatar image

3★kuruma
17.7k72143209
accept rate: 8%

edited 02 Sep '14, 20:27

Hi,
I made a video editorial on segment trees and how they solve this question. You can have a look at it here:
https://youtu.be/CN0N1ddJ9hA

Cheers!

link

answered 23 Mar '17, 16:39

gkcs's gravatar image

4★gkcs
2.6k11127
accept rate: 9%

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

link

answered 27 Mar '17, 17:06

vipul2706's gravatar image

2★vipul2706
111
accept rate: 0%

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

link

answered 14 Dec '17, 21:50

ruddradev's gravatar image

3★ruddradev
1245
accept rate: 7%

I have solved it.

(18 Jun '18, 02:38) ruddradev3★

Ok.
This can be solved using segment trees. In each node you keep :
- how many coins in subtree are heads up
- how many flips were made
If you don't know how to code it yet,
please ask again here : stas.szczesniak@gmail.com,
and i wiil show you how to code this.

link

answered 01 Sep '14, 23:52

stasszczesniak's gravatar image

2★stasszczesniak
26216
accept rate: 9%

edited 02 Sep '14, 18:42

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

(29 Sep '15, 16:15) dragonemperor3★

Hi.
This is my code to FLIPCOIN.
http://pastebin.com/4gsLkjff
I think it might help, because i commented it.
UPD1: M is segment tree size.
UPD2: It reminded me the very simmilar task :
2 types of queries :
-> flip(a,b)
-> count_inversions(a,b)

link

answered 02 Sep '14, 23:12

stasszczesniak's gravatar image

2★stasszczesniak
26216
accept rate: 9%

edited 02 Sep '14, 23:41

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

link

answered 25 Dec '15, 01:26

shubham99's gravatar image

2★shubham99
2403932
accept rate: 5%

@u_ seem_ surprised Thanks to u_ seem_ surprised, I finally understand the concept.

link

answered 03 Dec '16, 20:36

waterbyte's gravatar image

1★waterbyte
11
accept rate: 0%

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

link

answered 23 Mar '17, 13:38

ajay_5097's gravatar image

3★ajay_5097
1
accept rate: 0%

edited 23 Mar '17, 17:26

@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

link

answered 04 Apr '17, 08:47

abhishel's gravatar image

2★abhishel
383
accept rate: 10%

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.

link

answered 29 Sep '17, 15:08

devpahuja's gravatar image

3★devpahuja
11
accept rate: 0%

edited 29 Sep '17, 15:11

Can this be done using Binary Indexed tree?

link

answered 24 Dec '17, 10:32

anubhaw_iiitu's gravatar image

4★anubhaw_iiitu
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×30

question asked: 01 Sep '14, 22:32

question was seen: 9,628 times

last updated: 18 Jun '18, 02:38