{"raw_statement":[{"iden":"statement","content":"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$.\n\nNow, 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!\n\nThe 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 eq.not j, 0 <= i, j < n$) representing adjacent vertices $x_i$ and $x_j$ in $G$.\n\nYou are guaranteed that $1 <= n <= 100$ and $1 <= | G | <= 1600$.\n\nOutput a double representing the maximal standard deviation within a $. 0001$ margin of error.\n\nThis problem has the same prerequisites as UT's CS331 Algorithms: Probability/stats and matrices/linear algebra.\n\n"},{"iden":"input","content":"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 eq.not j, 0 <= i, j < n$) representing adjacent vertices $x_i$ and $x_j$ in $G$.You are guaranteed that $1 <= n <= 100$ and $1 <= | G | <= 1600$."},{"iden":"output","content":"Output a double representing the maximal standard deviation within a $. 0001$ margin of error."},{"iden":"note","content":"This problem has the same prerequisites as UT's CS331 Algorithms: Probability/stats and matrices/linear algebra."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected unweighted graph with $ n $ vertices $ V = \\{x_0, x_1, \\dots, x_{n-1}\\} $.  \nLet $ \\mathbf{X} = (x_0, x_1, \\dots, x_{n-1})^\\top $ be a random vector with $ \\mathbb{E}[x_i] = 0 $ for all $ i $.  \n\nThe covariance matrix $ \\Sigma \\in \\mathbb{R}^{n \\times n} $ is defined as:  \n- $ \\Sigma_{ii} = \\deg(i) $ (degree of vertex $ x_i $),  \n- $ \\Sigma_{ij} = -1 $ if $ (i,j) \\in E $,  \n- $ \\Sigma_{ij} = 0 $ otherwise.  \n\n**Constraints**  \nLet $ \\mathbf{w} \\in \\mathbb{R}^n $ be a weight vector such that $ \\|\\mathbf{w}\\|_2 = 1 $.  \n\n**Objective**  \nMaximize the variance of the linear combination $ \\mathbf{w}^\\top \\mathbf{X} $:  \n$$\n\\max_{\\|\\mathbf{w}\\|_2 = 1} \\mathbf{w}^\\top \\Sigma \\mathbf{w}\n$$  \nThis is equivalent to finding the largest eigenvalue of $ \\Sigma $.  \n\n**Output**  \nThe square root of the largest eigenvalue of $ \\Sigma $, i.e., the maximal standard deviation.","simple_statement":"Find the maximum possible standard deviation of a linear combination of random variables $ x_0, \\dots, x_{n-1} $ with unit norm coefficients, where each $ x_i $ has variance equal to its degree in graph $ G $, and covariance between $ x_i $ and $ x_j $ is $ -1 $ if they are connected, else $ 0 $.","has_page_source":false}