Minimum Variance

All submissions for this problem are available.
You are given $n$ sets $S_1, S_2, \ldots, S_n$. For each $i$, you want to choose $x_i \in S_i$, such that the variance of the multiset $\{x_1, x_2, \ldots, x_n\}$ is minimized. The variance of a multiset $\{x_1, x_2, \ldots, x_n\}$ is defined as $\sigma^2 = \displaystyle \dfrac{\sum_{i=1}^{n} (x_i  \mu)^2}{n} $, where $\mu$ is the mean, which equals $\displaystyle \dfrac{ \sum_{i=1}^{n}x_i}{n}$. Say the minimum possible variance is $R$. Print $n^2 \times R$. It can be proved that $n^2 R$ is always an integer. ### Input  The first line contains $n$, the number of sets.  $i^{\text{th}} $ of the next $n$ lines contain an integer $S_i$ followed by $S_i$ distinct integers denoting the elements of set $S_i$. ### Output In the only line, print a single integer denoting the product of $n^2$ and the minimum possible variance of $\{x_1, x_2, \ldots, x_n\}$ ### Constraints  $1 \le n \le 50,000$  $ 1 \le S_i \le 50,000$ for all valid $i$.  $1 \le \displaystyle \sum_{i=1}^{n} S_i \le 50,000$  All elements in a single set are distinct.  The elements of all the sets are between $1$ and $50,000$ inclusive ### Example Input 1 ``` 2 3 3 7 1 2 5 11 ``` ### Example Output 1 ``` 4 ``` ### Example Input 2 ``` 2 2 2 5 1 5 ``` ### Example Output 2 ``` 0 ``` ### Explanation **Example case 1:** You should choose $x_1 = 3$ from $S_1$ and $x_2 = 5$ from $S_2$, the mean is $4$ and the variance is $\dfrac{(34)^2 + (5  4)^2}{2} = 1$. Hence, the output should be $n^2 \times 1 = 4$. **Example case 2:** Choosing $x_1 = x_2 = 5$ gives a variance of $0$.Author:  jtnydv25 
Tags  jtnydv25 
Date Added:  26112019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, 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. 