SCALSUM - Editorial

editorial
, , , , ,
62

Hi,
I have a doubt regd the above problem. As mentioned in the third paragraph in the explanation section:
“In each block choose the layer with the least number of vertices. Select every possible pair from this layer to pre-process. Let’s observe that if the block has K vertices then in selected layer there could be at most K/sqrt(N) vertices”.

If I consider a binary tree with N = 31 vertices (please find the image link below), then
block size = sqrt(N) = sqrt(31) = 5.56 ~ 5
maximum number of vertices in a selected layer in a block = K/sqrt(N) = 31/5.56 = 5.568 ~ 5

This means that, all the levels come into a single block which has all 5 layers.
Maximum number of vertices in any selected layer in a block should not exceed 5.
But maximum number of vertices as per the diagram is 16 (in the last level)
Can someone please help me where am I going wrong?

binary tree would look like this : https://www.google.com/imgres?imgurl=https%3A%2F%2Fmedia.geeksforgeeks.org%2Fwp-content%2Fuploads%2Fbinary_tree-1.png&imgrefurl=https%3A%2F%2Fwww.geeksforgeeks.org%2Fperfect-binary-tree-specific-level-order-traversal%2F&tbnid=BT7Qs6cJDlR90M&vet=12ahUKEwjfvsSv7ojtAhWzk0sFHbeRCSQQMygAegUIARCiAQ..i&docid=xXDjpbYuLRe87M&w=774&h=322&q=binary%20tree%20with%2032%20vertices&ved=2ahUKEwjfvsSv7ojtAhWzk0sFHbeRCSQQMygAegUIARCiAQ

63

Strangely map does work…
Anybody can explain why manually computing upto depths less than = 1000
and memoizing for greater depths passes the 60 pts subtask?

submission - CodeChef: Practical coding for everyone

64

I implemented the same logic in Python and I am getting AC in SubTask-1 but in SubTask 2 and 3 I am getting RE and TLE.
Solution Link: CodeChef: Practical coding for everyone

Can Someone Please help?

65

Yeah, turns out unordered map doesn’t work well for many insertions and lookups (high constant factor) . I used gp_hash_table as @new_coder_12 did in his submission.

66

I tried the exact same approach described in the video editorial. Still, it is giving TLE.Kindly check which part of the code is causing the problem?

https://www.codechef.com/viewsolution/39671745

67

Which library should I include in my code to use this??

68

why modulo 2**32 is not computed in the editorials.

70

I think this one

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

look at the reply by @new_coder_12 for the ac code

72 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
   const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
    struct chash {
        int operator()(int x) const { return x ^ RANDOM; }
    };

gp_hash_table<ll, ui, chash> record;

Implement your own hash function for AC…read the codeforces blog given by @l_returns

73

they have used unsigned int which has the range 0 to 2^32…so acts like mod

74

What if tree structure is like, the first root and then its (3*10^5 - 1) child? Then in that case complexity will shoot to O(N^2)!

1 Like
75

I have to include this line only?? In my code??

76

i have included this line but still it giving tle for last two cases can you tell why??
submission>> CodeChef: Practical coding for everyone

77

can you please explain it in detail by giving a small example? I haven’t understand it clearly.

78

Range of unsigned int is 0 to 4,294,967,295 and 2^32 is 4,294,967,296. If at any point your ans becomes 4,294,967,296 the expected output is ans%4,294,967,296 which would be 0 and since unsigned int cant store 4,294,967,296 it would overflow and store it as 0 and your code would continue to add to this value …which is as good as using mod in this sum.

1 Like
80

I don’t know this kind of approach before. Thanks for explaining.

81

In that case, the first node will be selected for preprocessing. So, every query in the second level can be answered in 4 steps.

1 Like
82

Sorry cannot find the issue…i usually code in java and tried c++ only for this sum.
Maybe he can help @bennyjoseph.

83

Can you share some good resource for sqrt decompositions on tree??

84

It’s for minimum amount of vertexes in any blocks dont exceed k/sqrt(n)
Like realize it in this way you have 5 spaces and you have to put 20 packets in these spaces then then maximum value of minimum packets in any spaces don’t exceed 20/5 as puuting 4 in each essentially if you remove it from one next one become greater and minimum decrease more