Problem Link:
Difficulty:
Medium
Pre-requisites:
Combinatorics
Problem:
You are given a RxC chess board, on which you have to place N rooks. The board is numbered 1 to R from top to bottom and 1 to C from left to right. Rooks can be placed in such a way that there are more than one rook on each square. However, the squares in which the rooks are placed should be non-decreasing in both row-coordinate as well as column-coordinate. Your friend then tries to move rooks left and up such that at the end of his moves, no two rooks attack each other. Also, at the end of your friend’s moves, the rooks should be placed in cells that are non-decreasing in both row as well as column coordinates. In how many ways can you place the rooks initially so that you ensure that your friend CANNOT make these moves.
Explanation:
Let us try to find ways to ensure we win. Firstly, if there are too many rooks in the early rows and columns, we win. Notice that if we had 2 rooks in the first row, then those two rooks would definitely attack each other. Similarly if we had two rooks in the first column.
If we try to place rooks from top-left to bottom-right, and ask, if the first cell we place rooks is (i, j), then we definitely win by placing more than min(i, j) rooks there. One may be tempted to break up the problem into an (R-i)x(C-j) chessboard, but this is not necessarily right, as in the following example:
.....
.....
..1..
.....
....4
There, if we look carefully, we can move that board to
1....
.1...
..1..
...1.
....1
but if we were to break up the problem into the first 3x3, and the remaining 3x3, we would get that we would ensure our opponent can’t win by placing four rooks at the final corner.
This is because, by placing just 1 rook at position (3, 3), there is actually considerable slack in the first 3x3 part of the board, into which further rooks can be placed.
Our condition for losing should then look as:
sum of rooks in the first i rows <= i, 1 <= i <= R,
sum of rooks in the first i cols <= i, 1 <= i <= C.
If either condition of the above is violated, then we would definitely win, since our opponent would be unable to ensure that those i rows (or cols) can have rooks not attack each other.
Further, if those conditions are met, then our opponent can definitely ensure that he places the rooks on the main diagonal and he would win.
Thus, we need to find how many ways are there of placing N rooks such that the total number of rooks in the first i rows and the first i cols <= i, for all i.
In order to count this, we ask two questions:
(1) What is the total number of ways of placing N rooks on the board satisfying that the rooks are placed in cells that are non-decreasing in row and column coordinates?
(2) How many ways can we place N rooks on the board satisfying the first i rows and the first i columns have <= i rooks?
Bijection between placing rooks on the board and counting the number of rooks per row/column
The need to answer the second question yields the following scheme of encoding the board:
Let r[i] = Number of rooks in row i, and
c[i] = Number of rooks in col i.
Claim: Given values r[1], r[2], …, r[R], and c[1], c[2], …, c[C], such that sum of r-values and sum of c-values are both N, and r[i], c[i] >= 0, there is a unique way to fill in the board such that the number of rooks in the i’th row is r[i], and the number of rooks in the i’th col is c[i].
Once we are given these values, let i0 be the first nonzero value in r, and j0 be the first nonzero value in c. Then, if I want the number of rooks in the i’th row and j’th column to be r[i] and c[j] respectively, I need to place min(r[i0], c[j0]) rooks in cell (i0, j0). If I don’t, then some rook will have to be below (i0, j0), and some rook will have to be to the right of (i0, j0), thus contradicting that the positions of the rooks will be in nondecreasing order of row/col-coordinates.
Once I have placed min(r[i0], c[j0]) rooks in cell (i0, j0), I just subtract that value from r[i0], c[j0], and repeat the process (note that now, atleast one of r[i0], c[j0] would have become 0). This will ensure that I have placed exactly r[i] rooks in row i, and exactly c[j] rooks in col j for all 1 <= i <= R and 1 <= j <= C.
This gives us a bijection from the set of placements of rooks on the board to the number of arrays (r, c) satisfying sum of values in r and in c = N each.
The total solutions to “number of nonnegative arrays A, having M elements, whose sum is N” = Comb(N + M - 1, N), where Comb(a, b) is “a choose b”. Thus, the total number of ways of placing rooks onto the board is Comb(R + N - 1, N) * Comb(C + N - 1, N).
Finding number of losing positions for us
A losing position, as we have seen earlier, is where sum of values of r for the first i entries is <= i, and sum of values of c for the first i entries is <= i. Clearly, if N > min(R, C), one of those two would be violated for the last row/column, and hence the number of losing positions would be 0. Thus, we only consider N <= min(R, C).
That motivates the question: “Given an array A of M entries, whose entries are nonnegative and sum to N, how many ways are there of filling in this array with the added constraint that the sum of the first i entries <= i?” If we answer this question, we just need to substitute values of R or C in the above parameter “M”.
Thus, let us go about solving the above.
Let y[i] = sum of first i entries of A. We need y[1] <= 1, y[2] <= 2, …, y[M] = N <= M, and y[i] >= y[i-1]. If we were to plot the y’s on a grid, and consider y[i] values as “corners” along a “path from (0, 0) to (M, N)”, we would get the following question: “How many paths are there from (0, 0) to (M, N) taking only right and upward moves, and not crossing the y=x line?”
Without the constraint of ensuring y[i] <= i, we would have that the number of paths from (0, 0) to (M, N) taking only right and up moves is Comb(M+N, N).
If we were to put M = N, we would notice that we end up with the N’th Catalan number. Indeed, we go about counting our required number in a manner very much like “the reflection method” used for Catalan numbers here.
The basic idea is as follows. From the set of paths from (0, 0) to (M, N) wherein there are no constraints on crossing y=x line, we subtract those paths that actually cross the line.
In order to count how many cross the y=x line, we take the first point at which the path crosses the line. Let this be at point (i, i+1). From here, we reflect the path to (M, N) : that is, switch up-moves with right-moves and vice-versa. This leads us to the point (N-1, M+1) (See this figure for an understanding). Further, since N <= M, any path from the origin to (N-1, M+1) necessarily crosses the y=x line. And from the first point that this path has crossed the line, we can reflect it to get a path going to (M, N).
Thus, we have found a bijection between “paths from (0, 0) to (M, N) passing crossing the y=x line” with “paths from (0, 0) to (N-1, M+1)”. The latter is easy to count, and is Comb(M+N, N-1).
Thus, this finally answers our question. Comb(M+N, N) - Comb(M+N, N-1), where N <= M.
Thus, the solution to question (R, C, N) is merely:
Comb(R+N-1, N) * Comb(C+N-1, N)
- [(Comb(R+N, N) - Comb(R+N, N-1)) * (Comb(C+N, N) - Comb(C+N, N-1))].
Calculating Comb(a, b) : Lucas’ theorem
Since R, C are rather large, we cannot precompute values of Comb[a][b], nor can we perform O® or O© time computation. However, we need to find the values modulo 10007, a prime.
Using Lucas’ Theorem, we can find Comb(a, b) modulo P by writing a and b in base P, and then taking product of combination digit-wise. Under the constraints, The combination would have atmost 5 digits (in base P), and each digits’ combination would take O§ time to calculate factorials and inverse factorials.
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here