# BURARRAY - EDITORIAL

**URL:** <https://discuss.codechef.com/t/burarray-editorial/29301>\
**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:** 3

<div class="post-metadata">

**Author:** ![an09mous](https://discuss.codechef.com/user_avatar/discuss.codechef.com/an09mous/32/47737_2.png) [@an09mous](https://discuss.codechef.com/u/an09mous)\
**Post date:** [June 29, 2019, 6:43pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/45 "2019-06-29T18:43:16Z")

</div>

Basically you implemented DSU using maps

---

<div class="post-metadata">

**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 29, 2019, 6:48pm UTC](https://discuss.codechef.com/t/burarray-editorial/29301/47 "2019-06-29T18:48:38Z")

</div>

I used pbds(ordered set) instead of treap but got TLE in all except first subtask although its time complexity is O(Q∗log(N)) per test case 😐  
Can someone explain what mistake I am doing [Code](https://www.codechef.com/viewsolution/24989607)

---

<div class="post-metadata">

**Author:** ![shivamchef](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivamchef/32/5634_2.png) [@shivamchef](https://discuss.codechef.com/u/shivamchef)\
**Post date:** [June 30, 2019, 4:02am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/50 "2019-06-30T04:02:48Z")

</div>

i also tried same approach but complexity of this algo this O(Q\*log(q)\*log(q)) which is around 4 \* 10^9 which is resulting in TLE.

---

<div class="post-metadata">

**Author:** ![shivamchef](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivamchef/32/5634_2.png) [@shivamchef](https://discuss.codechef.com/u/shivamchef)\
**Post date:** [June 30, 2019, 4:04am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/51 "2019-06-30T04:04:42Z")

</div>

what is O(log\*(n)) ? what is \* ?

---

<div class="post-metadata">

**Author:** ![saurabhshadow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhshadow/32/347886_2.png) [@saurabhshadow](https://discuss.codechef.com/u/saurabhshadow)\
**Post date:** [June 30, 2019, 4:08am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/52 "2019-06-30T04:08:13Z")

</div>

I thought segment tree will be used and my mind was moving around segment tree only. I just managed to get 20 points, but now when i see the editorial, i am like…😑

---

<div class="post-metadata">

**Author:** ![gkothyari](https://discuss.codechef.com/user_avatar/discuss.codechef.com/gkothyari/32/4048_2.png) [@gkothyari](https://discuss.codechef.com/u/gkothyari)\
**Post date:** [June 30, 2019, 5:25am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/53 "2019-06-30T05:25:41Z")

</div>

A very nice solution indeed!

---

<div class="post-metadata">

**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, 5:45am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/54 "2019-06-30T05:45:30Z")

</div>

\log\_2(2\*10^5)=19 whereas log^\*\_2(2\*10^5)=4  
Google it.

---

<div class="post-metadata">

**Author:** ![shivamchef](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivamchef/32/5634_2.png) [@shivamchef](https://discuss.codechef.com/u/shivamchef)\
**Post date:** [June 30, 2019, 5:48am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/55 "2019-06-30T05:48:22Z")

</div>

atleast give me a key word to search 😂

---

<div class="post-metadata">

**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, 5:54am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/56 "2019-06-30T05:54:29Z")

</div>

Already gave. Search log^\*(n)

---

<div class="post-metadata">

**Author:** ![kukreja\_vlk](https://discuss.codechef.com/user_avatar/discuss.codechef.com/kukreja_vlk/32/125882_2.png) [@kukreja\_vlk](https://discuss.codechef.com/u/kukreja_vlk)\
**Post date:** [June 30, 2019, 5:56am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/57 "2019-06-30T05:56:55Z")

</div>

The input size is huge, 10^{18}. Lazy propogation won’t make a difference. Dsu with path compression using maps will work fine as mentioned by editorialist.

---

<div class="post-metadata">

**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, 6:03am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/58 "2019-06-30T06:03:28Z")

</div>

yes…(20 char limit)

---

<div class="post-metadata">

**Author:** ![shivamchef](https://discuss.codechef.com/user_avatar/discuss.codechef.com/shivamchef/32/5634_2.png) [@shivamchef](https://discuss.codechef.com/u/shivamchef)\
**Post date:** [June 30, 2019, 6:06am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/59 "2019-06-30T06:06:18Z")

</div>

Thnks! got it now…

---

<div class="post-metadata">

**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, 6:08am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/60 "2019-06-30T06:08:44Z")

</div>

Is the bonus problem also for people who are using path compression??

---

<div class="post-metadata">

**Author:** ![jayeshkarvir5](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@jayeshkarvir5](https://discuss.codechef.com/u/jayeshkarvir5)\
**Post date:** [June 30, 2019, 6:09am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/61 "2019-06-30T06:09:50Z")

</div>

Is it possible to solve this problem using Square Root decomposition?  
By storing all the updated elements in an array of vectors and querying only those buckets which lie in the range l to r.

---

<div class="post-metadata">

**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, 6:11am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/63 "2019-06-30T06:11:08Z")

</div>

Works for all cases.  
Using path compression/using union by rank/using both.  
Easy modification.

---

<div class="post-metadata">

**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, 6:36am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/64 "2019-06-30T06:36:56Z")

</div>

yep  
solution:- add a query of type 3 with 3 followed by the index of the element.

```
If the element is not zero before the update:
     Do nothing.
Else:
      set par[par[node]]=node and del par[node]:
 
This modification is for the code which is using path compression
```

---

<div class="post-metadata">

**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, 6:39am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/65 "2019-06-30T06:39:27Z")

</div>

wrong using only path compression complexity is q\*α(q).  
α is the inverse of the ackermann function and in CP terms α of a number is not more than 4.So linear complexity.

---

<div class="post-metadata">

**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, 6:53am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/66 "2019-06-30T06:53:09Z")

</div>

Okay. Cool. \hspace{1mm}  
My solution with and without path compression takes equal time.  
Does that mean union by rank is also O(4) ? 😅

---

<div class="post-metadata">

**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, 6:55am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/67 "2019-06-30T06:55:43Z")

</div>

I am not sure about union by rank

---

<div class="post-metadata">

**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, 7:31am UTC](https://discuss.codechef.com/t/burarray-editorial/29301/68 "2019-06-30T07:31:48Z")

</div>

I have used a similar approach as the tester, but I am getting TLE on the last subtask. Link to my solution : [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/24993267)

[Previous page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=2)

[Next page](https://discuss.codechef.com/t/burarray-editorial/29301.md?page=4)