PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
CAKEWALK
PROBLEM:
Given a chess board of size N\times N. A ‘disabled’ king is initially at cell (1,1). In one move, the king can move from cell (x,y) to any of the following cells (provided they are within the board):
- (x, y + 1)
- (x, y - 1)
- (x + 1, y + 1)
- (x + 1, y - 1)
- (x - 1, y + 1)
- (x - 1, y - 1)
Determine the minimum moves required to reach cell (N,1).
EXPLANATION:
Observation: The minimum moves required is always \ge N-1.
Proof
In one move, the king can travel atmost 1 step to the right. The destination cell is exactly N-1 steps to the right of the initial cell.
Thus, the minimum moves required is always \ge N-1.
There are now two cases:
- N is odd: The minimum number of moves required is N-1, which can be achieved as follows:
- N is even: Here, it isn’t hard to conclude that it is impossible to reach the destination cell using only N-1 moves. However, it can be done in N moves, in the following fashion:
Therefore, output
- N-1 when N is odd, and
- N otherwise.
TIME COMPLEXITY:
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters