# 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:** 5
**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:51am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/90 "2019-07-01T08:51:29Z")
I have absolutely no idea how you passed the last three cases but failed the first two. ---
**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, 9:00am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/91 "2019-07-01T09:00:02Z")
I have 2 versions : [version 1](https://www.codechef.com/viewsolution/25018565) [version 2](https://www.codechef.com/viewsolution/25018442), 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. ---
**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, 9:29am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/92 "2019-07-01T09:29:27Z")
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. ---
**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, 9:31am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/93 "2019-07-01T09:31:07Z")
2nd one is not using path compression. Path compression is you compress it every time you traverse it. ---
**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, 9:31am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/94 "2019-07-01T09:31:49Z")
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 ?? ---
**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, 9:34am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/95 "2019-07-01T09:34:48Z")
> PS: I believe what @taran_1407 said And I have experience of PBDS taking more time compared to few other algos or DS ---
**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, 9:35am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/96 "2019-07-01T09:35:32Z")
shouldn’t the second one be considered better than first ? as In first, you are allowing the chain to grow large ( compressing only when one need to find node’s parent ) while in the second, right from the start, I ain’t allowint the chain to grow and always accumulating it to one parent. ?? ---
**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, 9:36am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/97 "2019-07-01T09:36:27Z")
Height should be minimized in order to reduce time complexity. 1st one is doing that. ---
**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, 9:38am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/98 "2019-07-01T09:38:34Z")
If I keep on adding elements n-1 time, length grows to n, and then query once, leading to O(n) I guess ?? whereas in second, the height doesn’t grow to n ?? Any wrong logic 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, 9:41am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/99 "2019-07-01T09:41:40Z")
Height can’t grow to n. As while merging it you will find root and while finding root you should compress. ---
**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, 9:43am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/100 "2019-07-01T09:43:28Z")
agreed ! But have a look at the version 1 again, While merging, I ain’t finding the root. ---
**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, 9:44am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/101 "2019-07-01T09:44:46Z")
I doubt if that’s DSU 🤔. In DSU I learnt we merge two connected components. You are making a graph with given edges instead. ---
**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, 9:46am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/102 "2019-07-01T09:46:47Z")
yeah, that’s what I am confused about . While adding nodes, in first version I am doing the same and making the height really large, still it gives better time complexity than the second version ( which I claim should be more time efficient as the depth isn’t allowed to grow ) … … . . . . Do you agree results are weired ?? ---
**Author:** ![shivam\_g1470](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivam_g1470/32/14942_2.png) [@shivam\_g1470](https://discuss.codechef.com/u/shivam_g1470)\ **Post date:** [July 1, 2019, 10:53am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/103 "2019-07-01T10:53:25Z")
ooh. I misread Bonus problem as Update Ap to some X(not P)😅. So, In original bonus problem we would just remove the element P from DS if present and proceed normally 🙂 . Could you think of any algorithm if query was Update Ap to X?🤔 ---
**Author:** ![anon55659401](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon55659401](https://discuss.codechef.com/u/anon55659401)\ **Post date:** [July 1, 2019, 10:56am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/104 "2019-07-01T10:56:47Z")
Send me some nice persistent tutorials…please sir \_/\_ (akele akele maje mat karo aap) ---
**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, 11:06am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/105 "2019-07-01T11:06:11Z")
Lol . . . . . 😂😂🤣🤣 This should be my comment in reply to yours one… . . . . . . ---
**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, 12:09pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/106 "2019-07-01T12:09:06Z")
Hey, you are not clearing the data stored at each node in each test case. still why isn’t that affecting the solution for more than one test cases ? for example, [here](https://drive.google.com/open?id=1-nCTSlEhaUAb3pYplZwVJmcKiKyvU_AN), shouldn’t the `cont` at node=2 be affected as there is something left from the previous test case which should have been cleared ? TC2 represents the expected test case2 but actually the tree would look diffrent. Is there something that I am missing ? ---
**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, 12:42pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/107 "2019-07-01T12:42:49Z")
I am clearing the data, the last loop which is iterating from 1 to ctr is making everything 0. ---
**Author:** ![anon10768935](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon10768935](https://discuss.codechef.com/u/anon10768935)\ **Post date:** [July 1, 2019, 2:05pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/108 "2019-07-01T14:05:01Z")
The problem is you used unordered sets which in STL implementation of min heap and I used Unordered map which in STL uses Red black trees which reduce Time Complexity by huge amount. Though you did great buddy. ---
**Author:** ![gpatel3](https://discuss.codechef.com/user_avatar/discuss.codechef.com/gpatel3/32/208155_2.png) [@gpatel3](https://discuss.codechef.com/u/gpatel3)\ **Post date:** [July 1, 2019, 3:20pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/109 "2019-07-01T15:20:36Z")
Suppose if the queries were like below (let us assume queries are not online they are just simple queries i.e. x , l and r are directly given for respective type queries) : 1 1000000000000000000 500000 1 1000000000000000000 2 1 1000000000000000000 1 999999999999999999 2 1 1000000000000000000 1 999999999999999998 2 1 1000000000000000000 1 999999999999999997 2 1 1000000000000000000 … ans so on Then, will this algo work [Previous page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=4) [Next page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=6)