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.

3 Likes

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

1 Like

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).

4 Likes

the book is russian

follow this …it helped me too

1 Like
#include<bits/stdc++.h>
using namespace std;
#define read(x) long long int x; cin>>x
#define from(i,a,b) for(int i=a;i<b;i++)
#define fromr(i,a,b) for(int i=a;i>b;i--)
#define test long long int t; cin>>t; while(t--)
#define inArray(arr) for(int i=0;i<n;i++){ cin>>(arr)[i];}
#define count long long int c=0
#define str(s) string s; cin>>s
#define yes cout<<"YES"<<endl
#define no cout<<"NO"<<endl
#define ll long long int
#define pb push_back
#define pob pop_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define ff first
#define ss second
void _KD_(){
    read(n);
    from(i,1,n+1){
        if(i==1){
            cout<<0<<endl;
        }else if(i==2){
            cout<<6<<endl;
        }else{
            ll total = ((i*i)*((i*i)-1LL))/2LL;
            ll thay = (i-2LL)*((4LL*i)-6LL) + (2LL*i - 4LL);
            cout<<total - thay<<endl;
        }
    }
}
int main()
{
    _KD_();
    return 0;
}

Basically, first knight has k^2 choices second has k^2 - 1 but as the two are indistinguishable \frac{k^2 \cdot (k^2 - 1)}{2} total choices. Now one attack occupies a block of dimensions 2×3 as it goes upward and down \implies \frac{(k-1)(k-2) \cdot 8}{2}. We multiple by 8 as there are 8 moving possibilites and divide by 2 to remove the duplicates. \frac{k^2 \cdot (k^2 - 1)}{2} - 4(k-1)(k-2)
Hope this help