A note about the constraints
Constraints indicate us that the maximum width and height will be 21. There is another constraint though: The maximum total number of cells is 150. This can help us because it means that the smaller dimension will be at most 12. 13 x 12 > 150. Since rows and columns behave in the same way in this problem, we can just assume that the width is always the smallest dimension - In case it is not, we can just rotate the board. From now on assume that `(1 <= w <= 12)` and `(w <= h <= 21)` are the width and height of the board, respectively.
A sum of probabilities
The expected value of the necessary number of steps is:
\[ \begin{align*} E(\text{number of steps}) = \sum_{i=0}^\infty {i P(\text{i steps are needed}) } \end{align*} \]
We can think of many ways to find the probability that i steps are needed. This time it is convenient to think of the probability that the objective (at least one cell in each row/column is painted) is not fulfilled after i steps. Then you can tell, if the objective was not fulfilled after i-1 steps, but it is fulfilled after i steps, then exactly i steps were needed. The following is a way to develop a formula to solve the problem after finding this conclusion:
\[ \begin{align*} P\left(\text{i steps are needed}\right) &= P\left(\text{Not done after i-1 steps}\right) - P\left(\text{Not done after i}\right) \\ E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty {\left(i \left( P\left(\text{Not done after i-1 steps}\right) - P\left(\mbox{Not done after i}\right) \right) \right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty {\left(i P\left(\text{Not done after i-1 steps}\right) - i P\left(\text{Not done after i}\right) \right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty {i P\left(\text{Not done after i-1 steps}\right)} - \sum_{i=0}^\infty {i P\left(\text{Not done after i steps}\right)} \\ E\left(\text{number of steps}\right) &= 0 * P\left(\text{Not done after -1 steps}\right) + \sum_{i=1}^\infty {i P\left(\text{Not done after i-1 steps}\right)} \\ &- \sum_{i=1}^\infty {\left(i - 1\right) P\left(\text{Not done after i-1 steps}\right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=1}^\infty {\left(i P\left(\text{Not done after i-1 steps}\right) - \left(i-1\right) P\left(\text{Not done after i-1 steps}\right) \right)} \\ E\left(\text{number of steps}\right) &= \sum_{i=1}^\infty {P\left(\text{Not done after i-1 steps}\right)} \\ E\left(\text{number of steps}\right) &= P\left(\text{Not done after 0 steps}\right) + P\left(\text{Not done after 1 step}\right) + P\left(\text{Not done after 2 steps}\right) + … \end{align*} \]
With some changes, we have:
\[ \begin{equation*} \tag{1} E\left(\text{number of steps}\right) = \sum_{i=0}^\infty {P\left(\text{Not done after i steps}\right)} \\ \end{equation*} \]
Let us try to find probabilities that the objective is not done after i steps.
Inclusion-exclusion
We can see that probability as the probability that, after i steps, at least one row or column is not painted.
It is possible to calculate the probability each single row is painted or not after \(i\) steps. Let \(s\) be the probability we pick the row (or column) in a single step. The probability we do not ever pick it after \(i\) steps is \( \left( 1 - s \right)^i \). We can add these probabilities together for each column or row. However ,we would be double-counting any situation in which there are two rows, two columns or a row and a column that are not painted after \(i\) steps. We can calculate, for each pair of two columns or rows, the probability \(t\) either of them are picked in a single step. The probabilities \( \left(1-t\right)^i \) are now the probability that neither of the two columns/rows/(column and row) will be picked after two steps, so we can subtract them from the original sum. But we would be subtracting some cases more times than necessary - The cases in which there are 3 or more columns or rows that are not painted. In short, we can use the inclusion-exclusion principle:
\[ \begin{align*} P\left(\text{Not done after } i \text{ steps}\right) &= \sum_{ x \in \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P(x) \right)^i } \\ &- \sum_{ \left\{x_0,x_1\right\} \subseteq \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P\left\{x_0,x_1\right\} \right)^i } \\ &+ \sum_{ \left\{x_0,x_1,x_2\right\} \subseteq \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P\left\{x_0,x_1,x_2\right\} \right)^i } \\ &- \sum_{ \left\{x_0,x_1,x_2,x_3\right\} \subseteq \left( \text{rows } \cup \text{ columns} \right) } { \left(1 - P\left\{x_0,x_1,x_2,x_3\right\} \right)^i } \\ &+ … \\ \\ \tag{2} P\left(\text{Not done after } i \text{ steps}\right) &= \sum_{ s \subseteq \left( \text{rows } \cup \text{ columns} \right) , \left|s\right| \text{ is odd} } \left( 1 - P\left(s\right) \right) ^ i \\ &- \sum_{ s \subseteq \left( \text{rows } \cup \text{ columns} \right) , \left|s\right| \text{ is even} } \left( 1 - P\left(s\right) \right) ^ i \end{align*} \]
For each subset \(s\) of rows and columns, we calculate its probability \( P\left(s\right) \) that any of the rows and columns are picked in a single step. Then we subtract or add \( \left( 1 - P\left(s\right) \right)^i \) to the total, depending on the parity of the number of elements in the set.
Putting it together
Combining equations \( (1) \) and \( (2) \) together:
\[ \begin{align*} E\left(\text{number of steps}\right) &= \sum_{i=0}^\infty { \left( \sum_{\text{odd }s } {\left( 1 - P\left(s\right) \right) ^ i} - \sum_{\text{even }s}{\left( 1 - P\left(s\right) \right) ^ i} \right)} \\ E\left(\text{number of steps}\right) &= \sum_{\text{odd }s } {\left( \sum_{i=0}^\infty \left( 1 - P\left(s\right) \right) ^ i \right) } - \sum_{\text{even }s}{\left( \sum_{i=0}^\infty \left( 1 - P\left(s\right) \right) ^ i \right)} \end{align*} \]
The last trick we used was to distribute the outer summations inside the inner summations. For each set \(s\) of columns and rows, we just need to calculate \( \left( 1 - P\left(s\right) \right) ^ i \). Depending on the number of elements in the set, we add or subtract the resulting value from the total.
Let us find \( \left( 1 - P\left(s\right) \right) \), that is the probability that none of the cells that belong to a column or row in the set are picked. Let \(x\) be the sum of the values outside the set, the probability is then : \( (x / T) \). Where \(T\) is the total sum of all the cells in the board. The sum of all \( \left( x / T \right) ^ i \) is the sum of a geometric progression. Therefore:
\[ \sum_{i=0}^\infty \left( \frac{x}{T} \right)^i = \frac{T}{T - x} \]
For each set of columns and rows with a sum of cells outside it equal to \( x \), if the number of elements of the set is odd then add \( \frac{T}{T - x} \) else subtract \( \frac{T}{T - x} \). That is our result. Note that when \( x = T \), the formula is invalid. This can only happen if the set cannot be picked in any step, which is not true, because any row and column will always have at least one non-zero cell.
Count the sets
Since the value that is added/subtracted to the result depends only on \( x \), the sum of the cells outside the set, we can just count the number of even and odd sets for each value of \( x \). In fact, the result is to just multiply (number of odd sets for \(x\)) - (number of even sets for \(x\)) and \( \frac{x}{T - x} \) together. So we only need to find the total subtraction between the number of odd and even sets for each \( x \).
The sum \( (w + h) \) can be as large as 140, so the number of subsets of rows and columns can be insanely high. Remember though that \(w \leq 12\), so the number of sets of columns is not going to be very high. Assume that the set of columns included in the set \( s \)is already fixed, so we only need to decide which rows to add. If we decide to include the i-th column, then we already know the total sum of the cells outside the set - It is equal to the cells in the i-th row that do not belong to any of the picked columns. We can pre-calculate this sum after picking the set of columns.
Dynamic programming
Let mask be the fixed subset of columns. We precalculate \( b_i \), for each row \( i \), as the sum of the cells not included in any of the picked columns. Find the subtraction (number of odd sets) - (number of even sets) that is possible for every value \(x\) of the sum of cells outside sets of columns and rows that already include mask. Let \( f(i, x) \) be a function that solves this problem for the first \(i\) columns. If the \(i\)-th column is added then \(x\) remains the way it is, and the parity of the number of elements in the set changes. If \(i\)-th column is not added, \(x \) is increased by \(b_i\) and the parity does not change. From this we can make a dynamic programming solution. For each \( f(i, x) \), subtract \(f(i,x)\) from \(f(i+1,x)\) and add \( f(i,x) \) to \( f(i+1,x + b_i ) \). The base case is \( f(0,0) \) which is equal to -1 (If the number of columns in mask is even) or 1 (If the number of elements in mask is odd). After running this dynamic programming approach, we can accumulate the values we have found for each \(x\) given the mask.
For a complexity analysis, we repeat a \( O\left( h \times T \right) \) dynamic programming approach for \( O\left(2 ^ w \right) \) subsets of columns. In total, \( O\left(2^w \times h \times T \right) \). Remember that \( w \leq 12 \) and by constraints \(T \leq 1350\), so this solution can run comfortably under 2 seconds in TopCoder’s servers.