GridColoring

SRM 409 · 2008-07-10 · by slex

SRM 409 · 2008-07-10 · by slex · Math

Show categories

Class Name: GridColoring

Return Type: double

Method Name: area

Arg Types: (int, int, int)

Problem Statement

Given a rectangular grid where all the cells are initially white, you perform the following procedure K times:

Select a cell from the grid at random, and call it A
Select a cell from the grid at random, and call it B
Color all the cells in the rectangle bounded by A and B

Each cell is selected at random, with uniform distribution, and each selection is independent from the other selections. It's possible that A and B correspond to the same cell.

For example, the image below shows a 5x7 grid where the selected pairs could have been (row, column):

(0,1); (3,2)
(3,6); (4,0)
(0,6); (0,5)

Resulting in a grid with 22 colored cells and 13 white cells.

You are given ints rows and cols, the dimensions of the grid. Return the expected number of colored cells after K steps.

Notes

The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

K will be between 0 and 100, inclusive.
rows will be between 1 and 1000, inclusive.
cols will be between 1 and 1000, inclusive.

Examples

1
2
1
Returns: 1.5

The grid has two cells. The probability that both of them will get colored is 0.5, and the probability that only one of them will get colored is 0.5. So the expected value is 0.5 * 2 + 0.5 * 1 = 1.5.

2
2
1
Returns: 1.875

With the same grid as in the previous example, but two selections, the expected value rises to 1.875.

1
2
2
Returns: 2.25

3
5
7
Returns: 19.11917924647044

0
1000
1000
Returns: 0.0

Submissions are judged against all 60 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GridColoring with a public method double area(int K, int rows, int cols) · 60 test cases · 2 s / 256 MB per case