Page **1** of **1**

### Standard Deviation

Posted: **Sun Jul 31, 2005 6:59 am**

by **temper_3243**

Problem I

Standard Deviation

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

Posted: **Sun Jul 31, 2005 7:37 am**

by **sharpobject**

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.

Posted: **Sun Jul 31, 2005 7:05 pm**

by **abishek**

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

Posted: **Sun Jul 31, 2005 8:03 pm**

by **Krzysztof Duleba**

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.

Posted: **Sun Jul 31, 2005 10:25 pm**

by **misof**

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