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

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.

https://drive.google.com/open?id=1ReXuKeDWnQPsGF9VeP7MVpHD5m8LvqV2

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

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

3 Likes

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

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


[1]


  [1]: https://ideone.com/iU9F67

What I did was if n was even I printed -sigma n/2 times and sigma n/2 times. This makes the mean 0 and std=sqrt(n*sigma^2/sigma) = sigma.

If n was odd (n=1 handled separately) print last element as 0 and (n-1)/2 elements as sigma * sqrt(n/n-1) and the remaining as (-1 * sigma* sqrt(n/n-1)). Again makes mean 0 and then the usual stuff.

2 Likes

Another possible Approach which was used by our team is as follows. This is different from all other approaches because in this case each number generated is distinct i.e. no two numbers are same.

Let us try to generate an Arithmetic Progression :

k, 2k, 3k, 4k,…,nk whose standard deviation is \sigma. where k is some real number.

The value of k can be derived in about 6-7 lines by solving the equation of Standard Deviation which is left as an exercise for the reader. ( :stuck_out_tongue: )

For n=1 , denominator( for eqn of k) turns out to be zero which indicated “-1” for the case when n=1.

My apologies for bad representation of formulas.

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

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 :slight_smile:

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.

@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.