https://codeforces.net/contest/236/problem/B
Can someone explain why I am getting TLE in the following solution? https://codeforces.net/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?
The use of long long everywhere is the cause of TLE here. Same solution gets Accepted if you use int instead of long long.
True, This is the accepted submission after changing long long to int Accepted Solution
The
long longproblem 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.
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.
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.
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.