# BURARRAY - EDITORIAL **URL:** \ **Category:** editorial\ **Tags:** binary-search, editorial, taran\_1407, treap, union-find, ltime73\ **Created:** [June 29, 2019, 2:05am UTC](https://discuss.codechef.com/t/burarray-editorial/29301 "2019-06-29T02:05:59Z")\ **Posts on this page:** 20\ **Page:** 4
**Author:** ![avi141](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@avi141](https://discuss.codechef.com/u/avi141)\ **Post date:** [June 30, 2019, 7:45am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/69 "2019-06-30T07:45:50Z")
Could you pleas explain your solution ? ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 30, 2019, 8:09am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/70 "2019-06-30T08:09:13Z")
This is brute Force. Tester uses path compression. ---
**Author:** ![rahul\_bose](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rahul\_bose](https://discuss.codechef.com/u/rahul_bose)\ **Post date:** [June 30, 2019, 8:27am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/71 "2019-06-30T08:27:48Z")
Solved this in python3 [https://www.codechef.com/viewsolution/25002631](https://www.codechef.com/viewsolution/25002631) Any help optimising it? ---
**Author:** ![kshitij\_789](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kshitij_789/32/208155_2.png) [@kshitij\_789](https://discuss.codechef.com/u/kshitij_789)\ **Post date:** [June 30, 2019, 8:44am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/72 "2019-06-30T08:44:06Z")
You can look at my solution -[CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24988479) 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 ---
**Author:** ![rahul\_bose](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@rahul\_bose](https://discuss.codechef.com/u/rahul_bose)\ **Post date:** [June 30, 2019, 8:45am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/73 "2019-06-30T08:45:35Z")
I meant further optimisation, if possible Looking at your code for references Thanks ---
**Author:** ![sam\_b](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sam_b/32/3653_2.png) [@sam\_b](https://discuss.codechef.com/u/sam_b)\ **Post date:** [June 30, 2019, 9:04am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/74 "2019-06-30T09:04:20Z")
I got it now. Thanks! ---
**Author:** ![ojhasaurabh209](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ojhasaurabh209](https://discuss.codechef.com/u/ojhasaurabh209)\ **Post date:** [June 30, 2019, 9:05am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/75 "2019-06-30T09:05:54Z")
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 ---
**Author:** ![adarshverma013](https://discuss.codechef.com/user_avatar/discuss.codechef.com/adarshverma013/32/9118_2.png) [@adarshverma013](https://discuss.codechef.com/u/adarshverma013)\ **Post date:** [June 30, 2019, 11:17am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/76 "2019-06-30T11:17:39Z")
Simple and easy to understand very nice code well done!!! ---
**Author:** ![muditrustagii](https://discuss.codechef.com/user_avatar/discuss.codechef.com/muditrustagii/32/3653_2.png) [@muditrustagii](https://discuss.codechef.com/u/muditrustagii)\ **Post date:** [June 30, 2019, 1:09pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/77 "2019-06-30T13:09:58Z")
@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](https://www.codechef.com/viewsolution/25012213) ---
**Author:** ![monster\_1097](https://discuss.codechef.com/user_avatar/discuss.codechef.com/monster_1097/32/2045_2.png) [@monster\_1097](https://discuss.codechef.com/u/monster_1097)\ **Post date:** [June 30, 2019, 6:18pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/78 "2019-06-30T18:18:35Z")
Yes you are right complexity is O(Q\*log(Q)\*log(n)) but I think doing it with treap will also have same complexity. ---
**Author:** ![harshraj22](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshraj22/32/25247_2.png) [@harshraj22](https://discuss.codechef.com/u/harshraj22)\ **Post date:** [June 30, 2019, 7:37pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/79 "2019-06-30T19:37:19Z")
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](https://www.codechef.com/viewsolution/25015414) ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [June 30, 2019, 9:23pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/80 "2019-06-30T21:23:06Z")
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. ---
**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\ **Post date:** [July 1, 2019, 12:15am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/81 "2019-07-01T00:15:47Z")
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. ---
**Author:** ![taran\_1407](https://discuss.codechef.com/user_avatar/discuss.codechef.com/taran_1407/32/299985_2.png) [@taran\_1407](https://discuss.codechef.com/u/taran_1407)\ **Post date:** [July 1, 2019, 12:18am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/82 "2019-07-01T00:18:44Z")
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. ---
**Author:** ![l\_returns](https://discuss.codechef.com/user_avatar/discuss.codechef.com/l_returns/32/233293_2.png) [@l\_returns](https://discuss.codechef.com/u/l_returns)\ **Post date:** [July 1, 2019, 2:51am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/83 "2019-07-01T02:51:16Z")
Okay thanks will think about it 🤔 ---
**Author:** ![call\_me\_hypa](https://discuss.codechef.com/user_avatar/discuss.codechef.com/call_me_hypa/32/11843_2.png) [@call\_me\_hypa](https://discuss.codechef.com/u/call_me_hypa)\ **Post date:** [July 1, 2019, 4:25am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/85 "2019-07-01T04:25:22Z")
Can Anyone figure out what’s wrong in my solution, just got 80/100 points 😐 !!! Solution : [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/25016569) ---
**Author:** ![harshraj22](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshraj22/32/25247_2.png) [@harshraj22](https://discuss.codechef.com/u/harshraj22)\ **Post date:** [July 1, 2019, 7:02am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/86 "2019-07-01T07:02:47Z")
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 ??? ---
**Author:** ![harshraj22](https://discuss.codechef.com/user_avatar/discuss.codechef.com/harshraj22/32/25247_2.png) [@harshraj22](https://discuss.codechef.com/u/harshraj22)\ **Post date:** [July 1, 2019, 7:06am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/87 "2019-07-01T07:06:34Z")
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) )??? ---
**Author:** ![blake\_786](https://discuss.codechef.com/user_avatar/discuss.codechef.com/blake_786/32/208155_2.png) [@blake\_786](https://discuss.codechef.com/u/blake_786)\ **Post date:** [July 1, 2019, 8:24am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/88 "2019-07-01T08:24:50Z")
If you want to solve it using segment tree, you can learn persistent segment tree to solve the problem. [Link](https://www.codechef.com/viewsolution/25018390) ---
**Author:** ![shardic](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shardic/32/4034_2.png) [@shardic](https://discuss.codechef.com/u/shardic)\ **Post date:** [July 1, 2019, 8:46am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/89 "2019-07-01T08:46:51Z")
Hey @anon10768935, this was my solution: [https://www.codechef.com/viewsolution/25018371](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? [Previous page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=3) [Next page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=5)