BURARRAY - EDITORIAL

editorial
, , , , ,
69

Could you pleas explain your solution ?

70

This is brute Force. Tester uses path compression.

1 Like
71

Solved this in python3
https://www.codechef.com/viewsolution/25002631

Any help optimising it?

72

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

73

I meant further optimisation, if possible
Looking at your code for references
Thanks

74

I got it now. Thanks!

1 Like
75

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 :sweat_smile: It may exist with some other name if not the exact name :sweat_smile: If some one finds a link. Do share it

76

Simple and easy to understand very nice code well done!!!

77

@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?

CodeChef: Practical coding for everyone

78

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
79

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
80

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 :thinking:.
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
81

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
82

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
83

Okay thanks will think about it :thinking:

85

Can Anyone figure out what’s wrong in my solution, just got 80/100 points :neutral_face: !!!
Solution : CodeChef: Practical coding for everyone

86

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
87

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
88

If you want to solve it using segment tree, you can learn persistent segment tree to solve the problem.

Link

2 Likes
89

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?