CATHIEF TLE Help

Hello All,
This is my first contest. Solved one problem easily but I can’t understand why I am getting a Time limit exceeded error in this solution.
Please have a look- https://www.codechef.com/viewsolution/40640166
and it will be helpful if one can share the approach for this problem.

Thanks in advance

N is 109 which gives u TLE

can you share the approach for this please.

You are using brute force , Consider in worst case x=0 , y=10^9 ,k=1 , n=10^9
it will be very slow since it will calculate and check every value of x,y.
TLE is very common if you brute force large constraints
Here is my solution.

1 Like
if(abs(x-y)%(2*k) ==0):
   print("Yes")
else:
   print("No")

take pen paper and check why it is correct

1 Like

See here if u observe both has to move at a particular second either to their left or to their right now if thief has to be caught there should be One side blocked and on the other side the distance between police man and thief should be 2k and thus a the next second thief has to move to that integer and police man catches him .This situation only arises when the difference between policeman and thief is a multiple of 2k thus u only need to check whether the difference between the initial positions of them is a multiple of 2*k or not if so Yes else No

1 Like

Thanks …got it now…

Thank you for clear explaination…:grin::metal: