PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: lavish_adm
Tester: utkarsh_adm, iceknight1093
DIFFICULTY:
1577
PREREQUISITES:
2D arrays, loops
PROBLEM:
Given two cells on the chess board, find if there is a third cell from which a knight can attack both the other cells.
EXPLANATION:
Since the chess board is pretty small - just 8 x 8, we can loop over all the 64 cells and check whether placing a knight there will attack the cells (x_1, y_1) and (x_2, y_2). And even if one of those 64 cells works, we output Yes. If none of them work, we output No.
So now, all that remains is to figure out how to check whether a knight on a call, say (x_4, y_4) attacks a given cell, say (x_3, y_3). For this, from the problem statement, we note that a knight attacks these cells:
One square horizontally and two squares vertically away from it, or
One square vertically and two squares horizontally away from it
So we just check if x_3 and x_4 are one unit apart, and simultaneously, if y_3 and y_4 are two units apart. If so, then they satisfy the first criteria. To do this, we just check whether the absolute difference of (x_3 - x_4) is 1, and whether absolute difference of (y_3 - y_4) is 2.
Similarly, for the second point, we check whether absolute difference of (x_3 - x_4) is 2, and whether absolute difference of (y_3 - y_4) is 1.
If either of these two points are satisfied, we know that the cell is attacked.
TIME COMPLEXITY:
Time complexity is O(8 * 8) = O(1).
SOLUTION:
Tester's Solution
for _ in range(int(input())):
x1, y1 = map(int, input().split())
x2, y2 = map(int, input().split())
ans = 'NO'
for x in range(1, 9):
for y in range(1, 9):
mask = 0
for dx in [1, -1, 2, -2]:
for dy in [1, -1, 2, -2]:
if dx%2 == dy%2:
continue
if x + dx == x1 and y + dy == y1:
mask |= 1
if x + dx == x2 and y + dy == y2:
mask |= 2
if mask == 3:
ans = 'YES'
print(ans)
Editorialist's Solution
#include <iostream>
using namespace std;
int testcases,x1,x2,y1,y2;
// Returns true if a knight in (x4, y4) attacks the cell (x3, y3)
bool doesAttack (int x3, int y3, int x4, int y4)
{
if( (abs(x3-x4)==1) && (abs(y3-y4)==2) )
return true;
if( (abs(x3-x4)==2) && (abs(y3-y4)==1) )
return true;
return false;
}
int main() {
cin>>testcases;
while(testcases--)
{
cin>>x1>>y1>>x2>>y2;
int found = 0;
for(int i=1;i<=8;i++)
{
if(found == 1)
break;
for(int j=1;j<=8;j++)
{
if( ((i==x1)&&(j==y1)) || ((i==x2)&&(j==y2)) )
continue;
// (i, j) is now a cell where we can place the knight.
if( doesAttack(x1, y1, i, j) && doesAttack(x2, y2, i, j) )
{
found = 1;
break;
}
}
}
if(found == 1)
cout<<"Yes\n";
else
cout<<"No\n";
}
return 0;
}
