Solve Knight and Reversal Problems

The online assessment contained two coding problems:

1. Generalized knight shortest path: Given an integer n, consider an n x n chessboard with coordinates from (0, 0) to (n-1, n-1). For each ordered pair of positive integers (a, b) where 1 <= a, b < n, a piece can move from (x, y) to any of the eight positions formed by applying (+/-a, +/-b) or (+/-b, +/-a). For every (a, b), compute the minimum number of moves needed to reach (n-1, n-1) starting from (0, 0), or -1 if the target is unreachable.

2. Minimum segment reversals: Positions are numbered from 1 to n. A token starts at position p, and some positions are forbidden and cannot be occupied. In one move, you may choose any contiguous segment of length k that contains the token, reverse that segment, and the token moves to its mirrored position inside the chosen segment. For every position from 1 to n, compute the minimum number of reversals required to move the token there, or -1 if it cannot be reached. The assessment version used 1-indexed positions.

Part 1: Generalized Knight Distance Matrix

Given an integer n, consider an n x n chessboard with cells labeled from (0, 0) to (n-1, n-1). For each ordered pair of positive integers (a, b) such that 1 <= a, b < n, a piece may move from (x, y) to any of the eight cells obtained by adding (+/-a, +/-b) or (+/-b, +/-a). Return an (n-1) x (n-1) matrix where the value at row a-1 and column b-1 is the minimum number of moves needed to reach (n-1, n-1) starting from (0, 0). If the target cannot be reached for that (a, b), store -1 instead.

Constraints

• 1 <= n <= 25
• Coordinates are 0-indexed from (0, 0) to (n-1, n-1)
• For every pair (a, b), 1 <= a, b < n

Examples

Example 1

Input: (1,)
Output: []

Explanation: There are no valid pairs (a, b) when n = 1, so the result is an empty matrix.

Example 2

Input: (2,)
Output: [[1]]

Explanation: Only (a, b) = (1, 1) exists, and the piece reaches (1, 1) in one move.

Hints

1. For a fixed (a, b), this is an unweighted shortest-path problem on a grid graph, so BFS gives the minimum number of moves.
2. The move set for (a, b) is identical to the move set for (b, a), so you can compute one and mirror the answer.

Part 2: Minimum Reversal Moves with Forbidden Positions

Positions are numbered from 1 to n. A token starts at position p, and some positions are forbidden and can never be occupied. In one move, you may choose any contiguous segment of length k that contains the token, reverse that segment, and the token moves to its mirrored position inside the chosen segment. For every position from 1 to n, compute the minimum number of reversals needed to move the token there, or -1 if it is impossible. The input uses 1-indexed positions.

Constraints

• 1 <= n <= 200000
• 1 <= p <= n
• 1 <= k <= n
• 0 <= len(banned) < n
• All values in banned are distinct
• The starting position p is not forbidden

Examples

Example 1

Input: (1, 1, [], 1)
Output: [0]

Explanation: Only one position exists, so the token is already at the answer with distance 0.

Example 2

Input: (5, 4, [2], 1)
Output: [-1, -1, -1, 0, -1]

Explanation: A reversal of length 1 changes nothing, so only the starting position is reachable.

Hints

1. If the token is at 0-indexed position i and you reverse a segment [l, l+k-1], its new position becomes 2*l + k - 1 - i.
2. For a fixed current position, all next positions lie in one interval and all have the same parity. BFS is still the right idea, but you need a fast way to skip already-used positions of each parity.