Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

jenil0108's blog

Seemingly same solutions 1 gets TLE the other gets AC
By jenil0108, history, 7 days ago, In English

While I was giving the recent Codechef Starters 139, I encountered TLE in the last TC, I optimized my solution and got the AC.
The problem was https://www.codechef.com/problems/COUNTN.

The approach to the question is add all the primes up to the smallest prime factor of K and multiply that sum to get the answer.
The original TLE solution iterates through the primes and breaks when K is divisible by a prime. I optimized it by getting the lowest prime factor and precomputing the sum of primes to get AC. Then after contest when I was seeing some other submissions I found out a solution almost the same as my TLE solution got AC and I was baffled. That solution stores the lowest prime factors and iterates through the list of primes till it reaches the LPF.
I tried to replicate it and here are the submission ids so you guys can see.
AC
https://www.codechef.com/viewsolution/1066327168
TlE
https://www.codechef.com/viewsolution/1066327170
(Note: both solutions have fastio used and are exactly same I just commented out the main logic of the code between the submissions.)

The only difference in the codes:
- In the AC solution the if condition compares (primes[i]==LPF[k]) and breaks.
- In the TLE solution the if condition checks (k%primes[i]==0) and breaks. By the way, LPF[k] is same as the first prime which divides k so both will break at the same iteration.

The only thing I can think of is that, if along with % operator, is a bit slower than == in the AC soliution.
But now comes the more confusing part, if we had an, if condition (k%primes[i]==0); within the loop of the AC solution it also gets AC.
Here is that submission id https://www.codechef.com/viewsolution/1066327202

Update: I also added a dummy statement after the (k%primes[i]==0) to avoid any compiler optimizations and it still gets AC, shouldn't this take more time than the TLE Solution?
https://www.codechef.com/viewsolution/1066440473

I have exhausted all my detective skills and that is why I am posting it here to find why this is happening. The thing is the iterative solution should never get an AC as the test cases are 1e4 and the total number of primes in the range are approx 8e4 so worst case it would have been more than 1e8.

Update 2: Since it x is a local variable the compiler still optimizes the code you can see the comment by djm03178 for more information. Basically, simple anser is don't trust modulo operator.

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

»
6 days ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

As you noticed, % operator is extremely slow especially when the divisor is not a constant. Since the most overwhelmingly slowest operation in the loop is that one operator, it's no wonder that it takes more than double execution time than simply comparing.

The last submission where you added if (k%primes[i]==0); is probably just optimized by the compiler and became non-existent, because that sentence doesn't do anything (if anything happens here it's a UB).

→ Reply
  • »
    »
    6 days ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Makes sense, I tried adding a statement too after the if condition but that also got AC. https://www.codechef.com/viewsolution/1066440473 Shouldn't this code be taking more time than TLE code?

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

      It's still possible for the compiler to notice that these added statements are not actually doing anything, and therefore erase them. In fact, the only variable that is affected is x which is a local variable, and it has absolutely no effect on any external things. I think, but not 100% sure, that if you change it to a global variable it may have actual effect.

      → Reply
    • »
      »
      »
      6 days ago, # ^ |
      ← Rev. 3   Vote: I like it +1 Vote: I do not like it

      I modified the code a little and tested:

      The only difference is whether I defined x as a local or a global variable.

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

        Ahhh that is so interesting. Didn't know about compiler optimizations that much but it is crazy thank you for the help.

        → Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Modulo operations are slow and here it will be used too many times which will cause tle

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Best practice: avoid modulo operator (%) wherever possible.

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jenil0108 (previous revision, new revision, compare).

→ Reply
»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jenil0108 (previous revision, new revision, compare).

→ Reply