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??
plzz explain how to solve this problem??
Then just divide this number by z!, since now you can rearrange the rooks and still get the same configuration.
Otherwise => inclusion-exclusion
Ai - set of ways of placing z identical rooks on a x*y chessboard knowing that i is missing where i is a column or row
We 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}-S
and
S=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 here
H(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
d[x][y][z]-your answer
d[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]=1
d[x][y][z]=0, x<1 or y < 1 or z < 1
As 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)!
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.
If k > n OR k > m answer is 0.
And if k <= min(m, n) my formulas should work.
Oh. Sorry. I made a mistake.
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/1150933
After we should switch x and y and repeat.
Solution for O(n3).
I am sorry
I the second row k <= x --> k < min(x, y)
First of all if k < min(x, y) 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 row i and column 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. Here is C++/pseudocode.
http://pastie.org/1150933
After we should switch x and y and repeat.
Solution for O(n3)
The answer is:
where