We define \(f(h, w)\) similarly to balakrishnan_v’s editorial, i.e. the number of ways to place \(K\) cells in a \(h \times w\) grid such that the minimum bounding box is the whole grid.

In general, principle of inclusion-exclusion (PIE) can be summarized with the following steps:

1. Identify a set of “violations”, i.e. a set of rules you want to obey and specific requirements for each rule to be broken.
2. Identify a way to calculate \(F(S)\): for every subset \(S\) of possible violations, the number of ways to violate at least that subset (note that we don’t need to know how to calculate the number of ways to violate exactly that subset).
3. The number of ways to obey all rules (i.e. not commit any violations) will then equal \((\sum _ {|S| \text{ is even}}F(S)) - (\sum _ {|S| \text{ is odd}}F(S)) = \sum _ S (-1) ^ {|S|} \cdot F(S)\) (note that zero is also even)

A way to compute \(f(h, w)\) then follows from such a principle. We can identify exactly \(4\) possible violations that would cause the minimum bounding box be not the entire \(h \times w\) grid:

• The first row of the \(h \times w\) grid is empty.
• The last row of the grid is empty.
• The first column of the grid is empty.
• The last column of the grid is empty.

Let’s define \(g(h, w) = \binom {\max(0, h) \cdot \max(0, w)} {K}\) (note this is \(0\) if \(h \cdot w < K\), or if any argument is negative). Then

• \(\sum _ {|S| = 0}F(S) = g(h, w)\)
• \(\sum _ {|S| = 1}F(S) = g(h-1, w) \cdot 2 + g(h, w-1) \cdot 2\)
• \(\sum _ {|S| = 2}F(S) = g(h-1, w-1) \cdot 4 + g(h-2, w) + g(h, w-2) \)
• \(\sum _ {|S| = 3}F(S) =g(h-1, w-2) \cdot 2 + g(h-2, w-1) \cdot 2\)
• \(\sum _ {|S| = 4}F(S) =g(h-2, w-2)\)

We can then obtain \(f(h, w)\) by adding or subtracting these terms as appropriate.

The total number of ways to enclose \(K\) cells within a grid of size \(h\times w\) in the original rectangle is \(f(h, w) \cdot (H+1-h) \cdot (W+1-w)\). The final expected value is thus \(\frac {1} {g(H, W)} \sum _{h=1} ^H \sum _{w=1} ^W f(h, w) \cdot (H+1-h) \cdot (W+1-w) \cdot h \cdot w\).

Addendum: if there are \(n\) possible violations, there are \(2^n\) possible subsets of violations. In this problem, \(n\) is small enough to enumerate them all, but for other problems, we might just need to find a way to calculate \(\sum _ {|S| = x}F(S)\) quickly for all relevant \(x\), instead of calculating \(F(S)\) for each individual subset.