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