mufaddalnaya's blog

Need Help
By mufaddalnaya, history, 6 years 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

Comments Comments (2)
| Write comment?
»
6 years 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.

→ Reply
  • »
    »
    6 years 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.

    → Reply