aryam_agarwal's blog

By aryam_agarwal, history, 3 weeks ago,

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?

• 0

 » 3 weeks ago, # |   0 in calc function program under if(q%2!=0) are not same
•  » » 3 weeks ago, # ^ |   0 Yes I have intentionally made the change in the statement under the if condition, that’s why I am adding an additional 1 when I am passing calc(rem , b-rem) instead of calc(b,rem)…the answer would remain the same so should the complexity be. But it is giving a tle
 » 3 weeks ago, # |   0 I don't think these two programs are the same.
•  » » 3 weeks ago, # ^ |   0 Two programs are not same as I have changed the statement under the if condition if(q%2!=0) But the changing this condition should not increase the tle as i am adding an extra one and reducing one step
 » 3 weeks ago, # |   0 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.
•  » » 3 weeks ago, # ^ |   0 Can you explain more as to why it would require 1e9 calls to compute b-rem in calc(rem , b-rem).