CSES-Two Knights problem: help needed!

can someone please help me in this problem??
https://cses.fi/problemset/task/1072
thanks!! :slight_smile:

2 Likes

+1 i also want to know the same …

from all possibilities of placing two knghts , you can substract those ones in which they both attack each other…(which are 4*(n-1)*(n-2) for given nXn board)

1 Like

Total possibilities are (n^2)C2

sorry, my fault.
i got ac with (n^2)C2 - 4*(n-1)(n-2)
can you please explain how did you get this 4
(n-1)*(n-2) term?
thanks!!

int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        if(i==1)
            cout<<0<<"\n";
        else if(i==2)
            cout<<6<<"\n";
        else
        {
            int p=i*i;
            int j=i-2,k=p*(p-1)/2;
            k-=8*j*(j+1)/2;
            cout<<k<<"\n";
        }
        
    }

Possible Duplicate: Number of ways two knights can be placed such that they don’t attack

@venturer have shared a link there: Explanation

2 Likes

can u please explain??

https://oeis.org/A172132

Hope this will help.

2 Likes

https://discourseproduction.s3.dualstack.us-east-1.amazonaws.com/original/3X/8/5/85862d08488bc75788f06a53902fcc656bc85e19.png

number of ways in which two knights can attack each other is equal to twice the number of 2x3 and 3x2 matrices that can fit in NxN matrix. Because in every 2x3 or 3x2 matrix we can have 2 distinct position such that both can attack each other. Now the number of 3x2 matrix in nxn = (n-2)(n-1) . Similarly number of 2x3 matrix also equals to (n-2)(n-1). As there are 2 distinct positions in each such matrix our ans becomes 4(n-1)(n-2).

2 Likes