_Theyvansh_'s blog

By _Theyvansh_, history, 5 days ago, In English

Problem : https://codeforces.com/contest/1538/problem/D

Solution Link : https://codeforces.com/contest/1538/submission/119077891

Can anyone explain why I am getting TLE on test 6 for this solution?

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I get TLE like you too. But after I changed using long long to int then I got AC.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This problem is so weird that you got AC when you use int but get TLE when you use long long

    • »
      »
      »
      5 days ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      yeah I got AC too. But why long long is leading to TLE?

      • »
        »
        »
        »
        5 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The time to process with long long is a little bit longer than that of int. So using int can speed up your program for a little bit and got AC in cases that your program execution time exceed the time limit with a very small amount of time.

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

          Yeah, I remember one of the dp problems in CSES having the same problem, took me a long time to figure out what went wrong.

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
»
5 days ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

I had the same problem. I fixed it by simply writing prime factorization (I counted all prime numbers from $$$2$$$ to $$$ \sqrt {10 ^ 9} $$$))

TL6: https://codeforces.com/contest/1538/submission/119027345

AC: https://codeforces.com/contest/1538/submission/119038949

»
5 days ago, # |
  Vote: I like it +7 Vote: I do not like it

i don't know why many people didn't get TLE with that solution. but as i know T*sqrt(1e9)*2 = 4e8 = 4seconds is TLE. at least, that's the reason for your TLE.

To be safe, you need to precalculate all prime numbers from 2 to sqrt(1e9) and only check thoses numbers.

  • »
    »
    5 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I did the same and it worked