MAXEXPR - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Vlad Zavodnik
Tester- Suchan Park
Editorialist- Abhishek Pandey

DIFFICULTY:

Medium

PRE-REQUISITES:

Maths, Cauchy-Schwarz 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.

QUICK-EXPLANATION:

Key to AC- A very elegant solution is possible using Cauchy-Schwarz Inequality.

The Cauchy-Schwarz 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 Cauchy-Scwarz 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 Cauchy-Schwarz 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^2-c_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 :smiley:

  • 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 non-negative 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^2-c_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-

6 Likes

I have used lagrange Multiplier theorem.

10 Likes
3 Likes

Any simpler solution ? …

All i knew was to " Maximize a multivariable function under constraints " so i was pretty sure some great mathematician had already found a way for this. All i did was google search !! :wink:
my sol : https://www.codechef.com/viewsolution/25740200

4 Likes

I used Lagrange Multipliers but I am only getting 60 points, I think I am missing out on something, can someone help me identify the mistake?
Submission link: https://www.codechef.com/viewsolution/25770083

1 Like

Your solution outputs -nan for those test cases as output. Take this hint for now and try debugging.

Check my solution. I used Lagrange multiplier to solve this problem and it was quite easy.
https://www.codechef.com/viewsolution/25816957

3 Likes

Can you provide any good material to learn Lagrange multiplier?

Can you explain your approach?

Look at this : Simple solution for MAXEXPR using Lagrange's Multiplier

A solution other than digit dp? Was the editorial not clear at some place?

Where is it? …

In what course Cauchy-Schwarz Inequality is taught ? I never came across it …

Sorry, I thought this was ENCODING editorial XD

1 Like

It is taught in IOM mostly. Also, sometimes college math courses discussing Langrange teach it. Other wise yeah, its a little rare.

1 Like

Lol what is this? I mean that’s pretty good. Did no one else use the binary search solution though? I am guessing that’s what most people would have used looking at the number of submissions.
I had no idea what Cauchy-schwarz inequality or lagrange multiplier theorem is.
Although, I agree my solution does not make intuitive sense, at least to me, but it worked.
Here’s what I did,
I just observed from the given test cases that for the desired expression to be maximized, following expression was equal to each other for all i.
ki √(xi+Ci) = VAL (let)
Then I just thought of doing a binary search on VAL to find such values of xi (for all i) such that the first series given in the question is zero (as asked). It’s easy to find the values of xi if we have a VAL by just simply manipulating the equation of VAL to separate x on LHS.
Before doing the binary search, I had no idea how large the value of VAL could go. So first, I started with x = 0 and then 1 and kept on doubling the value of VAL until the series in x*k (the first given series) became positive.
Then I did a binary search to find the exact point at which this series became positive from negative, in other words, where this series is zero.
This way, I found the value of all Xi, then I just put the value of Xi’s in the second given series of Xi and Ci and outputted the answer.
Total time complexity = N * (number of steps in binary search)
More steps meant more preciseness. I did for 40 steps which I believe was quite more than what was required.
Again, I am not really sure why my solution worked. If someone figures it out then please let me know it too.
Here’s the code, it’s not very informative though.
https://www.codechef.com/viewsolution/25790258

4 Likes

The best resource I could find to learn about Lagrange multiplier: https://www.khanacademy.org/math/multivariable-calculus/applications-of-multivariable-derivatives/lagrange-multipliers-and-constrained-optimization/v/constrained-optimization-introduction

Best part is, he proves the theorem intuitively which my professor never did.

2 Likes

@vijju123 Great problem. Are you aware of any geometric interpretation of the resulting X? I can only see that it will be perpendicular to the original vector K from the first equation.

1 Like

Let P = kx. We want to distribute this value among n choices.

Let f(x) = \sqrt{x+c}. Using calculus, we can calculate the increase of f(x) by the change of P by computing the first derivative. We have \frac{d f }{d P} = \frac{d f }{d x} \frac{d x }{d P} = \frac{1}{2 \sqrt{x+c}} \frac{1}{k} .
In addition, one can check that the return is diminishing as x increase when x+c >0 (by the second derivative). Therefore, it is optimal to let \frac{d f }{d P} equal among n choices, that is \frac{1}{2 k_i \sqrt{x_i + c_i}} = C for some constant C.

I hope this answer your question why your idea of setting k_i \sqrt{x_i + c_i} = V works.

5 Likes