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??
• 0

| Write comment?
 13 years ago, # |   0 > 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.
 13 years ago, # |   0 It depends on the complexity do you need)
 13 years ago, # |   0 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
 13 years ago, # |   0 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[1][1][1]=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.
 13 years ago, # |   0 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)!
•  13 years ago, # ^ |   0 Why is this correct? I mean, I don't understand why in all configurations all cells will be covered at least once.
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 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)
•  13 years ago, # ^ |   0 Cut out "But the idea can be adjusted. I don't know how.
•  13 years ago, # ^ |   0 If k > n OR k > m answer is 0.And if k <= min(m, n) my formulas should work.
•  13 years ago, # ^ |   0 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.
•  13 years ago, # ^ |   0 Oh. Sorry. I made a mistake.
•  13 years ago, # ^ |   0 "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.
 13 years ago, # |   0 Well... Not O(1) because we cannot calculate this factorials fast.But we can used Pascal's triangle to calc CMK
 13 years ago, # |   0 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).
•  13 years ago, # ^ |   0 I am sorryI the second row k <= x --> k < min(x, y)
 13 years ago, # |   0 The answer is: where
•  13 years ago, # ^ |   0 Sorry, in the first formula above, n should be x, m is y and r is z.