Standard Deviation

temper_3243 · Post by **temper_3243** » Sun Jul 31, 2005 6:59 am

Problem I
Standard Deviation

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

sharpobject · Post by **sharpobject** » Sun Jul 31, 2005 7:37 am

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 · Post by **abishek** » Sun Jul 31, 2005 7:05 pm

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 · Post by **Krzysztof Duleba** » Sun Jul 31, 2005 8:03 pm

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 · Post by **misof** » Sun Jul 31, 2005 10:25 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.)