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… 
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 : [email protected],
and i wiil show you how to code this.
@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:
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
6 Likes
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)
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.
11 Likes
this is nice So my “high-level” explanation is not very wrong 
@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
@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
Thanks a lot, this is slowly starting to make sense
Why do we need to keep track of how many flips were made?
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).
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).
@u_ seem_ surprised
Thanks to u_ seem_ surprised, I finally understand the concept.
we are subtracting because we want to get the total no. of elements in the range.
Hi,
I made a video editorial on segment trees and how they solve this question. You can have a look at it here:
Cheers!
3 Likes
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
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
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.
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
Can this be done using Binary Indexed tree?