DISABLEDKING - Editorial

editorial
, ,
1

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:

  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.

TIME COMPLEXITY:

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