SCALSUM - Editorial

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

85

can you tell why my code is giving tle in last cases i have done exactly like editoriol changed hash function can you check the issue??

86

@codemaster7s. You have added the submit link, not your solution link.

87

https://www.codechef.com/viewsolution/39689849
this is the link

88

@codemaster7s I checked your code. You did according to the editorial. Try the Iterative method for precomputation and answering queries.