Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### codeworrior's blog

By codeworrior, 13 years ago, in how many ways is it possible to place z identical rooks on a chessboard of dimension x*y such that every cell in the chessboard is threatened by at least one rook ??
plzz explain how to solve this problem??  Comments (19)
| Write comment?
 > i can solve it when all the rooks are considered of different colorThen just divide this number by z!, since now you can rearrange the rooks and still get the same configuration.
 It depends on the complexity do you need)
 If z>xy or z inclusion-exclusionAi - set of ways of placing z identical rooks on a x*y chessboard knowing that i is missing where i is a column or rowWe have |Ai1 * Ai2 * ... * Ain| = \binom{xy-ky-(n-k)x+k(n-k)}{z}, where k is the number of elements from {i1,...,in} that are rows with k in {0, ..., n} and n in {1,...,x+y} and "*" stand for intersection and \binom{x}{y}(binomial number) is x!/(y!(x-y)!) and if x is 0 or negative then \binom{x}{y} is 0;The answer is A=\binom{xy}{z}-SandS=sumi=1 x+y sumk=0 i(H(i,k))H(i,k)=\binom{x}{k} \binom{y}{i-k}\binom{xy-ky-(i-k)x+k(i-k)}{z}Hope the writing is understandable - I didn't find good tools of writing such formulas hereH(i,k) can be taken from a precomputed table.Precomputation can be done using O(n2) aditional memory and O(n2) using Pascal identity.Then follow O(n2) summations. Hope I'm not wrong. Even if I'm wrong the idea can be used - I believe so.If you get BigInts I think it can be done in O(n3) if this is O(n2) as claimed
 If anyone can check if my dinamic formula is correct, please do:d[x][y][z]-your answerd[x][y][z]=sum{i=1}{x}{d[x][y-1][z-i]*binom{x}{y}}+sum{i=0}{x-1}{x*d[x-1][y-1][z-1-i]*binom{x-1}{i}}d=1d[x][y][z]=0, x<1 or y < 1 or z < 1As it looks this algo is O(n4) but I'm thinking if some tricks might be used to reduce the complexity.
 I think there is a solution with O(1) complexity.We have k rooks and n*m board.Consider, we have not n*m but n*k board.Than the answer is n·(n - 1)·...·(n - k + 1).Now all we need is to select k rows from given m rows in all ways: m! / k!·(m - k)!
•  Why is this correct? I mean, I don't understand why in all configurations all cells will be covered at least once.
•  When we have only k rows, not m, this means we must occupy each row. First row we can occupy in any of n columns. Second - in any of n colums, except the column, selected on the previous step - (n - 1) and so on.Now we have m rows. So let's just select k that we will use and keep other rows empty. It can be done in CMK ways.
•  I repeat. If the answer is not 0 then k>=n and k>=m. So you cannot do it like you say. There will be at least one column with more than one rooks.
•  It is not correct. If k>n*m or k < max(n,m) the answer is 0. But the idea can be adjusted. Suppose the answer is not 0. Then k >=n and k >=m. By considering an n*k board we will not get the answer n*(n-1)*...*(n-k+1)
•  Cut out "But the idea can be adjusted. I don't know how.
•  If k > n OR k > m answer is 0.And if k <= min(m, n) my formulas should work.
•  Have you read the problem statement? Do you know what a rook is? We need our rooks to attack all positions on the chess table and we need at least max(n,m) rooks to do that.
•  Oh. Sorry. I made a mistake.
•  "If k>n or k>m answer is 0."A simple example to prove you wrong. The board is n*m and the number z of rooks is n*m. Then by simply filling the chessboard with rooks we get the single solution.
 Well... Not O(1) because we cannot calculate this factorials fast.But we can used Pascal's triangle to calc CMK
 Ok. I think I got it.First of all if k <= x answer is 0.Second of all ; ) to cover all spots we must place one rook either on each row or on each column. Why? Consider that we have column i and row j without rook - than place (i, j) is unattacked. Proved.So let's assume we are going to cover all x rows.Let's use dynamic programming. This is pseudocode.http://pastie.org/1150933After we should switch x and y and repeat.Solution for O(n3).
•  I am sorryI the second row k <= x --> k < min(x, y)
 The answer is: where •  Sorry, in the first formula above, n should be x, m is y and r is z.