PROBLEM LINK:
Author: Alex Gu
Tester: Istvan Nagy
Editorialist: Xellos
DIFFICULTY:
Easy
PREREQUISITES:
Probability and expected values
PROBLEM:
You’re given an N\times M matrix; some of its cells contain 1-s, other cells contain zeroes. Compute the expected sum of values inside a randomly chosen submatrix.
SHORT EXPLANATION:
Use the linearity of expectation - transform the problem into counting submatrices which contain a cell.
EXPLANATION:
The key observation in a lot of expected value problems is the fact that the expected value is linear - instead of computing the expected value of a sum, we can compute a corresponding sum of expected values.
In this case, the “sum” is the number of hearts in all fields of a chosen submatrix (rectangle). Instead of computing that sum for all possible submatrices, we’ll compute - for each heart - the expected number of submatrices which contain that heart, which is just the number of submatrices which contain it divided by the number of all possible submatrices. The answer is the sum of those values.
This is quite easy. A submatrix is given by the x-coordinates of its left and right side (x_l and x_r) and y-coordinates of its top and bottom side (y_t and y_b); the x-coordinates here can be from the interval of [0,N] and the y-coordinates from [0,M], since each side of a submatrix can be between cells or on a side of the whole matrix.
The only general constraints for them are 0 \le x_l < x_r \le N and 0 \le y_t < y_b \le M, (we don’t mislabel the right/left or bottom/top side and the submatrix isn’t empty), so the total number of submatrices can be computed as the product of the number of pairs (x_l,x_r) and the number of pairs (y_t,y_b) which satisfy the constraints. That’s
since for each x_l, we have N-x_l valid choices of x_r and for each y_t, M-y_t choices of y_b, so the number of x-pairs is \sum_{x_l=0}^N N-x_l = \sum_{i=0}^N i for i=N-x_l; similarly for y-pairs.
If we want to count the number of submatrices containing a cell (x,y), we have further constraints x_l < x \le x_r, y_t < y \le y_b (we’ll keep indexing the cells from 1, so the left side of a cell (x,y) has x-coordinate x-1 and the top side has y-coordinate y-1) - the left side of the submatrix mustn’t be to the right of the left side of our cell, the right side of the submatrix mustn’t be to the left of the right side of our cell, etc. The number of such submatrices is
since we have x choices of x_l, N+1-x choices of x_r (in the range [x,N]), y choices of y_t and M+1-y choices of y_b.
So the only thing we have to do is compute the sum of \frac{G(x,y)}{Z} for all cells (x,y) which contain a heart. It can be computed in time O(1) and there are just K such cells, so the time complexity is O(K) per test case. Memory: O(1).
Watch out, Z and G() don’t fit even into 64-bit integers; it’s better to compute \frac{G(x,y)}{Z} in doubles as a product of fractions: 4\frac{x}{N}\frac{N+1-x}{N+1}\frac{y}{M}\frac{M+1-y}{M+1}.