# How to solve second problem STDDEV of acm icpc online round

Pleas explain the solution of STDDEV

Let the standard deviation be denoted by ‘sigma’

and mean denoted by mu

So according to the formula given in the problem :

Sigma^2 = SummationOf((xi-mu)^2)/n

n*sigma^2 = SummationOf((xi-mu)^2)

If we take the mean(mu) = 0

The equation reduces to

n*sigma^2 = SummationOf(xi^2)

For doing so , what we can do is to have n/2 positive numbers and their n/2 additive inverse .
This will make our mu=0;

But we can simplify it further . What if we have a number x and its additive inverse -x in the array and all the rest of numbers are 0 . By doing this , mu still remains 0 .

And our equation becomes

n*sigma^2 = (x)^2 + (-x)^2

nsigma^2 = 2((x)^2)

x^2 = n(sigma^2)/2*

x = sqrt(n(sigma^2)/2)*

So now you have the value of x . Print x , -x and the rest of numbers are 0 .

For corner cases , if sigma is 0 , you only have to output n 0s .

I n is 1 and sigma !=0 , the case yiels -1 and as it not possible to have sigma ! = 0.

Hope this helps.

5 Likes

My apologies for bad representation of formulas.

Try to print array such that first element is A1 and all other are zero.

Process to find A1 is shown in image.

For N=1 consider other case i.e, if N=1 Sigma has to be zero for any value of A1. And print -1 if N=1 && Sigma !=0.

2 Likes

For such constructive algorithm questions, especially of this type, there are several methods.

1. (N-1) elements have some fixed value, and we manipulate the last element. In this case, we can set all (N-1) elements to 0, and find the last element accordingly. We can easily do so as-

Let K= standard deviation, and M be mean, and x be last element of array.

{K}^{2}=({(0-M)}^{2}+{(0-M)}^{2}+{(0-M)}^{2}+...(N-1 times)+{(x-M)}^{2})/N
N{K}^{2}={M}^{2}*(N-1)+{(x-M)}^{2}

But, M=(0+0+0...+x)/N=x/N since rest all elements are 0 element here except x.

Hence,
N{K}^{2}={(x/n)}^{2}*(N-1)+{((N-1)*x/N)}^{2}

On re-arranging, we get-
{N}^{3}*{K}^{2}={x}^{2}*((N-1)+{(N-1)}^{2})={x}^{2}(N-1+1-2*N+{N}^{2})={x}^{2}*(N*(N-1))

This simplifies to-

x=N*k/\sqrt{N-1}

Clearly, no answer exists for N=1.

Process 2-

If every element of an array of standard deviation k is multiplied by an element p, then standard deviation of new array = p*k.

So you find manually an array of standard deviation 1, and multiply with required constant.

5 Likes

It took me 35min to write the derivation neatly XDXD.

@vijju123 for N=1 and sigma =0 answer would exist. But if N=1 and sigma !=0 answer wont exist.

3 Likes

Sigma was from 1 to {10}^{5} as in constraints, so I was talking with respect to that. Also, please comment such one liners under appropriate answers- makes it easier to address things 1 Like

Oh I didnt saw that yeah if sigma>=1 then only case is if n==1 then no answer exist. Thanks for correcting me!

• Bow to your determination *

That’s pretty fast . It took me around 10-15 minutes to write these not so good representation .

Feels good to be back.

Another possible solution is as follows. (This is author’s solution).

Basically check the corner of n = 1 separately.

Now, let us fix the first n - 1 elements to be all zeros, and notice that if we increase n-th element from 0 to 10^8, the value of standard deviation will only increase. So, we use binary search over the last element to find out the desired \sigma.

3 Likes

@trashmaster: If you encode your math formulas in

math formuala
, for example -
x^2
, they will look properly formatted as latex symbols do.
1 Like

Process 2 was my main incentive with coming with the problem. The idea is that you can achieve a particular standard deviation by just multiplying the values by a constant was really nice.

\sigma was from 0 to 10^5.

But why use binary search when we already have a formula, i.e. fixed value for the last element for given deviation?

Considering precision issues, Binary search over values of data type double have to be especially done carefully.

But you need an array of size N with standard deviation 1. How will you find that?

Perhaps then I am forgetting things probably. Just like entire syllabus fades out an hour after exam :p. Sorry for that though.

The error margin is 1e-2, way too less. So, not much to worry about precision issues in general. You can easily use binary search. You can use formula too, but that’s not a reason against not using binary search.

Perhaps you are right. For me, absolute error margin is always dicey when values are large. I feel its better safe than sorry. I think you have a valid point, but my point also came from a similar practice problem.

I remember a problem, the values were <= {10}^{14} though, and we required careful binary search so that answer comes in margin of 0.01 of absolute error. My usual binary search gave WA. [Actually, the modification was trivial- but still, I mean, no one will want to take a risk when a O(1) solution is available- under impression that plain formula usage will minimize error].

1 Like

I solved this problem with the same method of putting all elements(except last one) equal to zero and finding the last element according to the equation. But I got wrong answer. Can anybody find what is wrong with my




: https://ideone.com/iU9F67