## Standard Deviation

Moderator: Board moderators

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

### Standard Deviation

Problem I
Standard Deviation

Do we have to write the for loop and then calculate the average and solve it. Any other tricks ?

sharpobject
New poster
Posts: 4
Joined: Sun Jul 31, 2005 6:37 am
Contact:
If we knew the period on the random number function, might be a bit easier. If it's small enough, the answer becomes much simpler because we'd just have to consider (((standard dev of the period)^2)*repetitions+any numbers from outside the period) then sqrt() that.

abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am
I think the random number generator used int he problem is commonly known as the
chi^2 generator. (except for the division by 2^31-1, which could have been ignored in the computations anyways). But I don't know anything about the period of this generator or how to find it : (

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
I got AC during the contest without looking for any period. My implementation was about 5 times faster than naive copy-paste from the problem statement, but it was still not enough. However, adding one small trick made it.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
The idea of my first submission was simply "if (numbers > 500000) numbers = 500000", but it got WA. My AC solution did look for a period in the RNG. (I used Floyd's method, a.k.a. the two pointers method.)