jenil0108's blog

By jenil0108, history, 6 months 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.

Full text and comments »

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