Блог пользователя vaibhav.verrma

Автор vaibhav.verrma, история, 4 года назад, По-английски

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
  • Проголосовать: не нравится

»
4 года назад, # |
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.

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.