Could you pleas explain your solution ?
This is brute Force. Tester uses path compression.
You can look at my solution -CodeChef: Practical coding for everyone
This is 0.29 seconds faster than yours.
Yours is already optimized time limit was 10 seconds for python and you got it in 4
I meant further optimisation, if possible
Looking at your code for references
Thanks
I got it now. Thanks!
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.
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
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.
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.
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.
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 ???
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) )???
If you want to solve it using segment tree, you can learn persistent segment tree to solve the problem.
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?