### vaibhav.verrma's blog

By vaibhav.verrma, history, 6 weeks ago, ,

https://codeforces.com/contest/236/problem/B

Can someone explain why I am getting TLE in the following solution? https://codeforces.com/contest/236/submission/86035444

I have pre-calculated the number of factors of all the numbers up to 1000000, and then looped through each a,b,c and added the number of factors of each i*j*k to the answer. I tried multiple test-cases and they all are giving me the correct answer almost immediately. What is the problem here?

• +4

 » 6 weeks ago, # | ← Rev. 2 →   +8 The use of long long everywhere is the cause of TLE here. Same solution gets Accepted if you use int instead of long long.
•  » » 6 weeks ago, # ^ |   0 True, This is the accepted submission after changing long long to int Accepted Solution
•  » » 5 weeks ago, # ^ |   0 Got it. Thanks a lot!
 » 5 weeks ago, # |   +3 The long long problem isn't really the core issue here. I think your basic algorithm to compute $d(i)$ for $i$ up to $N$ takes around $O(N \sqrt{N})$, which for $N = 10^6$ is a little too slow. You were able to squeeze it in because your implementation was efficient and C++ is fast.See if you can think of a way to compute all the divisor counts at once by reducing the repeated work. I think there's sort of a sieving approach that makes sense.
•  » » 5 weeks ago, # ^ |   0 Okay, I'll try that approach. Thank you!
 » 5 weeks ago, # |   0 With memoization it passes in 62 ms: 86296254 I calculated that there are at $N = 46911$ distinct products in the case $a = b = c = 100$, so the time complexity is $O(N\sqrt{1e6}) = 4.6911e7$, which is fast enough.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Nice! That's a new approach for me. Also, I noticed that your rating has increased quite steadily in a short span of time. Can you tell me how you practice? Do you solve problems randomly or topic-wise? I started CP around the same time as you but haven't made considerable progress.
•  » » » 5 weeks ago, # ^ |   0 Virtual participation and random solving by difficulty in the code forces problem set and up-solving contests. I turn tags off since they spoil the problems.