Editorial for Bubble Cup V8 D Tablecity

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

First notice that parity of thief's $X$ ~X~ coordinate changes every time he moves.

Assume that at the beginning $X$ ~X~ coordinate of thief's position is odd, and check districts $(1,1)$ ~(1,1)~ and $(1,2)$ ~(1,2)~. The next day check districts $(2,1)$ ~(2,1)~ and $(2,2)$ ~(2,2)~ and so on until $1000^{th}$ ~1000^{th}~ when you check districts $(1000,1)$ ~(1000,1)~ and $(1000,2)$ ~(1000,2)~. What is achieved this way is that if starting parity was as assumed, thief could have never moved to district with $X$ ~X~ coordinate $i$ ~i~ on day $i+1$ ~i+1~, hence he couldn't have jumped over the search party and would've been caught. If he wasn't caught, his starting parity was different than we assumed, so on $1001^{st}$ ~1001^{st}~ day we search whatever ( $1$ ~1~ and $1001$ ~1001~ are of the same parity, so we need to wait one day), and then starting on $1002^{nd}$ ~1002^{nd}~ day we do the same sweep from $(1,1)$ ~(1,1)~ and $(1,2)$ ~(1,2)~ to $(1000,1)$ ~(1000,1)~ and $(1000,2)$ ~(1000,2)~ and guarantee to catch him.

Shortest possible solution is by going from $(2,1)$ ~(2,1)~ and $(2,2)$ ~(2,2)~ to $(1000,1)$ ~(1000,1)~ and $(1000,2)$ ~(1000,2)~ twice in a row, a total of $1998$ ~1998~ days, which is correct in the same way. First sweep catches the thief if he started with even $X$ ~X~ coordinate, and second sweep catches the thief if he started with odd $X$ ~X~ coordinate.

Comments

There are no comments at the moment.