vaibhav.verrma's blog

By vaibhav.verrma, history, 4 years ago, In English

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?

  • Vote: I like it
  • +4
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

The use of long long everywhere is the cause of TLE here. Same solution gets Accepted if you use int instead of long long.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.