SCALSUM - Editorial

https://www.codechef.com/submit/SCALSUM
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??

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

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

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

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: https://www.codechef.com/viewsolution/39401538
JAVA code: https://www.codechef.com/viewsolution/39473939

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

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

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

Try using vectors instead of map.

but in vector how would i got my previous calculated node ansers faster ??

Consider we just have k nodes in one level (where we do precomputation for each pair…)
Before doing that , store the indices of each node in a new vector … idx[node1] = 1… and so on
Then for each pair (node1 , node2) in that level precompute and store it in this index->idx[node1]*level_size + idx[node2] of the main vector at each level. (G[100005][index]).
So , when ever you get two ancestors that have been precalculated then use this index of vector G[level] , idx[ancestor1]*level_size + idx[ancestor2] from here you can get the value …
This is my code for reference
Hope this helps…

in this code you didnt used mod with 2^32?? why its so?? or i am missing something??

see this. As i have used unsigned int(which considers only last 32 bits…) it would be fine

1 Like

https://www.codechef.com/viewsolution/39720499
i have done with vector as well its still tle can you check it where its wrong??

I found one mistake that you are doing a[v].push_back(v). But I don’t know it will be useful or not.

its still showing tle done exactly like your code but why its showing tle for more cases now?

hey i got ac thanks for your guidence now by changing mod to unsigned int now may be that may be reason for them to give modulo from power of 2^32 because modulo is somewhat expensive …
link -> https://www.codechef.com/viewsolution/39723475

Ok nice…

Can anyone please explain that where does my reasoning go wrong? Naive approach will perform O(NQ) operations which is approx. 10^11 operations which can be done in 2 sec.
So, naive approach should give AC