Standard Deviation

Let's talk about algorithms!

Moderator: Board moderators

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

Standard Deviation

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
New poster
Posts: 4
Joined: Sun Jul 31, 2005 6:37 am
Contact:

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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

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

Post Reply

Return to “Algorithms”