QUEENATTACK - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Lavish Gupta
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh

DIFFICULTY:

To be calculated

PREREQUISITES:

None

PROBLEM:

A queen is placed at cell (X, Y) on a N\times N chessboard. How many cells does it attack?

EXPLANATION:

Let’s separately count the squares that are under attack horizontally, vertically, and diagonally. Our answer is the sum of these squares.

  • Horizontally: The queen can move any number of squares horizontally. So, every square in its row is under attack, apart from the one it’s standing on. This gives us N-1 squares.
  • Vertically: The exact same reasoning as the horizontal case gives us N-1 more squares in this case as well.
  • Diagonally: There are two diagonals to consider, so once again we count them separately and add up.
    • One diagonal consists of all squares (A, B) such that A+B = X+Y. A little experimenting on paper should show you that the number of squares on this diagonal is the difference between N+1 and X+Y, i.e, |(N+1) - (X+Y)|. Subtract one from this to account for the square the queen is standing on.
    • The other diagonal consists of all squares (A, B) such that A - B = X - Y. Once again, a little experimenting will show that the number of squares on this diagonal is N - |X - Y|, from which we subtract one.

Add up the answers to these four cases to obtain the final answer.

TIME COMPLEXITY:

\mathcal{O}(1) per test.

CODE:

Python 
for _ in range(int(input())):
	n, x, y = map(int, input().split())
	ans = 2*n # row + column
	ans += n - abs(x - y) # diagonal 1
	ans += n - abs(n+1 - (x + y)) # diagonal 2
	print(ans - 4)
1 Like