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
Omg!! why didn’t check for overflow? I was more concerned about some corner cases. 
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 
@admin: Yes, I tested. They arent exploding much. Well, I just thought about playing it safe. Thanks for explaining it, I really appreciate this <3
Same here
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
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.
5 Likes
@swetankmodi: You just proved us too dumb. Thanks for such a nice approach 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.
3 Likes
@admin : glad it helped and allowing only integers would have been more challenging @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.
2 Likes