aryam_agarwal's blog

unable to understand reason for TLE when complexity is same
By aryam_agarwal, history, 22 months ago, In English

I have been solving Problem C from Codeforces Round #885(Div. 2),1848C - Vika and Price Tags. Below code gets accepted but adding a little change to the calc function gives TLE,

Accepted Submission: 266686268 .....TLE: 266686665

I changed 

return calc(b ,rem ) + q + q/2;

to 

 return calc(rem , b-rem ) + q + q/2 + 1;

in the calc function and it is giving a TLE after this change even though the overall complexity remains the same. Can anyone explain the same?

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

Comments Comments (3)
| Write comment?
»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

in calc function program under if(q%2!=0) are not same

→ Reply
»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I don't think these two programs are the same.

→ Reply
»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Function $$$calc$$$ in the first submission seems to be roughly equal to $$$gcd$$$ in terms of complexity, but in the second submission it is $$$O(b)$$$, $$$calc(1, 1e9)$$$ needs $$$1e9$$$ calls to be computed.

→ Reply