SCALSUM - Editorial

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

89

Same code in C++ giving TLE but accepted in JAVA…
Is it because of the extra time we get in java or is it because of bad hashing of unordered_map in C++ ??
C++ code: CodeChef: Practical coding for everyone
JAVA code: CodeChef: Practical coding for everyone

1 Like
90

I have done precomputation iteratively …In which part you are saying to change?? Can you specify… It will be helpfull

91

Anyone who is getting tle (try using n maps and in those , use only sqrtn maps to store the pair values , which decreases time complexity a little bit) , Although it gave me (60 pts)…
This is my code , Anyone help me where i can optimise this code a bit more

92

Thanks, mate. Was struggling for the past few days. Things got clearer now. I’m very thankful to you. :smile: :smile:

93

Try using vectors instead of map.