BURARRAY - EDITORIAL

editorial
, , , , ,
102

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

103

ooh. I misread Bonus problem as Update Ap to some X(not P):sweat_smile:. So, In original bonus problem we would just remove the element P from DS if present and proceed normally :slightly_smiling_face: . Could you think of any algorithm if query was Update Ap to X?:thinking:

104

Send me some nice persistent tutorials…please sir _/_ (akele akele maje mat karo aap)

1 Like
105

Lol . . . . . :joy::joy::rofl::rofl:
This should be my comment in reply to yours one… . . . . . .

1 Like
106

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

107

I am clearing the data, the last loop which is iterating from 1 to ctr is making everything 0.

1 Like
108

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.

109

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

110

Thanks a lot for this wonderful answer using persistent segment tree. Can you share some more of your answers using same ??

1 Like
111

But I changed the DS too to use Maps instead of a Set, still TLE.
https://www.codechef.com/viewsolution/25021777

112

I switched to this array implementation recently, however you can have a look at this persistent trie. GPD - persistentTrie

113

Thank a lot for this ( though it will take some time to understand it).I tried to code up the persistent segment tree on my own way but got up getting WA. To make it easier to understand, I changed your code a little bit to work similarly as mine, but I don’t understand why it gives WA.

114

Best solution of tester, small ,neat and easy to understand.

1 Like
115

Consider the example where n is equal to 6, you have already inserted 4,5 in tree and your search query is [1 5]. Do a dry run for this example on your code and as well as on mine. You will get the error.

116

I did the same with map but it gave tle. When I switched it to unordered_map it gave AC.
Tle solution: CodeChef: Practical coding for everyone
Withour TLE solution: CodeChef: Practical coding for everyone

1 Like
117

I just checked your code, You didn’t used path compression technique well,that’s why your solution didn’t pass. And for unordered_map it did slight speed due to it’s average time complexity is less than map,But I think it passeed due to test cases are not that strong.

1 Like
118

Soppose this case: let array after some updates be like 1 1 0 0 0 0 .
here if query is for [1,6]
a2=1;a3=6;
Then solution works as following:
check mp.find(6)->true
mp.find(mp[6])->true
assign mp[6]=mp[mp[6]] -->>mp[6]=4;
a3=4;
mp.find(4)->true
mp.find(mp[4])->true
assign mp[4]=mp[mp[4]] -->>mp[4]=2;
a3=2;

So, if you carefully observe, mp[4] becomes 2, but mp[6],mp[5] remains equal to 4.
So if there is again this query [1,6]
you will again do the same process, because mp[6] shoud return 2;
But if you used path compression, then mp[6] will directly return 2.
Hope you understand my this long explanation.

1 Like
119

I see no difference between updated code and your original code tried on the given test cases.
Even the tree created is same. The only difference is that you are allowing the ‘r’ to be outside the range of node ( the leaves that the current node covers ) while I am always making sure to include it. But at the return statement, you are taking min( ) making the output same ?

120

I think there might be a problem in your find_set function

Look at my python solution for reference:-
https://www.codechef.com/viewsolution/25025506

121

updated code
see the change i made in line 95, because it’s possible that r <= mid, in that case the end should be r not mid.

1 Like