Editorial for DMOPC '22 Contest 4 P3 - K-Knight

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: Riolku


Binary Search


WLOG x \le y. If all moves are made with the long part of the move going vertically, then x must have the same parity as the operation count.

Otherwise, the moves we make horizontally, call it h, and the vertical moves v, must satisfy the inequalities v + h \cdot k \ge x and v \cdot k + h \ge y.

Since we binary search, we know the value of v + h, call it m, so we have m + h \cdot (k - 1) \ge x or h \ge \frac{x - m}{k - 1} and a similar equation for v.

We can then compare our minimum h value and minimum v value to see if a given m is possible.


There are no comments at the moment.