TopCoder SRM 583 - 950: RandomPaintingOnABoard

Problem Statement

给出一个n * m的棋盘，每个格子上有一个0到9的数字，所有的数字之和为S，
现在玩一个游戏，一开始所有的格子都是白色的，
每一回合你要按一定的概率选择一个格子，并将这个格子染黑（已经被染黑的格子可能被重复染色），
如果一个格子上的数字为x，那么这个格子被选择的概率是 x / S，
当在某一回合之后，如果发现这个棋盘的每一行每一列都至少有一个格子是黑色的，那么游戏结束，
请求出游戏结束的期望回合数。

1 <= n,m <= 21
1 <= n * m <= 150
每个格子上的数字保证在0到9之间
保证每一行每一列至少有一个格子上的数字非0

You are given a board with N row and M columns. We will use (i,j) to denote the j-th cell in the i-th row (0-based indices). Each cell is initially white. You goal is to have a board that has at least one black cell in each row, and at the same time at least one black cell in each column.

You will paint the cells black in turns. In each turn, you select one cell (in a specific way that is given below) and color it black. You stop as soon as your goal is achieved.

You are given a String[] prob consisting of N elements, each M characters long. All characters in prob are digits ('0'-'9'). The digit represented by the j-th character in the i-th row (0-based indices) will be denoted p[i][j]. This digit is the relative probability of cell (i,j) being chosen in each turn.

Formally, let s be the sum of all p[i][j]. Then in each turn the cell (i,j) is chosen with probability p[i][j]/s. Note that the same cell may be chosen multiple times: we may sometimes choose a cell that is already black.

The constraints guarantee that achieving your goal is possible. Return the expected number of turns until your goal is achieved.

Definition

Class RandomPaintingOnABoard
Method expectedSteps
Parameters vector<string>
Returns double
Method signature double expectedSteps(vector<string> prob)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

Your return value must have a relative or an absolute error of less than 1e-9.

Constraints

prob will contain between 1 and 21 elements, inclusive.
Each element of prob will be between 1 and 21 characters long, inclusive.
The elements of prob will be of the same length.
Each element of prob will consist of digits only ('0'-'9').
The total number of cells (i.e., the total number of digits in prob) will be between 1 and 150, inclusive.
In each row there will be at least one non-zero digit.
In each column there will be at least one non-zero digit.

Test cases

input
- prob {"10",
  "01"}
output
Returns 3.0

note

Each of the cells (0,0) and (1,1) has probability 1/2 to be chosen in each turn. One of those cells will be colored black in the first turn.

Then there will be some additional turns until the other cell is chosen. As that happens with probability 1/2, the expected number of additional turns is 2.

Thus the total expected number of turns is 1+2 = 3.
input
- prob {"11",
  "11"}
output
Returns 3.6666666666666665
note
This board is symmetric, so we can just assume that the cell (0,0) was chosen in the first turn.

Then there will be some additional turns until some other cell is chosen for the first time. The probability of choosing a different cell is 3/4, thus the expected number of these additional turns is 4/3.

Now, what is the second cell to be colored black?
- With probability 1/3 it is the cell (1,1) and we are done.
- With probability 2/3 it is one of the other two cells. In either of these two cases, we still need to color any one of the other two white cells black, and the expected number of turns until that happens is 2.
Thus the answer is 1 + 4/3 + (2/3 * 2) = 11/3.
input
- prob {"11",
  "12"}
output
Returns 3.9166666666666665
input
- prob {"0976",
  "1701",
  "7119"}
output
Returns 11.214334077031307
input
- prob {"000000000000001000000",
  "888999988889890999988",
  "988889988899980889999",
  "889898998889980999898",
  "988889999989880899999",
  "998888998988990989998",
  "998988999898990889899"}
output
Returns 1028.7662876159634

back to the menu