DSA sheet / Introductory
Two Knights
The problem in brief
For every board side k up to n (n up to 10 000), how many pairs of squares can hold two identical, mutually safe knights? Print the n answers, one per line.
An adapted, shortened summary (changed from the original) shared under the same licence, not a substitute for the statement. The problem is from the CSES Problem Set (Antti Laaksonen), CC BY-NC-SA 4.0. Read the official statement and submit at cses.fi/problemset/task/1072.
Try it
Tab indents; press Esc, then Tab, to leave the box. Ctrl+Enter runs.
Output
Errors
Hints
Stuck? Reveal one hint at a time. Each nudges without giving away the next.
-
Which is easier to count directly: pairs of squares that are safe, or pairs that are not?
-
Now count in the easier direction and subtract it from the total: how many ways are there to choose 2 squares out of k^2? That is a binomial coefficient you can write as a formula.
-
A knight’s attack is an L-shape, which fits inside a 2 by 3 or 3 by 2 rectangle. Each such rectangle contains exactly two attacking pairs. Count the rectangles.
-
The formula is quadratic in k for the attack count and quartic for the total. Check the largest value against 64-bit range, and in JavaScript against 2^53.
The walkthrough
Spoilers ahead: open a section only after you have given the hints a fair try.
How to think
“Count the placements where a condition does NOT hold” is a classic complement trick: total minus bad is usually easier than a direct count of good. Here the total is trivial, and the bad pairs have a clean geometric description.
To count attacking pairs, avoid enumerating positions. Ask instead which small region determines the attack. A knight at one corner of a 2 by 3 rectangle attacks the opposite corner, and each 2 by 3 (or 3 by 2) rectangle has exactly two such diagonal pairs. Every attacking pair lives in exactly one such rectangle, so the number of attacking pairs is 2 times the number of rectangles. Confirm with brute force on k up to 8 before trusting the formula.
Intuition
Choosing two squares out of k^2 gives k^2(k^2 - 1)/2 unordered pairs. Some pairs are an L-shape apart. Slide a 2 by 3 window over the board: there are (k - 1)(k - 2) positions; do the same for a 3 by 2 window. Each window contributes two attacking pairs, so the attacking pairs number 2 * 2 * (k - 1)(k - 2) = 4(k - 1)(k - 2).
Approach
- For each k from 1 to n compute total = k^2 (k^2 - 1) / 2.
- Subtract attacks = 4 (k - 1)(k - 2).
- Print each result on its own line.
Pitfalls: for k = 1 the total is 0 and the formula gives 0 - 0 = 0, so no special case is needed. For k = 10 000, k^2 = 10^8 and k^2 (k^2 - 1) is about 10^16, which exceeds the exact range of a JavaScript double, so use BigInt there. The product also needs long long in C++ and long in Java. Do the division by 2 last (the product is always even).
Complexity
O(n) time and O(n) output, with O(1) arithmetic per board size.
Solutions
Written from scratch and checked by compiling and running each one against a brute force on random inputs. Fast input/output, the way you would submit it.
Show solutions (C++17, Python 3, Java 17, Node.js)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
for (long long k = 1; k <= n; k++) {
long long s = k * k;
long long total = s * (s - 1) / 2;
long long attacks = 4 * (k - 1) * (k - 2);
printf("%lld\n", total - attacks);
}
return 0;
}import sys
def main():
n = int(sys.stdin.readline())
out = []
for k in range(1, n + 1):
s = k * k
out.append(s * (s - 1) // 2 - 4 * (k - 1) * (k - 2))
print("\n".join(map(str, out)))
main()import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine().trim());
StringBuilder sb = new StringBuilder();
for (long k = 1; k <= n; k++) {
long s = k * k;
long total = s * (s - 1) / 2;
long attacks = 4 * (k - 1) * (k - 2);
sb.append(total - attacks).append('\n');
}
System.out.print(sb);
}
}const n = Number(require('fs').readFileSync(0, 'utf8').trim());
const out = [];
for (let k = 1n; k <= BigInt(n); k++) {
// BigInt: k^2 * (k^2 - 1) reaches about 10^16, past the 2^53 exact range of doubles.
const s = k * k;
out.push(((s * (s - 1n)) / 2n - 4n * (k - 1n) * (k - 2n)).toString());
}
console.log(out.join('\n'));Problem: CSES Problem Set (Antti Laaksonen, University of Helsinki), CC BY-NC-SA 4.0. The explanations and code above are original (© Anupam Kumar).