Mother of Dragons
Contest: Codeforces Round 428 (Div. 2)
Difficulty rating: 2700
Tags: brute force, graphs, math, meet-in-the-middle

There are n castles in the Lannister's Kingdom and some walls connect two castles, no two castles are connected by more than one wall, no wall connects a castle to itself.

Sir Jaime Lannister has discovered that Daenerys Targaryen is going to attack his kingdom soon. Therefore he wants to defend his kingdom. He has k liters of a strange liquid. He wants to distribute that liquid among the castles, so each castle may contain some liquid (possibly zero or non-integer number of liters). After that the stability of a wall is defined as follows: if the wall connects two castles a and b, and they contain x and y liters of that liquid, respectively, then the strength of that wall is x·y.

Your task is to print the maximum possible sum of stabilities of the walls that Sir Jaime Lannister can achieve.

Input format:
The first line of the input contains two integers n and k (1 ≤ n ≤ 40, 1 ≤ k ≤ 1000).

Then n lines follows. The i-th of these lines contains n integers ai, 1, ai, 2, ..., ai, n ($$a_{i,j} \in \{0,1\}$$). If castles i and j are connected by a wall, then ai, j = 1. Otherwise it is equal to 0.

It is guaranteed that ai, j = aj, i and ai, i = 0 for all 1 ≤ i, j ≤ n.

Output format:
Print the maximum possible sum of stabilities of the walls that Sir Jaime Lannister can achieve.

Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $$\frac{|a-b|}{\max(1,b)} \leq 10^{-6}$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, we can assign 0.5, 0.5, 0 liters of liquid to castles 1, 2, 3, respectively, to get the maximum sum (0.25).

In the second sample, we can assign 1.0, 1.0, 1.0, 1.0 liters of liquid to castles 1, 2, 3, 4, respectively, to get the maximum sum (4.0)

Example input:
3 1
0 1 0
1 0 0
0 0 0

Example output:
0.250000000000

Example input:
4 4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0

Example output:
4.000000000000

Editorial:
Lemma : Let G be a simple graph. To every vertex of G we assign a nonnegative real number such that the sum of the numbers assigned to all vertices is 1. For any two connected vertices (by an edge), compute the product of the numbers associated to these vertices. The maximal value of the sum of these products is when assign equal numbers to a maximal clique (a subgraph that all of its vertices are connected to each other) and 0 to the rest of the graph.
Proof : If the graph is complete of order n then the problem reduces to finding the maximum of $$\sum_{1 < i < j \leq n} x_i \cdot x_j$$ knowing that x1 + x2 + … + xn = 1. This is easy, since $$\sum_{1 \leq i < j \leq n} x_i x_j = \frac{1}{2} \left( 1 - \sum_{i=1}^n x_i^2 \right) \leq \frac{1}{2} \left( 1 - \frac{1}{n} \right)$$. The last inequality is just the Cauchy-Schwarz inequality and we have equality when all variables are $${\frac {1}{n}}$$.
Unfortunately, the problem is much more difficult in other cases, but at least we have an idea of a possible answer: indeed, it is easy now to find a lower bound for the maximum: if H is the complete subgraph with maximal number of vertices k, then by assigning these vertices $${ \frac { 1 } { k ^ { * } } }$$ and to all other vertices 0, we find that the desired maximum is at least $$\frac{1}{2} \left( 1 - \frac{1}{k} \right)$$. We still have to solve the difficult part: showing that the desired maximum is at most $$\frac{1}{2} \left( 1 - \frac{1}{k} \right)$$.
Let us proceed by induction on the number n of vertices of G. If n = 1 everything is clear, so assume the result true for all graphs with at most n−1 vertices and take a graph G with n vertices, numbered 1, 2, ... , n. Let A be the set of vectors with nonnegative coordinates and whose components add up to 1 and E the set of edges of G. Because the function $$f(x_{1},x_{2},\ldots,x_{n})=\sum_{(i,j)\in E}x_{i}\cdot x_{j}$$ is continuous on the compact set A , it attains its maximum in a point (x1, x2, ... , xn). If at least one of the xi is zero, then f(G) = f(G1) where G1 is the graph obtained by erasing vertex i and all edges that are incident to this vertex. It suffices to apply the induction hypothesis to G1 (clearly, the maximal complete subgraph of G1 has at most as many vertices as the maximal complete subgraph of G). So, suppose that all xi are positive. We may assume that G is not complete, since this case has already been discussed. So, let us assume for example that vertices 1 and 2 are not connected. Choose any number 0 < a ≤ x1 and assign to vertices 1, 2, ... , n of G the numbers x1−a, x2 + a, x3, ... , xn. By maximality of f(G), we must have $$\sum_{i \in C_1} x_i \leq \sum_{i \in C_2} x_i$$ , where C1 is the set of vertices that are adjacent to vertex 2 and not adjacent to vertex 1 (the definition of C2 being clear). By symmetry, we deduce that we must actually have $$\sum_{i \in C_1} x_i = \sum_{i \in C_2} x_i$$ , which shows that f(x1, x2, ... , xn) = f(0, x1 + x2, x3, ... , xn). Hence we can apply the previous case and the Lemma is solved.
Now by the Lemma , we have to find the maximal clique and get the answer.(Let the maximal clique have m vertices, then the answer is $$\frac{k^2 \cdot (m-1)}{2*m}$$).
We can find the maximal clique by the "meet in the middle" approach. Divide the vertices of the graph into 2 sets with equal number of vertices in each set(if n is odd, one set will have a vertex more than the other). We can save the maximal clique for each subset of the first set in dp[mask]. Now ,for each clique C in the second set, let v1, ... , vt be vertices in the first set that are connected to all of the vertices of C. Then m = max(m, dp[mask(v1, ... , vt)] + sizeof(C)) (m is size of maximum clique). Note : finding the maximal clique is also possible by a wise brute forces.