!Weird (chnging pos of function call made my code faster )WHY?

http://discuss.codechef.com/questions/63511/help-for-tle-answer-is-100-correct----> i posted a question here for a TLE ERROR in “prime palindrome” (i donno why link is not working) ppl helped me a lot in optimising code there & i optimised it to large extent BUT SOMETHING WEIRD HAPPENED
http://www.codechef.com/viewsolution/6056842 <-Solution2
&&&&http://www.codechef.com/viewsolution/6056846 <-Solution1
what happened is i just exchanged the function call " reverse " and " prime "… My solution1 was getting tle error but after exchanging function calls in if statement as in solution 2 it got accepted.

Yes this is a very important optimization, let me explain this behavior ( I helped you optimizing the code in the previous question which is now not opening , weird !!!). The reason is that complexity of those specific functions differ largely.

Prime() has a loop from 3 to sqrt(n) (temp in code), so loop executes n times ( temp times ), which takes more time than Reverse().

At first we need to understand how if statement works.

if((a==0) && (b==5)) means at first a is checked if zero or not. If a is not 0 then the second condition is not checked at all. b==5 is checked only if a is 0.

Now in your code, the main calling order in if statement is deciding the execution path.

In this statement => if(reverse(i)== i && prime(i)==0) if the number is not palindrome then primality is not checked which saves a lot time.

But in case of if(prime(i)==0 && reverse(i)== i) , it checks primality everytime (incurs higher execution time ) and then if true checks for palindrome. This takes more time as call to prime() is invoked first. The complexity of prime() is much more than reverse() which adds upto the total and gives TLE.

But this does not happen in the first case as prime() is called only if a number is palindrome.

Very weird behavior indeed at a glance but if analysed gives a beautiful reason of such behaviour. :smiley:

Thank You Very Much @mediocoder for the whole explaination It is very kind of you…


You’re welcome.

If your question has been answered then kindly accept the correct answer as it will help others find the correct answer/explanation and also can be marked as closed.

how do i close an answer