BACREP - Algorithm behind?

29

It passed only in 0.47 Sec :frowning:
Can someone explain it.

1 Like
30

what is PBDS ?

31

I think that’s why he is 7 star.

32

@webhead PBDS is data structure supported by g++ compiler. Cpp Coders are Blessed!!

Blog covering pbds by Adamant.

Part1 → https://codeforces.com/blog/entry/11080
Part2 → http://codeforces.com/blog/entry/13279

@ssjgz Thanks for the commented solution!! em 5 star looks great :wink:

3 Likes
33

policy based data structure

34

ohhhhh man :smiley::smile:

35

I thought it was feature only for gcc compiler !!!
Are you sure it is built in STL ???

2 Likes
36

@harshraj22 Thanks for pointing out. Didn’t know it wasn’t part of STL. Edited my post!!

2 Likes
37

Too good! And congrats for the Five Stars. Any tips on how can I reach the same(2000+) rating?

1 Like
38

Thanks :slight_smile: These are the only tips I can give, I’m afraid :confused:

1 Like
39

thanks bro for those two links :smile: @idgaf_99

40

Can someone please find a testcase where this solution fails. I even locally generated testcases and compared with a brute approach and both are giving the same results. Help would be much appreciated.

Solution : CodeChef: Practical coding for everyone

41

This causes a segfault with your solution on my machine:

1 2
44 
+ 1 250
? 1

Edit:

After you fix that (your isLeaf logic is a little odd :)), try:

3 6
2 1
3 1
371 629 595 
? 3
? 2
? 3
+ 3 731
+ 2 578
? 2
1 Like
42

I modified the segfault when N = 1 case.
However, I checked the second test case you gave but the answer produced by my code is the same answer that is produced by your code.
Also, is there another better logic for finding whether a node is a leaf. The logic I’ve used now is that the degree of a leaf node is 1 and the node is not the root.
Once again, thank you so much for taking the time to go through my code

2 Likes
43

Ok - I did a quick hack-fix to fix the segfault, and probably introduced a new problem which your fix didn’t :slight_smile:

I just used fixParentAndChild and then the logic is the more straightforward isLeaf = node->children.empty();.

1 Like
44

@ssjgz I have just one query regarding your code, what are int minTDD and int maxTDD supposed to be doing in your code? I get the algorithm behind the question, it all boils down to updates and queries based on Time Depth Difference(TDD), which we perform using a Segment Tree. I just have problem realizing how we will manage the size of this Seg Tree, given that TDD can also be negative.
I see that you initialized int minTDDandint maxTDDto-query.size()and+query.size()respectively and then used twice of their difference, i.e.2 * (maxTDD - minTDD + 1)as size of Seg Tree. If I am not wrong, Seg Tree takes4 * size_of_array` as space. Can you please help me understand this part?

2 Likes
45

I can’t remember where I got the original Segment Tree from, but this looks like a likely candidate, and says:

Here, n is the range of values that can be used as “indices”/ “positions”/ “tdd-values” i.e. maxTDD - minTDD + 1.

Does that answer your question?

Edit:

Oh, and the initialisation with -query.size() and +query.size() turned out to be a mistake on my part (which wasn’t detected by 10000 random tests XD) - the current version has:

SegmentTree ancestorAddEventTDDs(-queries.size(),  // Minimum timeDepthDiff occurs when depth is 0 and we are dealing with the final query.
                                 +nodes.size() + 1); // Max timeDepthDiff occurs when depth is N and we are dealing with the initialBacteria query (t == -1).
2 Likes
46

Thank you. That clears it up. I have read at multiple places that size of Segment Tree in the worst case can go upto 4 times the space of array, may be I have to re-look into that.

2 Likes
47

Below I’ll discuss the space requirement for an array based implementation of the segment tree.

Let’s consider the base array A[] to be of size N.
All the array elements are placed in the leaf nodes. So, the number of leaf nodes is N.

What’s the maximum size of the segment tree?

We consider the case where the last level contains at least one of the leaf nodes.
Then, the tree would have the following distribution of nodes:

level | number of nodes
0     | 2 ^ 0
1     | 2 ^ 1
2     | 2 ^ 2
.     | .
.     | .
.     | .
n     | 2 ^ n

. . . where, 2^n is the lowest power of 2 which is not less than N.

So, the size of the segment tree is the sum of the G.P.

\approx 2 ^ {\lceil log_2 N\rceil + 1} - 1
\approx 2 ^ {\lceil log_2 N\rceil + 1}
\approx 2 ^ {log_2 N + 2}
= 2 ^ {log_2 N} \times 2 ^ 2
= N \times 4
= 4N

Please correct me if I went wrong anywhere. Thank you. :slightly_smiling_face:

5 Likes
48

Give me a treat? It’s because of my post :stuck_out_tongue: