SUSROOKS - Editorial

editorial
, , , , , ,
1

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

MEDIUM

PREREQUISITES:

Combinatorics, Inclusion Exclusion, FFT/NTT

PROBLEM:

Given two positive integers N and M. Let S be the set of all binary grids of dimensions N*M, where the coordinates of the 1's in the grid are strictly increasing.

Let f(T) represent the number of ways to place rooks in the grid T such that, the rooks are non-attacking and no rook is placed in a cell with value 1.

Determine \sum f(t)\mod{998244353}, where t\in S.

EXPLANATION:

It is immediately obvious that the coordinates of the 1's in each of the generated grids are strictly increasing. Hence, each grid has atmost one 1-valued cell in each row/column.

Let P=\min(N,M). It is also obvious that the maximum number of rooks over all valid arrangements is equal to P.

Hint 1

Start by finding the number of valid ways to place rooks in a N*M grid consisting of 0's only.

Solution

Since there are no unavailable cells in the grid, we are only concerned with finding the number of different placements such that no two rooks are attacking. This is a classical problem, whose solution can be represented by the formula:

\sum_{i=0}^{P} {N\choose i}\cdot{M\choose i}\cdot i!

In brief, we count the number of ways to place exactly i rooks (summed over all valid i), by selecting i distinct X and Y coordinates and calculating the number of different sets of coordinates that can be created by pairing these values.

Hint 2

Now solve for when there is exactly one 1-valued cell in the grid. A little intuition tells us that the answer is unaffected by the coordinates of the 1-valued cell(s).

Solution

Subtracting the number of ways to place non-attacking rooks where one rook is placed on the 1-valued cell from the total number of ways to place non-attacking rooks, gives us the desired answer.

How do we calculate the former mentioned value?

The number of ways to place non-attacking rooks on a N*M grid, with the position of one rook fixed, is equivalent to the number of ways to place non-attacking rooks on a (N-1)\cdot(M-1) sized grid (Why?)

More formally, let W_i represent the number of ways to place non-attacking rooks on a grid of size (N-i)\cdot(M-i). Then, the answer to the above question is equal to

W_0-W_1

Can you extend this to solve for when there are i\ (1\le i\le P) 1-valued cells?

Solution

Standard application of inclusion-exclusion.

The answer is equal to (derivation is mundane and left to the reader as an exercise):

{i\choose 0}W_0-{i\choose 1}W_1+{i\choose 2}W_2-\dots+{i\choose i}W_i
Hint 3

So far, we’ve derived a method to determine the number of ways we can place rooks when there are exactly 1\le i\le P cells with value 1. Call this value Q_i.

Then, if K_i represents the number of valid grids with exactly i 1-valued cells, the answer to the problem is equal to:

\sum_{i=0}^{P} K_i\cdot Q_i

How will you calculate array K?

Solution

By our initial observation (mentioned at the start), the following equation is trivially derivable:

K_i= {N\choose i}\cdot{M\choose i}

However, we are not done yet. The time complexity of the described solution is O(P^2), which will TLE in the final subtask. Clearly, we need to optimise!

Analysis (optional, but recommended)

We summarise our progress, along with the time complexity of our approach.

K_i represents the number of valid grids with exactly i, 1-valued cells.

K_i= {N\choose i}\cdot{M\choose i}

which can be calculated in O(P) with suitable pre computations.

W_i represents the number of ways to place non-attacking rooks on a grid of size (N-i)\cdot(M-i).

W_i=\sum_{k=0}^{P-i} {N-i\choose k}\cdot{M-i\choose k}\cdot k!

and can be computed naively in O(P^2) time.

Q_i represents the number of ways we can place rooks when there are exactly i cells with value 1.

Q_i=\sum_{x=0}^{i} (-1)^x{i\choose x}W_x

that similarly has an O(P^2) time complexity.

The final answer is then -

\sum K_i\cdot Q_i

The total time complexity is therefore:

O(P+P^2+P^2+P)\approx O(P^2)
Hint 4

A huge part of our algorithm is devoted to multiplying and summing the values of different arrays (implicitly). This just screams FFT/NTT.

Can you rewrite the above equations to utilise the power of FFT?

Solution

Let’s start with efficiently calculating array W.

\begin{aligned} W_i &= \sum_{k=0}^{P-i} {N-i\choose k}\cdot{M-i\choose k}\cdot k!\\ &= (N-i)!\cdot(M-i)!\cdot\sum_{k=0}^{P-i}\frac{1}{k!\cdot(N-i-k)!\cdot(M-i-k)!} \end{aligned}

Now, the summation of the products (last term of the equation) can be calculated at once over all i using FFT.

What are the coefficients of the polynomials to multiply

A=[P!,(P-1)!,\dots,0!] and B=[N!\cdot M!, (N-1)!\cdot (M-1)!, \dots, (N-P)!\cdot (M-P)!]. Let C be the coefficients after multiplying A and B.

Then W_i can be rewritten as:

W_i=(N-i)!\cdot(M-i)!\cdot\frac{1}{C_{P-i}}

Which can be computed in O(P\log P + P) overall time complexity.

Similarly, we can rewrite Q_i and apply FFT on it. Deriving the suitable formula is left to the reader as an exercise (you may have to simplify \sum K_i\cdot Q_i and then apply FFT, which is what my solution does). Refer my (well written) code for help.

TIME COMPLEXITY:

Computing array K takes O(P). Computing array W takes O(P\log P+P). Calculating the final solution takes O(P\log P+P). The final time complexity is therefore:

O(P\log P)

SOLUTIONS:

Editorialist’s solution can be found here.
Author’s solution can be found here.
Tester’s solution can be found here.

3 Likes
2

There is an error in the final part of solution:
The actual formula for Wi should be:
Wi = (N-i)! * (M-i)! *(1/C_{p-i})
In the editorial (1/C_{p+i}) is written.

1 Like
3

Thanks, fixed.