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?
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
Cauchy - Schwarz was something taught in middle school so Im quite surprised to see not many people know it. This problem is ridiculously basic if you do.
We all have different backgrounds, including schools.
1 Like
This is the sort of solution I like, that does not depend on happening to know a mathematical trick! I also worked backwards from observing the pattern in the supplied test cases.
3 Likes
Yeah, that’s why I say I’m quite surprised to see that not many countries do the same.
This is what I was looking for.
Thank you!
2 Likes