PROBLEM LINK:
Setter Vlad Zavodnik
Tester Suchan Park
Editorialist Abhishek Pandey
DIFFICULTY:
Medium
PREREQUISITES:
Maths, CauchySchwarz Inequality
PROBLEM:
Given 2 sequences k and c, find a sequence x such that \sum k_i*x_i=0 and \sum \sqrt {x_i+c_i} is maximum possible.
QUICKEXPLANATION:
Key to AC A very elegant solution is possible using CauchySchwarz Inequality.
The CauchySchwarz inequality says that
(a_1*b_1+...+a_n*b_n)^2 <= (a_1^2+...+a_n^2)*(b_1^2+...+b_n^2)
and that the equality holds iff a_1/b_1 = a_2/b_2 = ... = a_n/b_n.
Chose a_i=\sqrt{k_i*(x_i+c_i)}, b_i=1/\sqrt k_i. We have chose such a_i and b_i as their product a_i*b_i=\sqrt{x_i+c_i}.
Let F denote \sum a_i*b_i=\sum \sqrt{x_i+c_i}.
Substituting F and values of a_i,b_i in the inequality, we will find that F^2 \leq (\sum k_j*c_j)*(\sum 1/k_j). If this number turns out to be negative, then no sequence x is possible!
Else, we know that equality occurs if a_i/b_i is same for all i. That, along with cosntraint \sum k_i*x_i=0 gives us the final result of
x_i = (\sum с_j*k_j)/(k_i^2*(\sum 1/k_j))c_i
EXPLANATION:
This is a mathematical problem  and there are honestly multiple ways to arrive at the same result in maths. But I found setter’s use of CauchyScwarz Inequality pretty appealing and elegant. Hence we will derive it step by step here.
If you want to derive things yourself, then stuff from quick explanation is enough. You’d want to stop reading here and give an attempt.
We will break derivation into 2 steps
 Finding the upper bound
 Proving that upper bound can be reached (by finding x_i)
Lets get started!!
Upper Bound
Starting from the first step of quick explanation
The CauchySchwarz inequality says that
(a_1*b_1+...+a_n*b_n)^2 <= (a_1^2+...+a_n^2)*(b_1^2+...+b_n^2)
and that the equality holds iff a_1/b_1 = a_2/b_2 = ... = a_n/b_n.
Now, how can we relate it to this problem? Realize that we want an upper bound for \sqrt{x_i+c_i}
Looking at the inequality, it makes sense that a_i*b_i=\sqrt{x_i+c_i} because then we will successfully get an upper bound  that too an upper bound which we know is possible! (Because we know the condition for existence of equality!)
Now, when we are faced with this problem, of making a_i *b_i =f(x), there are a few tricks we can use

Decompose f(x) into 2 functions h(x) and g(x) such that f(x)=g(x)*h(x) and try.

A very common trick to use then, is to look at what variables you know, and put a_i = P(y) * f(x) and b_i=\frac{1}{P(y)} where P(y) just denotes any function which we know, or can compute using input. In other words, we are setting a_i=f(x), then multiplying a_i with some thing, and divide b_i with the same thing.
Now \sqrt{x_i+c_i} is not a very easy function to decompose. Hence, the latter trick seems useful. Hence, lets explore the second trick.
We set a_i=\sqrt{x_i+c_i} for now. Now, we are in knowledge of the sequence k and the sequence c. So great, we can either have P(y) as some function of k, some function of c or perhaps a mixed function of both k and c. How to decide this?
Realize that we also have an equation that \sum k_i*x_i=0. This is a good hint that setting P(y) as some function of sequence k is a good idea because then we may be able to use this equation later on!
Since the equation is \sum k_i *x_i=0, we decide that P(y)=\sqrt k_i would be the best as then a_i=\sqrt{k_i*(x_i+c_i)}  something where we can straight forwardly use the equation later on.
So lets keep a_i=\sqrt{k_i *(x_i+c_i)} and b_i=1/ \sqrt{k_i}.
Substituting them to the inequality, we get
(\sum \sqrt{x_i+c_i})^2 \leq \sum(k_i*(x_i+c_i)) * (\sum 1/ k_i) .
Let me define F=\sum \sqrt{x_i+c_i} for convenience while denoting. Now, we have
F^2 \leq \sum(k_i*(x_i+c_i)) * (\sum 1/ k_i)
Let me define LHS as 
LHS = \sum(k_i*(x_i+c_i)) * (\sum 1/ k_i)
= \sum(k_i*x_i+k_i*c_i) * (\sum 1/ k_i)
=\sum(0+k_i*c_i) * (\sum 1/ k_i)
= \sum (k_i*c_i) * (\sum 1/k_i)
\implies F^2 \leq \sum (k_i*c_i) * (\sum 1/k_i)
With this, we conclude that
\therefore F \leq \sqrt{\sum (k_i*c_i) * (\sum 1/k_i) }
We obtained an upper bound. Now, no solution is possible iff the value inside the square root is negative. Meaning, no solution exists if \sum (k_i*c_i) * (\sum 1/k_i) <0.
Since in the given constraints of the problem, k_i >0, so we know that \sum 1/k_i will always be positive. Hence, we only need to check for \sum (k_i*c_i) \geq 0
We are done with first half of the proof.
Finding the sequence x
We found the upper bound, and also dealt with case of no solution above. Now, if a solution is existing, we will proceed as follows
We found the upper bound of F=\sum \sqrt{x_i+c_i} above. We also know that F will be equal to the upper bound only in case when a_1/b_1 = a_2/b_2 = ... = a_n/b_n.
Now, as we discussed above, we have a_i=\sqrt{k_i *(x_i+c_i)} and b_i=1/ \sqrt{k_i}
\implies a_i/b_i = k_i * \sqrt{x_i+c_i}
Let a_1/b_1 = a_2/b_2 = ... = a_n/b_n=B where B is some constant.
\implies a_i/b_i = B
Squaring both sides, (because mathematics after removing the square root is often easier!)
\implies (a_i/b_i)^2 = k_i ^2*(x_i+c_i)=B^2 where B is some constant.
Now, our equation is
a_1/b_1 = a_2/b_2 = ... = a_n/b_n
Lets see if we can find an equation by this. Note that, B was a constant we introduced just to make denotation easier  but when solving, we should avoid using B in the equation as much as we can because we do not know the value of B (B, although ultimately a constant, needs x to be calculated). Its better to equate some a_i/b_i=a_j/b_j and see where we can go from there. For sake of clarity, let j=1 in our below solving
\implies a_i/b_i=a_1/b_1 for all i.
\implies k_i^2*(x_i+c_i)= k_1^2*(x_1+c_1)
Dividing both sides by k_i^2
\implies x_i+c_i = (k_1^2/k_i^2)*(x_1+c_1)
\implies x_i = (k_1^2/k_i^2)*(x_1+c_1)с_i
Great, we made some progress! We are able to get a dependency between x_i and (x_1+c_1). Now, if we could just get 1 more equation to somehow find (x_1+c_1) or use the above value of x_i, we can proceed.
This is time to use our last hope! Our lovely \sum k_i*x_i=0 yet again! Substituting value of x_i here
\sum_{i=1} ^{i=n} [(k_1^2/k_i^2*(x_1+c_1)с_i)*k_i] = 0
\implies \sum [(k_1^2/k_i^2)*(x_1+c_1)*k_i)]  (\sum с_i*k_i) = 0
\implies \sum [(k_1^2/k_i)*(x_1+c_1)] = (\sum с_i*k_i)
Since (x_1+c_1) and k_1 on LHS is constant, we can take it out of the summation symbol
(x_1+c_1)*k_1^2*(\sum 1/k_i) = (\sum с_i*k_i)
\implies x_1+c_1 = (Σ с_i*k_i)/(k_1^2*(Σ 1/k_i))
Great! We are able to find the value of (x_1+c_1). Lets put it back in our previous equation of x_i.
\because x_i+c_i = k_1^2/k_i^2*(x_1+c_1)
\therefore x_i+c_i=(k_1^2/k_i^2)*(Σ с_j*k_j)/(k_1^2*(Σ 1/k_j))
x_i+c_i= (Σ с_j*k_j)/(k_i^2*(Σ 1/k_j)) (by cancelling k_1 from numerator and denominator)
\implies x_i = (Σ с_j*k_j)/(k_i^2*(Σ 1/k_j))c_i
Let t=(\sum с_j*k_j)/(\sum 1/k_j), as it can be precomputed. Now, x_i= t/k_i^2c_i
SOLUTION
Setter
from math import*
for _ in range(int(input())):
n=int(input())
k=list(map(float,input().split()))
c=list(map(float,input().split()))
SUMck,SUM_k=0.0,0.0
for i in range(n):
SUMck+=c[i]*k[i]
SUM_k+=1/k[i]
F2=SUMck*SUM_k
if F2<0:
print(1)
else:
print(sqrt(F2),end=' ')
t=SUMck/SUM_k
for i in range(n):
print(t/k[i]/k[i]c[i],end=' ')
print()
Tester
import java.math.BigDecimal
import java.math.RoundingMode
const val PRECISION = 15
val mc = java.math.MathContext(PRECISION)
val MY_ONE = BigDecimal.ONE.setScale(PRECISION)
fun main(Args: Array<String>) {
var sumN = 0L
val reader = java.io.BufferedReader(System.`in`.reader())
val _NUM_TESTS = reader.readLine()!!.toInt()
require(_NUM_TESTS in 1..100000)
repeat(_NUM_TESTS) {
val N = reader.readLine()!!.toInt()
require(N in 2..100000)
sumN += N
val line1 = reader.readLine()!!.split(" ")
val K = line1.map{ BigDecimal(it).setScale(PRECISION, RoundingMode.HALF_EVEN) }
require(line1.all{
it[it.length  3] == '.' && it.substring(it.length  2 until it.length).all { it in "0123456789" }
})
require(line1.size == N)
require(line1.all{ it == "1.00" })
val line2 = reader.readLine()!!.split(" ")
val C = line2.map{ BigDecimal(it).setScale(PRECISION, RoundingMode.HALF_EVEN) }
require(line2.all{
it[it.length  3] == '.' && it.substring(it.length  2 until it.length).all { it in "0123456789" }
})
require(line2.size == N)
val a = K.map{ MY_ONE / it }.reduce{ x, y > x + y }
val b = K.zip(C).map{ (k, c) > k * c }.reduce{ x, y > x + y }
val lambda = b / a
val X = K.zip(C).map{ (k, c) > (lambda / k / k  c) }
val Y = X.zip(C).map{ (x, c) > x + c }
if(Y.all { it.signum() >= 0 }) {
print(Y.map{ y > y.sqrt(mc) }.reduce{ x, y > x + y }.toDouble())
print(" ")
println(X.map{ it.toDouble() }.joinToString(" "))
}else {
println(1)
}
}
require(sumN <= 100000)
}
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER
 What other popular inequalities or theorems could you use to prove the above?
Prove that Xi+Ci is always greater than or equal to 0
Notice that (Σ с_j*k_j)>=0 (this was proven), (k_i^2*(Σ 1/k_j))>0 (because k_j>0), so x_i+c_i>=0
Setter's Notes (With subtask solutions)
We will use Cauchy–Schwarz inequality: for any a_j,b_j:
(a_1*b_1+...+a_n*b_n)^2 <= (a_1^2+...+a_n^2)*(b_1^2+...+b_n^2), and equality holds if and only if a_1/b_1 = a_2/b_2 = ... = a_n/b_n.
Let a_j=\sqrt{k_j*(x_j+c_j}), b_j=1/\sqrt k_j.
Let’s substitute:
F^2 = (Σ \sqrt{x_j+c_j})^2 <= (Σ k_j*x_j+k_j*c_j)*(Σ 1/k_j) = ((Σ k_j*x_j)+(Σ k_j*c_j))*(Σ 1/k_j) = (0+(Σ k_j*c_j))*(Σ 1/k_j) = (Σ k_j*c_j)*(Σ 1/k_j)
If the resulting number is negative, then square of some number is not greater than negative number, so F can’t take any value. Otherwise number (Σ k_j*c_j)*(Σ 1/k_j) is nonnegative and
F<= \sqrt{(\sum k_j*c_j}*(\sum 1/k_j)).
Notice, that k_j are positive => (Σ 1/k_j)>0 => (Σ k_j*c_j)>=0.
Now we will prove, that F=sqrt((Σ k_j*c_j)*(Σ 1/k_j)) can be reached. Let’s use equality criteria. For all j must hold:
k_j*\sqrt{x_j+c_j} = const
Let’s prove, that this is possible (that is there exsist such x_i, that they satisfy a statement and x_i+c_i>=0)
k_i^2*(x_i+c_i) = const
k_1^2*(x_1+c_1) = k_i^2*(x_i+c_i)
x_i+c_i = k_1^2/k_i^2*(x_1+c_1)
x_i = k_1^2/k_i^2*(x_1+c_1)с_i
Let’s substitute x_i to equation x_1*k_1+x_2*k_2+...+x_n*k_n=0:
Σ (k_1^2/k_j^2*(x_1+c_1)с_j)*k_j = 0
(Σ k_1^2/k_j^2*(x_1+c_1)*k_j)  (Σ с_j*k_j) = 0
(Σ k_1^2/k_j*(x_1+c_1)) = (Σ с_j*k_j)
(x_1+c_1)*k_1^2*(Σ 1/k_j) = (Σ с_j*k_j)
x_1+c_1 = (Σ с_j*k_j)/(k_1^2*(Σ 1/k_j))
Let’s consider previously proven equality:
x_i+c_i = k_1^2/k_i^2*(x_1+c_1) = k_1^2/k_i^2*(Σ с_j*k_j)/(k_1^2*(Σ 1/k_j)) = (Σ с_j*k_j)/(k_i^2*(Σ 1/k_j))
x_i = (Σ с_j*k_j)/(k_i^2*(Σ 1/k_j))c_i
Notice that (Σ с_j*k_j)>=0 (this was proven), (k_i^2*(Σ 1/k_j))>0 (because k_j>0), so x_i+c_i>=0.
So, we proved, that F<=\sqrt((Σ k_j*c_j)*(Σ 1/k_j)) ans this value can be reached. So answer is \sqrt((Σ k_j*c_j)*(Σ 1/k_j)).
Let’s calculate t = (Σ с_j*k_j)/(Σ 1/k_j). Then a_i = t/k_i^2c_i.
Complexity : O(n).
Solution for subtask 1 (n=2)
Given equality:
x1*k1+x2*k2=0
x2=k1/k2*x1
Given expression:
F=\sqrt{x1+c1}+\sqrt{x2+c2}
So:
x1+c1>=0
=> x1>=c1
x2+c2>=0
\implies x2>=c2
\implies k1/k2*x1>=c2
\implies x1<=k2/k1*c2
Following observation is, that function F(x1) is concave (and so unimodal) on its domain (it can be proved via getting second derivative and proving that it is positive).
So we can run ternary search in found bounds.
Complexity : O(log(m)) where m is maximal possible value of x1.
Solution for subtasks 2 and 4 (c_i=0 for all i):
Given expression:
F=\sum(\sqrt x_i)
So x_i>=0 for all i.
If at least one x_i be positive, then \sum(x_i*k_i) will be positive too (because k_i>0)  contradiction.
So all x_i=0 and F=0.
Complexity : O(n).
Related Problems
Sorry! Its hard to find specific problems on this particular inequality. If you come across one, please let us know!
Until then, some problems on general mathematics