MagicalMatrix
2016 TCO Beijing Regional · 2016-03-24 · by ltdtl
Problem Statement
Maya has a magical matrix toy. The matrix has n rows and m columns, and each entry a[r][c] at row r and column c is a Bernoulli random varaible. That is, a[r][c] is either 1 with a p[r][c]% chance or 0 with a (100-p[r][c])% chance. Assume that the set of n*m random variables are mutually independent.
Maya wants to know whether the magical matrix contains at least one column that consists only of 1's. Maya does not know the realization of any entry to begin with, but Maya can inspect an arbitrary entry of the matrix at unit cost which reveals the realization of it.
Maya is going to choose an inspection ordering of the entries of the matrix (which is a permutation of the n*m entries of the matrix). Maya is not going to make unnecessary inspections, as follows:
- If Maya finds that every column contains at least one 0, then Maya will stop inspecting immediately.
- If Maya finds that some column c consists only of 1's, then Maya will stop inspecting immediately.
- If Maya finds that some column c contains at least one 0, then Maya will not inspect the entries of this column in the future (but she will continue inspecting according to the inspection ordering she chose to begin with).
Given a permutation of the entries of the matrix, Maya can easily compute the expected number of inspections she needs to perform. But Maya wants to know of the minimum expected number of inspections, and asks for your help. Given the size of Maya's magical matrix and associated probabilities, compute the minimum expected number of inspections she needs to perform, in order to determine whether the matrix contains a column consisting only of 1's or not.
You are given as input an array of integers prob which contains exactly n*m elements. The probability p[r][c] is given by prob[(r-1)*m + c].
Constraints
- n will be between 1 and 10, inclusive.
- m will be between 1 and 250, inclusive.
- prob will contain exactly n*m elements.
- Each element in prob will be between 1 and 99, inclusive.
1
1
{50}
Returns: 1.0
The matrix is a one-by-one matrix. Maya needs to inspect one element in this case.
1
1
{99}
Returns: 1.0
Again, Maya needs to inspection one element.
2
2
{50,50,50,50}
Returns: 2.625
2
3
{1,1,1,1,1,1}
Returns: 3.0296970101000005
2
2
{60,70,90,80}
Returns: 2.382
In this case we have p[1][1] = 60%, p[1][2] = 70%, p[2][1] = 90%, and p[2][2] = 80%.
Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MagicalMatrix with a public method double MagicalInspection(int n, int m, vector<int> prob) · 110 test cases · 2 s / 256 MB per case