I got it now. Thanks!
1 Like
Can we use sparse segment trees to solve this problem. I do know segment trees and got 20 points using it. I don’t know if sparse segment trees even exist 
It may exist with some other name if not the exact name If some one finds a link. Do share it
Simple and easy to understand very nice code well done!!!
@watcher, @taran_1407 With the same solution as that of testers and similiar code in python. My code didn’t pass for a subtask. Can you please tell me why?
Yes you are right complexity is O(Q*log(Q)*log(n)) but I think doing it with treap will also have same complexity.
1 Like
exactly !!! I don’t understand why editorialist’s solution passes the time limit. Our policy based data structure too does the required operations in the same log(n) time. Any hint @l_returns @taran_1407 @(anyone who would like to throw some light on this ) ??? here is what I tried
1 Like
PBDS is \log_2(n) but it’s constant might be higher than using treap and hence it doesn’t pass. Imagine tree taking 1.1 secs now even if PBDS takes twice time then also it will get TLE.
Otherwise your solution seems correct 
.
PS : his solution take 2.55 secs in Java. Which is equivalent to 1.275 in c++ approximately.
So you should avoid using PBDS unless necessary and if time limit is suitable.
1 Like
With path compression, it shall fail.
Suppose N = 3
Updates A[2] = 0
Update A[3] = 0
At this point, All three elements are member of same set due to path compression, right?
Then update A[2] = 2.
Query 1 3 should give 2, but gives 1 due to path compression being wrong.
Without path compression without ranks, it’ll get TLE.
With Ranks it may pass though very close to TL, or may get TLE.
Intended solution for bonus was Balanced BSTs.
2 Likes
My solution uses binary search which is O(log(N)) while pbds gives amortized O(log(N)) complexity due to inner structure, which i believe are making a difference here.
2 Likes
Okay thanks will think about it
Can Anyone figure out what’s wrong in my solution, just got 80/100 points 
!!!
Solution : CodeChef: Practical coding for everyone
How do you compare one algorithm’s constants ?? I mean I have never seen any post comparing two log(n) algorithms based on their constants as they are never taken into consideration while calculating the complexity and thus are lost. Moreover, How do you convert time in java code to that in cpp code ?? Is there any such tutorial ???
1 Like
Wow. … . … . . …
so how do you find if the given time coplexity for a algo is amortized or worst case ( as I never saw the time complexity of pbds mentioned as amortized log(n) )???
1 Like
If you want to solve it using segment tree, you can learn persistent segment tree to solve the problem.
2 Likes
Hey @anon10768935, this was my solution:
https://www.codechef.com/viewsolution/25018371
It’s kind of the same as yours. Can you please help me in identifying where I could have gone a little expensive with the time?
I have absolutely no idea how you passed the last three cases but failed the first two.
I have 2 versions : version 1 version 2, in 1, I got 80 points, I compressed the path while finding parent, in version 2, I got 30 points, I compressed the path while assigning the parent. and I witness huge time diffrence. Any reason why so ??
P.S. I don’t know why I am getting WA in first test case.
Nah. Since time multiplier of java is 2. I divided it by 2 !!
How can you not take constants into consideration.
If a log(n) algorithm takes 1 sec to run then obviously if an algorithm takes even twice time then also it won’t pass.
2nd one is not using path compression.
Path compression is you compress it every time you traverse it.
agreed. What I ment to say is how do you know that one algo’s constant is larger ??
Just by looking at the time taken by submitted solution ?? Or is it mentioned somewhere ??