407258: GYM102726 J Risk

Let $$$X = x_0, \cdots, x_{n-1}$$$ be random variables with zero expectation, and let $$$G$$$ be an undirected unweighted graph with vertices $$$X$$$. Define the variance of $$$x_i$$$ to be the degree of the vertex $$$x_i$$$ in $$$G$$$, and the covariance between $$$x_i$$$ and $$$x_j$$$ to be $$$-1$$$ if $$$x_i$$$ is adjacent to $$$x_j$$$ in $$$G$$$ and $$$0$$$ otherwise. Your goal is to come up with a linear combination of the $$$x_i$$$'s with maximal variance. In general, this is obviously unbounded, so please restrain yourself to linear combinations where the sum of the squares of the coefficients adds to $$$1$$$.

Now, here's an unrelated, completely hypothetical story. Alex graduated from his university with a computer science degree, but decided to work in finance instead of tech. This might have been a big mistake – his big performance review is in two days, and he has lost millions of dollars through the past couple of months due to trading blunders. Thankfully, he has come up with a plan to save his job with the following motto: "Go big or go home". All he needs to do is take on the riskiest possible position. If it pans out he'll keep his job, and if it goes belly up... well, he was going to get fired anyway!

The first line will have space-separated integers $$$n$$$, the number of vertices in the graph, and $$$|G|$$$, the number of edges in the graph. $$$|G|$$$ lines follow, each containing a pair of space-separated integers, $$$i$$$ and $$$j$$$ ($$$i \neq j, 0 \leq i, j < n$$$) representing adjacent vertices $$$x_i$$$ and $$$x_j$$$ in $$$G$$$.

You are guaranteed that $$$1 \le n \le 100$$$ and $$$1 \le |G| \le 1600$$$.

Output a double representing the maximal standard deviation within a $$$.0001$$$ margin of error.

2 1
0 1

1.4142135623730951

This problem has the same prerequisites as UT's CS331 Algorithms: Probability/stats and matrices/linear algebra.