KNIGHTATTACK - Editorial

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;
}
1 Like

Can you point out the mistake in my program
#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–)
{
int x,y,a,b;
cin>>x>>y>>a>>b;
int k=x-a;
int j=y-b;
int c=0,r=0;
if(k>0)
{
k=k*-1;
}
if(j<0)
{
j=j*-1;
}
if(k==0)
{
if(j==2||j==4)
c++;
}
if(k==1)
{
if(j==1||j==3)
c++;
}
if(k==3)
{
if(j==1||j==3)
c++;
}
if(k==4)
{
if(j==0||j==2)
c++;
}
if(j==1&&k==1)
{

        if(x-8==0)
        {
            if(y-1==0||y-8==0)
            r++;
        }
         if(x-1==0)
        {
            if(y-1==0||y-8==0)
            r++;
        }
         if(a-8==0)
        {
            if(b-1==0||b-8==0)
            r++;
        }
         if(a-1==0)
        {
            if(b-1==0||b-8==0)
            r++;
        }
    }
    
   if(r>0)
   {
       cout<<"no";
   }
    else if(c>0)
    {
        if((a+x)%2==0&&(y+b)%2==0)
        cout<<"yes";
        else
        cout<<"no";
    }
    else
    {
        cout<<"no";
    }
    cout<<endl;
}
return 0;

}

I do believe that my solution is easy to understand, take a look if the editorial does not make sense. First, I mark all of the places that knight 1 can go. Then, I analyze all the places that knight 2 can go, and see if any of those places have already been marked (able to be reached by knight 1). If so, there is an answer. The dx and dy arrays are to iterate through all possible knight movements.

https://www.codechef.com/viewsolution/67341773

bruh that is a perfect implementation.

1 Like

Thanks for sharing your code but i am not understanding why might my code be not correct can you please have a look at it

It’s hard to explain without fully understanding your thinking.

But there is a bug, for example, if x=1, y=1, a=2, b=2, then your k=-1 but then you do k > 0 check and then multiply it by -1, but if k=-1 then it’s not turned into a positive number.

You have to print your state to see what is wrong if you cannot figure it out just by reading the code.

yes i meant to do k<0

As the grid size is 8X8, we are checking every cell of the grid ,
What if the grid size is like 10^5X10^5 ( I mean larger grid), is there any way to check other than this??

2 Likes

You start your knight from x_1, y_1, jump all possible moves and store them in set a. Start your other knight from x_2,y_2, jump all possible moves and store them in set b.

Remove the moves where knights jumped outside of the board.

If a \cap b \neq \empty (intersection), then you can place one knight on any move in the intersection and it will attack both squares.

Python code below does what the explanation above says.

m = [(2, 1), (-2, -1), (2, -1), (-2, 1)]
X, Y = 9, 9
for _ in range(int(input())):
	x1, y1 = map(int, input().split())
	x2, y2 = map(int, input().split())
	a, b = set(), set()
	for x, y in m:
		a.add((x1+x, y1+y))
		a.add((x1+y, y1+x))
		b.add((x2+x, y2+y))
		b.add((x2+y, y2+x))
	a = set((x, y) for x, y in a if x>0 and y>0 and x<X and y<Y)
	b = set((x, y) for x, y in b if x>0 and y>0 and x<X and y<Y)
	print("YES" if a.intersection(b) else "NO")
2 Likes

Another approach is to make each possible knight move from the first square, then check if the move to the second square is one of the permitted moves (and is on the board):

N_moves = [(-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)]

T = int(input())
for tx in range(T):
    x1, y1 = map(int,input().split())
    x2, y2 = map(int,input().split())
    for dx, dy in N_moves:
        nx = x1 + dx
        ny = y1 + dy
        if (nx-x2, ny-y2) in N_moves:
            if nx >= 1 and nx <= 8 and ny >=1 and ny <= 8:
                print("YES")
                break
    else:
        print("NO")

(This uses the else option on the for loop, which is executed in the event of normal termination of the loop. An alternative way to do this would be to initially set a result variable as "NO" and only change to "YES" if a viable intermediate knight step is found).

Note that in fact the possible differences between the first square and the second square allowing a knight fork is quite limited anyway, and by symmetry can be largely tested on the absolute differences, for a quicker but perhaps less obvious solution. Only if one of the squares is right in the corner is there any change in which offsets are feasible and achievable.

I have a very Understandable Solution for this Problem.
KnightCheck Function Checks that if knight at (i,j) attacks point (x,y) for 1<= i,j <=8
and in main function we input all the knight points that can attack 1st point along with the 2nd given point.
#include<bits/stdc++.h>
using namespace std;
bool knightCheck(int i, int j , int x , int y)
{ // a knight is at i,j and we have to check if it can attack x,y
bool point = false;
if(i<1 || i >8 || j<1 || j>8){return false;}
if(x==i-1 && y==j+2) point= true;
else if(x==i+1 && y==j+2) point=true;
else if(x==i-2 && y== j+1) point = true;
else if(x==i+2 && y==j+1) point = true;
else if(x==i-2 && y==j-1) point = true;
else if(x==i+2 && y==j-1) point = true;
else if(x==i-1 && y==j-2) point = true;
else if(x==i+1 && y==j-2) point = true;

return point;

};
int main()
{
int T; cin>>T;
while(T–){
int x,y,x1,y1;
cin>>x>>y>>x1>>y1;
if( knightCheck(x-1,y+2,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+1,y+2,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x-2,y+1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+2,y+1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x-2,y-1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+2,y-1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x-1,y-2,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+1,y-2,x1,y1) ) cout<<“Yes”;
else cout<<“No”;
cout<<endl;
}
}

Can someone tell me the input of 2nd subtask?? @utkarsh_adm
I need to know why my logic was failing in that.

Can you please point out a test case or the problem where this code fails?
Explanation: I am considering each possible pair of y’s and their corresponding x’s and checking for each pair using the difference.
Since the white pieces need to be within a range of 4 or less, otherwise the knight can’t attack, I’ve considered every possible difference using direct if conditions.
Code:`

void solve(){
    int x1, y1, x2, y2;
    cin>>x1>>y1>>x2>>y2;
    if(abs(y1-y2)>4 || abs(x1-x2)>4) { cout<<"NO"<<endl; return; }
    if((abs(y1-y2)==4 || abs(y1-y2)==0)&&(abs(x1-x2)==2 || abs(x1-x2)==0)){
        cout<<"YES"<<endl; return;
    }
    if((abs(y1-y2)==3 || abs(y1-y2)==1) && (abs(x1-x2)==1 || abs(x1-x2)==3)){
        cout<<"YES"<<endl; return;
    }
    if(abs(y1-y2)==2 && (abs(x1-x2)==4 || abs(x1-x2)==0)){
        cout<<"YES"<<endl; return; }
    cout<<"NO"<<endl;
}`

@admin, Could you please tell me which test case is failing, because I am having a different approach. I also gone through

Ask a Doubt

and that guy have told me to post this message.
I am focusing on the absolute difference between two given positions and covered all the cases as you can see in the attachment.

Please let me know which test case is failing by my solution.
You can find solution at - SOLUTION
or I am also posting the code -

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	
	while(t--)
	{
	    int x1,x2,y1,y2,distance;
	    
	    cin>>x1>>y1;
	    cin>>x2>>y2;
	    
	    distance = abs(x1-x2)+ abs(y1-y2);
	    
	    if(distance>6)
	    {
	        cout<<"NO"<<endl;
	    }
	    else if(distance==6)
	    {
	        if(abs(x1-x2)<=1 || abs(y1-y2)<=1)
	            cout<<"NO"<<endl;
	        else 
	            cout<<"YES"<<endl;
	    }
	    else if(distance==4)
	    {
	        if(abs(x1-x2)==abs(y1-y2))
	        {
	            cout<<"NO"<<endl;
	            
	        }
	        else
	            cout<<"YES"<<endl;
	    }
	    else if(distance==2)
	    {

	            cout<<"YES"<<endl;
	    }
	    else if(distance==0)
	        cout<<"YES"<<endl;
	    else
	        cout<<"NO"<<endl;
	    
	}
	return 0;
}

Please tell me which test case is failing ?

#include<bits/stdc++.h>
using namespace std;
bool knightCheck(int i, int j , int x , int y)
{ // a knight is at i,j and we have to check if it can attack x,y
bool point = false;
if(x==i-1 && y==j+2) point= true;
else if(x==i+1 && y==j+2) point=true;
else if(x==i-2 && y== j+1) point = true;
else if(x==i+2 && y==j+1) point = true;
else if(x==i-2 && y==j-1) point = true;
else if(x==i+2 && y==j-1) point = true;
else if(x==i-1 && y==j-2) point = true;
else if(x==i+1 && y==j-2) point = true;

return point;

};
int main()
{
int T; cin>>T;
while(T–){
int x,y,x1,y1;
cin>>x>>y>>x1>>y1;
if( knightCheck(x-1,y+2,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+1,y+2,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x-2,y+1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+2,y+1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x-2,y-1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+2,y-1,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x-1,y-2,x1,y1) ) cout<<“Yes”;
else if( knightCheck(x+1,y-2,x1,y1) ) cout<<“Yes”;
else cout<<“No”;
cout<<endl;
}
}
this solution is passing one testcase and failing one. can someone please check
Function knightCheck that if position (x1,y1) is attacked by knight (I,j)
and main part checks knightCheck function for all the 8 knights that can attack (x,y) and (x1,y1) both

@umesh_5 Your failing case is probably the one where one piece is in the corner and the other piece is diagonally adjacent. Normally two pieces diagonally adjacent can be forked by a knight, but in the case above the two possible forking squares are both off the board.