Maximize an Expression

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/AUG19/hindi/MAXEXPR.pdf), [Bengali](http://www.codechef.com/download/translated/AUG19/bengali/MAXEXPR.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/AUG19/mandarin/MAXEXPR.pdf), [Russian](http://www.codechef.com/download/translated/AUG19/russian/MAXEXPR.pdf), and [Vietnamese](http://www.codechef.com/download/translated/AUG19/vietnamese/MAXEXPR.pdf) as well. Chef had three sequences of real numbers $k_1, k_2, \ldots, k_N$, $c_1, c_2, \ldots, c_N$ and $x_1, x_2, \ldots, x_N$. Unfortunately, he lost the sequence $x$; the only thing he remembers about it is that $$x_1 \cdot k_1 + x_2 \cdot k_2 + \ldots + x_N \cdot k_N = 0 \,.$$ Chef's favourite expression is $$\sqrt{x_1+c_1} + \sqrt{x_2+c_2} + \ldots + \sqrt{x_N+c_N} \,.$$ Its value is defined only if $x_i+c_i \ge 0$ for each valid $i$. Let's denote the maximum value of this expression$ $ (over all sequences $x$ such that it is defined) by $F$. Help Chef find $F$ and a sequence $x_1, x_2, \ldots, x_N$ such that the value of Chef's expression is $F$, or determine that there is no solution (the value of Chef's expression is always undefined). ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ real numbers $k_1, k_2, \ldots, k_N$.  The third line contains $N$ real numbers $c_1, c_2, \ldots, c_N$. All real numbers are given with exactly two digits after the decimal point. ### Output For each test case, if there is no solution, print a single line containing one integer $1$. Otherwise, print a single line containing $N+1$ spaceseparated real numbers $F, x_1, x_2, \ldots, x_N$. It can be proved that if a solution exists, then it is unique. Your answer will be considered correct if the absolute or relative error of each number on the output does not exceed $10^{−2}$. ### Constraints  $1 \le T \le 10^5$  $2 \le N \le 10^5$  $0 \lt k_i \le 2,000$ for each valid $i$  $c_i \le 2,000$ for each valid $i$  the sum of $N$ over all test cases does not exceed $10^5$ ### Subtasks **Subtask #1 (15 points):** $N = 2$ **Subtask #2 (15 points):** $k_i = 1$ and $c_i = 0$ for each valid $i$ **Subtask #3 (15 points):** $k_i = 1$ for each valid $i$ **Subtask #4 (15 points):** $c_i = 0$ for each valid $i$ **Subtask #5 (40 points):** original constraints ### Example Input ``` 5 4 1.00 2.00 3.00 4.00 5.00 6.00 7.00 8.00 3 1.23 8.90 5.67 2.34 9.01 6.78 3 1.00 1.00 1.00 1.23 8.90 5.67 2 1.23 8.90 5.67 2.34 2 1.23 8.90 5.67 2.34 ``` ### Example Output ``` 12.0761472885 28.6000000000 2.4000000000 3.2666666667 5.9000000000 1 3.6578682316 0.2566666667 7.4133333333 7.1566666667 3.5802375027 15.5642936942 2.1510203645 1 ``` ### Explanation **Example case 1:** The optimal solution is $x = (28.6, 2.4, 49/15, 5.9)$. Then, $x_1 \cdot k_1 + x_2 \cdot k_2 + x_3 \cdot k_3 + x_4 \cdot k_4 = 28.6 \cdot 1 + 2.4 \cdot 2  49 \cdot 3 / 15 + (5.9) \cdot 4 = 0$, and $F = \sqrt{28.6+5}+\sqrt{2.4+6}+\sqrt{49/15+7}+\sqrt{5.9+8} \doteq 12.076$. This is the maximum value of Chef's expression. **Example case 2:** For each $i$, $c_i$ is negative, but $x_i+c_i$ must be nonnegative, so $x_i$ must be positive. However, all $k_i$ are also positive, so $x_1 k_1 + x_2 k_2 + \ldots + x_N k_N$ cannot be $0$. There is no solution.Author:  vladprog 
Editorial  https://discuss.codechef.com/problems/MAXEXPR 
Tags  aug19, cauchyschwarzinequality, math, vijju123, vladprog 
Date Added:  14062019 
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