The number of connected components depends on the number of cycles. It can be proved that there exist only cycles between 2 vertices. Hence, we can reduce the problem into calculating the expected number of cycles between 2 vertices.

A connected component as a directed graph always consists of cycle of size two and some vertices hanging on the cycle vertices as trees. Therefore number of components is equal to the number of cycles of size two.

Expectation of this value is equal to sum of probabilities for every two empty cells of grid to form a 2-cycle. Two points form a 2-cycle iff no point is closer to the first point than the second, and vice versa; so, all points must lie outside some set. The probability for this is C_s^r - 2 / C_p^r, where s is size of the set, p is number of empty cells.

I think so too. If you had implemented it, you'd see that the time limit was very tight.

Yes, there were not enough time for me to make one simple optimization. And that's why my solution failed during contest

But in SRM 635 you was able to earn 0 points but increase your rating, that looks strange :o

• Binary search the lower bound of the minimum sum of the 16 sub-rectangles
• brute force the 3 vertical cuts
• greedily pick the horizontal cuts in order to exceed the lower bound
• total complexity O(n^4 log n) .. using pre-calculated partial 2D sums