How to solve second problem STDDEV of acm icpc online round

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
int n,q;

their product can overflow when they both are of {10}^{5}. Additionally make sure you are printing atleast 3-4 decimal places.

1 Like

@vijju123 :slight_smile: even I forgot that!! Thats why I remebered that I wrote the case for sigma=0

Yes, I am sorry for the confusion @bhola_nit :slight_smile:

Omg!! why didn’t check for overflow? I was more concerned about some corner cases. :frowning:

It makes sense to worry in some cases. But remember, output was around 10^8. You were allowed to make an error of 10^5+1e-2. You can analyze and see that intermediate values won’t explode so much.

That’s easy. Basically, my idea is as follows. I want mean 0 and almost all the values a_i = 1, so the variance would be 1. If n is even, then keeping half 1’s and the half -1’s does the job.

Consider the case when n is odd. This is bit tricky case. Here you have to keep (n-1)/2 1’s and -1’s, let the remaining three numbers be x, y, z. We want x+y+z = 0 and x^2 + y^2 + z^2 = 3. Simplifying, we get z = -(x+y).

Now, we make further assumption that what if x = y.

We have z = -2*x, Solving eqs, x^2 = 0.5 \implies x = \sqrt(0.5), y = sqrt(0.5) and z=-2\times \sqrt(0.5)

Yes, the N being odd was troubling me. Now I can be in peace <3 :slight_smile:

@admin: Yes, I tested. They arent exploding much. Well, I just thought about playing it safe. Thanks for explaining it, I really appreciate this :slight_smile: <3

Same here :slight_smile:
The first thing that struck me was if all elements are at a fixed distance from the mean, the standard deviation will naturally equal that distance. This gave a solution for even N, and the adjustment for odd N followed.

1 Like

Thanks @admin . I will keep it in my mind from the next time.

What I did was I randomly filled array of size N with random numbers within 10^5. Calculated standard deviation of that array in linear time(while populating it), then just multiplied all elements by x, (x = required SD / current SD of array ). Why do we need an array with SD 1? SD X also works.


nice approach ! @swetankmodi

@swetankmodi: You just proved us too dumb. Thanks for such a nice approach :slight_smile: Totally missed this up. In the version, I had thought of allowing only integers in the array. That’s why this line of thought was more stuck.


@admin : glad it helped :slight_smile: and allowing only integers would have been more challenging :slight_smile: @jaideeppyne thanks

@swetankmodi ,only 1 word :PRESSURE=RIP THINKING XDDD. Damn, since doubles are allowed, its so true :3

Damn, that appeoach is sexy XD.