Can anybody help me with this question - FLIPPING COINS

general
1

Hello everyone,I know that this is segment tree based question which can be done using lazy propagation.I have just started learning segment tree and I am facing lots of difficulties.I have seen some submissions but could not get anything.Can anybody help ?This is some XYZ’s submission.I have marked the lines which are making problems.I request you to please explain.If possible the hole thought process.If you are short of time atleast the commented one.Thank you all,Have a nice day

2

I’ll have a go at answering your questions.

Your first question is with the code below. The commented line isn’t needed and is incorrect. You only need to update the count if an odd number of flips have occurred. This is the reason for the second if statement.
The value lazy[idx] is the number of flips that have occurred since the last update for this range. So to update the number of heads you need to handle the whole range. The line seg[idx] = right - left + 1 - seg[idx] is just inverting the number of tails for heads.

if(lazy[idx]){
	//seg[idx] += lazy[idx];                      <--- why commented this line,When it is used ?
	if(lazy[idx]%2!=0){
		seg[idx] = right-left+1-seg[idx];
	}
	if(left!=right){
		lazy[idx*2] += lazy[idx];
		lazy[idx*2+1] += lazy[idx];
	}
	lazy[idx] = 0;
}

Your second question deals with this code

if(lazy[idx]%2!=0){
seg[idx] = right-left+1-seg[idx];          <----
}

I think I’ve already mostly answered this but I’ll try again just in case it wasn’t clear. Say you have a segment tree like this

     3
   /   \
  2     1
 / \   / \
1   1 0   1

If you do three flip on the whole range then the value for lazy1 = 3 (root node), left = 0, right = 3.
The new value for seg[idx] = ((3 - 0) + 1) - 3 = 1. This matches up with what you would expect.

Also here is a tutorial that might help
Tutorial

1 Like
3

Thank you :slight_smile: I am having so many doubts like this.Can you give me some advice how to master segment trees.I know it conceptually but I am facing difficulty in implementing it :frowning:

4

Try starting with an easy segment tree problem. This one just requires you to build the tree and do queries on it. It doesn’t require any updates and this means it doesn’t require lazy propagation either. Have a look at the editorial for it too.

There was also a problem in the August competition that used segment trees. The problem is quite a bit harder than the flipping coins one but the editorial also links to a few other segment tree problems and they all have editorials as well.

5

Also I found it really helpful to come up with a few small trees and manually do updates on it to understand what was supposed to happen. Then I wrote a small function that printed out the segment tree and lazy propagation values after each update/query so I could see if my code was matching up to my implementation. You can do the same by taking a working solution from the practice problem and see what their code prints out. Just try to find one a working solution that looks readable.

6

I’ve coded up this problem and tried to add some comments to make it a bit more obvious what is happening at each step.
https://www.codechef.com/viewsolution/7577028