ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1457. Heating Main

proving the approach correct
Posted by Bogatyr 4 Oct 2012 01:16
In the fine tradition of "digging deeper," I wanted to understand the solution to this problem more completely.   I mean, when I read the problem statement, it did not jump out at me instantly that the value of x that minimizes

 f(x) = k/n * ((x-a1)^2 + (x-a2)^2 + ... + (x-an)^2) is the artihmetic mean of a1...an

If you look at the example, you may think "Aha!  The output is the average of the input!"  But the solver must beware, test writers just love to mislead by simple example cases that do not reveal the entire subtlety of the problem.   They'll get you with one of those WA#12s if you're not careful.

So I dusted off my calculus and recalled that to calculate the min/max of a function, find the derivative of f(x) and set it to zero, and then solve for x.  So here we go...

f(x) = k * (x^2 -2(a1)x + (a1)^2 + x^2 -2(a2)x + (a2)^2 + ... + x^2 -2(an)x + (an)^2) / n
      = k (x^2 - (2/n)(a1 + a2 + ... + an)x + ((a1)^2 + (a2)^2 + ... + (an)^2)/n

so we have
f'(x) = k(2x - (2/n)(a1 + a2 + ... + an))
setting to zero and solving for x gives

x = (a1 + a2 + ... + an) / n

Voila!  Not a guess, but good solid derivation.   Oh, and we can be sure that this is minimum rather than a maximum because the function is an upward opening parabola (since we assume that k is positive).

Edited by author 04.10.2012 01:16
Re: proving the approach correct
Posted by BillSu 26 Apr 2014 18:21
Best Explanation.
Re: proving the approach correct
Posted by stomakun 20 Mar 2016 12:35
You may also see it in this way: the variance of samples x1..xn is the one that minimizes the sum of (xi-a)^2.
Re: proving the approach correct
Posted by IlushaMax 16 Apr 2016 23:55
I guess it's extremum, isn't it? We haven't learnt that makes it a little difficult(

Edited by author 16.04.2016 23:55
Re: proving the approach correct
Posted by IlushaMax 5 May 2016 12:21
I didn't know any extremums and others but now I know a little with this site: mathprofi.ru
Re: proving the approach correct
Posted by AB&B 14 Mar 2021 17:50
You are great, thank you!
Re: proving the approach correct
Posted by marat0210 8 Jan 2022 15:30
I haven't studied calculus yet, so i came up with the quadratic equation and it turns out to be correct, yet I don't even know how to prove it.