Editorial for Yet Another Contest 6 P3 - No More Cell Phone Messaging

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.

Author: Josh

Subtask 1

If $X$ ~X~ is the answer to the query $(1, 1)$ ~(1, 1)~, then the leftmost of Josh and Mike must be at $(X+1, 1)$ ~(X+1, 1)~.

Similarly, if $Y$ ~Y~ is the answer to the query $(N, 1)$ ~(N, 1)~, then the rightmost of Josh and Mike must be at $(N-Y, 1)$ ~(N-Y, 1)~.

Subtask 2

If we query at $(1, 1)$ ~(1, 1)~ and $(N, M)$ ~(N, M)~, we can use math to figure out which diagonals Josh and Mike are on.

Similarly, we query at $(1, M)$ ~(1, M)~ and $(N, 1)$ ~(N, 1)~, we can figure out which anti-diagonals Josh and Mike are on.

There are at most two possible sets of positions for Josh and Mike, depending on which diagonal corresponds to which anti-diagonal. We can query at one of the candidate positions to determine the answer. Be careful not to query outside the grid.

Comments

There are no comments at the moment.