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

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.