Тури#12974

Тури (Розбір)

Author:

Anton Trygub

Solved by:

First to solve:

N/A

The key idea is to try to characterize all good placements of rooks. It turns out they all have to lie on a rhombus of some sort. Note that the condition on all Manhattan distances being at most is equivalent to the following:

Note that it follows that A+B \leq 2x = (x-y)+(x+y) \leq A+B+2n for any rook , so \frac{A+B}{2} \leq x \leq \frac{A+B}{2}+n. Since can be any number, we get

\frac{A+B}{2}\leq 1, \frac{A+B}{2}+n \geq n \implies 0 \leq \frac{A+B}{2} \leq 1 \implies 0 \leq A+B \leq 2

Similarly, we know that (B-A)-n \leq 2y = (x+y)-(x-y) \leq (B-A)+n \implies \frac{B-A}{2} - \frac{n}{2} \leq y \leq \frac{B-A}{2}+\frac{n}{2} for any rook . Once again, it follows that

\frac{B-A}{2} - \frac{n}{2} \leq 1, \frac{B-A}{2}+\frac{n}{2} \geq n \implies \frac{n}{2} \leq \frac{B-A}{2} \leq \frac{n}{2} + 1 \implies n \leq B-A \leq n+2

Consider the case of odd n = 2k+1 first. Then there are cases: (A, B) \in \{(-k-1, k+1), (-k, k+1), (-k-1, k+2), (-k, k+2)\}. Each of these cases is basically defining some rhombus inside which every rook has to be; all of them are symmetric in the sense that they can be obtained by rotating the board by 90^\circ. So, we will count the number of configurations working for the case (A, B) = (-k-1, k+1), and for other cases just rotate the board.

From (A, B) = (-k-1, k+1) it follows that for rook we have

-k-1 \leq n - y \leq -k-1+n, k+1 \leq n+y \leq k+1+n \implies k+1 \leq y \leq k+1 \implies y = k+1

So, there definitely has to be a rook at (n, k+1): at the middle of the bottom column. It’s not hard to deduce where other rooks have to be.

Now it’s not hard to fill where the remaining rooks will be. Consider, for example, columns and . From current constraints, it’s easy to see that corresponding rooks in them have to be in rows or k+1. So, it’s either \{(k, 1), (k+1, n)\} or \{(k+1, 1), (k, n)\}. Then we can look at columns 2, n-1, and deduce that it’s either \{(k-1, 2), (k+2, n-1)\} or \{(k+2, 2), (k-1, n-1)\}, and so on: all other rooks are split into pairs, for each of which there are two placement choices. We can easily find the number of placements that satisfy already placed rooks.

However, we need to be careful to not double count any configurations. Fortunately, there are only of them that satisfy two choices of : one where rooks are placed at

\{(1, k+1), (2, k), (3, k-1), \ldots, (k+1, 1), (k+2, n), (k+3, n-1), \ldots, (n, k+1)\}

And its rotations. So just subtract whichever of these placements satisfy already placed rooks.

Runtime .

The analysis for the case of even n = 2k is similar. Once again, there are cases for :

\{(-k, k), (-k, k+2), (-k-1, k+1), (-k+1, k+1), (-k, k+1)\}

Here the first four are also rotations as each other, and the last one is a bit different.

The base configuration for the first looks as follows: there are two rooks at cells (1, k+1), (k+1, 1), and for 2 \leq i \leq k there are two rooks at \{(i, k+2-i), (2k+2-i, k+i-2)\} or at \{(i, k+i-2), (2k+2-i, k+2-i)\}. Once again, iterate over these rotations.

(-k, k+1) corresponds to the following:

For every 1 \leq i \leq k, there are two rooks at \{(i, k+1-i), (2k+1-i, k+i)\} or at \{(i, k-i), (2k+1-i, k+1-i)\}.

Once again, we need to avoid double counting. In this case, configurations that might be double counted are of form:

\{(1, k), (2, k-1), (3, k-2), \ldots, (k, 1), (k+1, n), (k+2, n-1), \ldots, (n, k+1)\}

And their rotations.

Runtime .