When you are asked to find an expected value, it is often effective to avoid directly evaluating but to find the sum of the answers over all possibilities and dividing it by the number of possibilities (and vice versa; i.e. it is sometime a good idea to find the expected value when you are asked to find the sum).

In this problem, we find the sum of scores over all the ways to paint, and then divide by the number of the ways to paint. We also use so-called “preposterous trick” to find the total sum by counting

• the number of ways of painting such that square \((a,b)\) is contained in the minimum rectangle

for all \((a,b)\) and summing them up. For convenience, let \((x_1,y_1),(x_2,y_2),\ldots\), and \((x_K,y_K)\) be the squares to paint.

Square \((a,b)\) is not contained in the minimum rectangle if and only if the squares to paint satisfy at least one of the following conditions:

• \(x_i\) is strictly less than \(a\) for all \(i\ (1\leq i\leq K)\);
• \(x_i\) is strictly greater than \(a\) for all \(i\ (1\leq i\leq K)\);
• \(y_i\) is strictly less than \(a\) for all \(i\ (1\leq i\leq K)\); or
• \(y_i\) is strictly greater than \(a\) for all \(i\ (1\leq i\leq K)\).

By applying the inclusion-exclusion principle for these conditions, one can count the number of ways of painting such that square \((a,b)\) is not contained in the minimum rectangle.

Therefore, the problem has been solved in a total of \(\mathrm{O}(HW+K)\) time, including the precomputation of finding the binomial coefficients.