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 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: CodeChef: Practical coding for everyone
JAVA code: CodeChef: Practical coding for everyone
1 Like
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. 
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??
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 → CodeChef: Practical coding for everyone
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
Online judge can perform only 10^8 operations in 1 second. So for 2 seconds it can only perform 2 * 10^8 operations. 10^11 operations would take 1000 seconds which is more than 15 minutes. Hope you got your doubts cleared.
1 Like