Expected Maximum Matching

All submissions for this problem are available.
You are given two sets of vertexes U = {U[1], U[2], ..., U[N]} and V = {V[1], V[2], ..., V[M]}. All N + M vertexes here are different. You are also given the matrix P of size N x M composed of real numbers from the segment [0, 1]. The number that stands at the intersection of the i^{th} row and the j^{th} column of this matrix is denoted by P[i][j] and means the probability that the vertexes U[i] and V[j] are connected by the bidirected edge. In other words, you are given a complete bipartite graph where each edge occurs with some probability. Your task is to find the expected size of the maximum matching of this graph.
What exactly does it mean?
Let's call our complete bipartite graph with random edges as random bipartite graph.
Consider some arbitrary bipartite graph G = (U, V, E). Denote by P(G) the probability that our random bipartite graph is equal to G. How to calculate P(G)? Consider some pair of vertexes (U[i], V[j]). If these vertexes are connected by the edge in G then put P_{G}[i][j] = P[i][j] otherwise put P_{G}[i][j] = 1 – P[i][j]. Then P(G) is equal to the product of P_{G}[i][j] for all N ∙ M pairs of (i, j), where 1 ≤ i ≤ N and 1 ≤ j ≤ M.
Next, denote by MM(G) the size of the maximum matching in the graph G. In other words, MM(G) is the size of the largest set of edges of G such that no two edges share a common vertex.
Finally, the expected size of the maximum matching is the sum of products P(G) ∙ MM(G) for all possible bipartite graphs G with parts U and V. Note that there are 2^{ N ∙ M } such graphs in all. So don't try to calculate the answer directly by definition if you do not want to get verdict Time Limit Exceeded ;)
Input
The first line of the input file contains two integers N and M. Each of the following N lines contains M real numbers. j^{th} number in the i^{th} line of these N lines denotes P[i][j], the probability that the vertexes U[i] and V[j] are connected by the direct edge. Each pair of consecutive numbers in every line is separated by exactly one space.
Output
In the only line of the output file print the expected size of the maximum matching. Your answer will be considered as correct if it has an absolute error less than 10^{6}.
Constraints
1 ≤ N ≤ 5
1 ≤ M ≤ 100
0 ≤ P[i][j] ≤ 1
P[i][j] will have exactly 5 digits after the decimal point
Example
Input 1: 3 3 0.38064 0.30000 0.29486 0.41715 0.90000 0.67837 0.53316 1.00000 1.00000 Output 1: 2.575940 Input 2: 2 2 0.40000 1.00000 0.10000 1.00000 Output 2: 1.46
Explanation
In the second example we have four different graphs with nonzero value of P(G). Their adjacent matrices with marked maximum matching as well as the values of MM(G) and P(G) are listed in the table below.
Adjacent matrix  MM(G)  P(G)  

1  (1 – 0.4) ∙ (1 – 0.1) = 0.6 ∙ 0.9 = 0.54  

2  0.4 ∙ (1 – 0.1) = 0.4 ∙ 0.9 = 0.36  

2  (1 – 0.4) ∙ 0.1 = 0.6 ∙ 0.1 = 0.06  

2  0.4 ∙ 0.1 = 0.04 
So the answer is 0.54 ∙ 1 + 0.36 ∙ 2 + 0.06 ∙ 2 + 0.04 ∙ 2 = 1.46.
Author:  shangjingbo 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/MATCH 
Tags  hard, june12, matching, probability, shangjingbo 
Date Added:  29032012 
Time Limit:  0.6  0.662602 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 