mufaddalnaya's blog

By mufaddalnaya, history, 5 months ago, In English,

In the latest codeforces Div. 3 contest, my solution for problem D is getting time limit exceeded. The code is written in java and I couldn't figure out the reason. The Problem and my 54157908. I saw some other java code which are accepted that have similar time complexity as my code.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Not quite sure, but am assuming that the problem is with the long division here:

for(int i=0;i<n;i++){
   if (ans%a[i]==0) continue;
   long lifesaver = gcd(a[i],ans);
   ans *= (a[i]/lifesaver);  //O(n^2)
}

I've read this about why long division has a high complexity: https://stackoverflow.com/questions/2486152/how-is-schoolbook-long-division-an-on2-algorithm

please share other Java solutions that got accepted so we can try to compare those solutions.

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

    Actually the problem was that I was using the gcd function due to which i would get a huge number at the end may be 10^18 and then i was trying to check all its divisors and therefore getting time limit exceeded.

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

      Interesting, I didn't think that might happen as the gcd function takes O(logn) time. Oh well, thanks for the info ^^