It passed only in 0.47 Sec
Can someone explain it.
what is PBDS ?
I think that’s why he is 7 star.
@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
policy based data structure
ohhhhh man
I thought it was feature only for gcc compiler !!!
Are you sure it is built in STL ???
Too good! And congrats for the Five Stars. Any tips on how can I reach the same(2000+) rating?
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
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
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
Ok - I did a quick hack-fix to fix the segfault, and probably introduced a new problem which your fix didn’t
I just used fixParentAndChild
and then the logic is the more straightforward isLeaf = node->children.empty();
.
@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 minTDDand
int 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 takes
4 * size_of_array` as space. Can you please help me understand this part?
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).
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.
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.
Give me a treat? It’s because of my post