Two Knights
For every board size from 1 to n, count how many ways two knights can be placed without attacking each other.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
For each board size \(k = 1, 2, \ldots, n\), count the number of unordered placements of two knights on a \(k \times k\) chessboard such that they do not attack each other.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Start with the total number of ways to choose two squares: \[ \binom{k^2}{2} = \frac{k^2(k^2 - 1)}{2}. \]
Now subtract the bad placements where the two knights attack each other.
An attacking knight pair must occupy opposite corners of a \(2 \times 3\) or \(3 \times 2\) rectangle. On a \(k \times k\) board there are \[ (k - 1)(k - 2) \] positions for each orientation, and each rectangle contributes \(2\) attacking placements. Since there are two orientations, the number of attacking pairs is \[ 4(k - 1)(k - 2). \]
So the final answer is \[ \frac{k^2(k^2 - 1)}{2} - 4(k - 1)(k - 2). \]
There is no need for backtracking or board simulation once that counting argument is in place.
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n)\)
Memory: \(O(1)\)
C++ Solution
The exact repository source used for this solution page.
#include <cstdint>
#include <iostream>
int main() {
std::int64_t n;
std::cin >> n;
for (std::int64_t k = 1; k <= n; ++k) {
const std::int64_t squares = k * k;
const std::int64_t total_pairs = squares * (squares - 1) / 2;
const std::int64_t attacking_pairs = 4 * (k - 1) * (k - 2);
std::cout << total_pairs - attacking_pairs << '\n';
}
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Print the answer for every board size independently. The formula also works for the small cases \(k = 1\) and \(k = 2\).
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.