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:

1. N is odd: The minimum number of moves required is N-1, which can be achieved as follows:
(1,1)\to(2,2)\to(3,1)\to(4,2)\to\dots\to(N,1)
1. 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:
(1,1)\to(2,2)\to(3,1)\to(4,2)\to\dots\to(N,2)\to(N,1)

Therefore, output

• N-1 when N is odd, and
• N otherwise.

O(1)

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