Can someone help me with this [question][1] of segment tree on hackerearth.
My
[2] is failing for 5 test cases. Please help me.
I even saw the editorial but cannot figure out what is the difference between their approach and mine.
Thanks in advance:)
[1]: https://www.hackerearth.com/practice/data-structures/advanced-data-structures/segment-trees/practice-problems/algorithm/shivam-and-expensive-birthday-gift-da58b2f0/description/
[2]: https://drive.google.com/open?id=12cUOJDgQYTHe-JWBPWClADndu1_3tPvX
its probably due to overflow,eg consider 100 queries of 1st type on element i,
so u can keep a stack at the leaf nodes,for 1st type of query push 1,increment the value of leaf by 1,for 2nd query ,pop if the popped value is 1,then decrement the value of leaf by 1
1 Like
Thank you. I understood the problem due to overflow but can you explain how to resolve it using stack Iām new to segment trees:(
Also can you please suggest me some problems(simple) to gain confidence in segment trees:)
It is an overflow issue, despite the promise in the problem statement that all array elements will fit into a 64 bit integer. Take for instance test #2. It starts with 90 multiplication operations (op 1) on A[50]. This will yield a value of 1237940039285380274899124223 which is well over 64 bits.
There is an elegant way to solve the problem using a segment tree without running into the overflow problem. Here is a hint: think about what the two operations do to a number with regard to the bits.
2 Likes
Thanks for the hint.
But can you explain when we have a query of type 2 a[i]=a[i]/2 why we are doing tree[node]-- if a[i]!=0;
ex a[i]=2(0010) after query a[i]=1(0001) why are we then reducing the count of 1 int tree node then? count of one must remain same:(
Who said we reduce the count?
U should reduce the count only if the last bit was 1,in ur case its 0,so better dont reduce the count.
So if a[i] was 2 dont reduce,if 3 reduce
But in the editorial of the problem they do not check this condition?
You will never have A[i] = 2. Unless A[i] = 0 the first bit will always be set. Operation 1 is multiply by two and then add one. This is equivalent to a bitwise shifting left and then turning the first bit on. You start with 0, so the successive operations give you 1, 3, 7, 15, ā¦ The first bit is always set. So, operation one always adds one bit.
Operation 2 is dividing by two. This is equivalent to a right shift, dropping the first bit. Unless A[i] = 0, this subtracts one bit.
1 Like
@jramaswami,thanks foR correcting,i didnt knew that elements are initialised to 0
Gotcha.
Can you tell me some problems(not too hard) on segment trees.
I am new to segment trees and just know basic like range minimum queries etc.
I think u should try the GSS series on spoj(GSS1,GSS2ā¦)
