I don’t understand the motive behind equal score distribution among all problems. Why all problems weigh same?
I’ve used similar logic as well, only doing a DFS using queries and calculating the number of bacteria at any time. I realise it might TLE but I’m getting wrong answer. Can you please show me where I’m going wrong. Would be extremely helpful!
https://www.codechef.com/viewsolution/27331351
I was going through some successful submissions and I found this.
https://www.codechef.com/viewsolution/27205637
Can someone please explain what’s going on in this code?
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).