Two Knights Solution

16 June 2021

Statement

( The original statement can be found here )
Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.

Input
The only input line contains an integer n.

Output
Print n integers: the results.

Constraints
1 ≤ n ≤ 10000
Time limit : 1.00s
Memory limit : 512MB


Example

Input :
8

Output :
0
6
28
96
252
550
1056
1848

Solution

This problem can be solved using mathematics and it might look quite daunting at first sight. One way of approaching this problem requires us to find the total number of ways to place two knights on the board and subtract the number of distinct ways to place two knights so that they attack each other.

Firstly we need to figure out how many ways there are to place two knights on the board. Since the first knight can be placed anywhere on the board (k^2 positions) and the second knight anywhere else (k^2 - 1 positions) then we can formulate the following expression.

We divide by two since the knights are indistinguishable and we want to remove duplicate cases where the knights positions are swapped.

Now, all we have to find out is how many of these positions put both knights under attack. As we can see in the following image there are eight different attacking configurations that can be made by a knight.

Since the board is a square we can deduce there are the same number of attacking positions for each of the eight configurations. So the last question that remains is how many ways are there to place each of the configurations in a k×k board and given that one attack occupies a block of dimensions 2×3 (and vice-versa) then we have (k-1)×(k-2) ways of placing the 2×3 block on the board. To get the total number of distinct attacking positions we multiply this value by eight and divide it by 2 to remove the duplicates.

The last step is to subtract the total amount of attacking positions from the total number of ways to place 2 knights on the board and we will get our answer. The following expression represents the answer:

#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n;
    cin >> n;

    cout << 0 << endl;
    for (long long i = 2 ; i <= n ; i++) {
      cout << (i * i) * (i * i - 1) / 2 - (4 * (i - 2) * (i - 1)) << endl;
    }

    return 0;
}

This algorithm runs in time complexity of O(N) and space complexity of O(1) and it seems to me that it is a pretty efficient approach to the problem.