KNIGHT2 - EDITORIAL

editorial
,
1

PROBLEM LINK:

Contest
Practice

Setter: jeevanjyot
Testers: satyam_343, rivalq
Editorialist: hrishik85

DIFFICULTY:

1144

PREREQUISITES:

None

PROBLEM:

Chef has an 8 \times 8 chessboard. He placed a knight on the square (X_1, Y_1). Note that, the square at the intersection of the i^{th} row and j^{th} column is denoted by (i, j).

Chef wants to determine whether the knight can end up at the square (X_2, Y_2) in exactly 100 moves or not.

For reference, a knight can move to a square which is:

  • One square horizontally and two squares vertically away from the current square, or
  • One square vertically and two squares horizontally away from the current square

A visual description of this may be found here.

EXPLANATION:

Chef has exactly 100 moves.
Important point to note here is that a knight can travel from one corner of the board at (1,1) to the opposite corner at (8,8) in 6 moves.

  • In effect, 100 moves are large enough to have repetitive moves on the chess board.
  • If a knight is on any position (X,Y) on an odd move, can it ever be on the same position on the 100^{th} move? Not possible.

In effect, the problem reduces to finding squares that the knight will reach on odd moves. Such squares can never be reached on the 100th move.
Given any (X_1, Y_1) and (X_2, Y_2), if ((X_2+Y_2)-(X_1+Y_1)) is divisible by 2, then the knight can reach (X_2, Y_2) on the 100^{th} move. Else it cannot.

TIME COMPLEXITY:

Time complexity is O(1).

SOLUTION:

Editorialist's Solution 
t=int(input())
for _ in range(t):
    x1,y1,x2,y2=map(int,input().split())
    if ((x2+y2)-(x1+y1))%2==0:
        print('YES')
    else:
        print('NO')
2

A simpler way of looking at the problem is that after every 2 moves the knight will be on a square of the same colour as it started. As there are 100 moves, a large even number, the knight can reach any square of the same colour as it starts on. A more interesting problem is to find the minimum number of moves for the knight to move from start to finish.

3 Likes