10886 - Standard Deviation

sunnycare · Post by **sunnycare** » Thu Aug 18, 2005 11:51 am

is there some skills to make my prog faster?

//10886 Standard Deviation
#include <iostream>
#include <cmath>
//#include <ctime>
using namespace std;
#define BUFFER_SIZE 320

unsigned long long seed;
static const long double Z = ( long double )1.0 / (1LL<<32);

long double buffer[BUFFER_SIZE];

//clock_t beg;
int main()
{
    long test;
    long tst;
    cin>>test;
    
    tst=1;
    cout.setf(ios::fixed,ios::floatfield);
	cout.precision(5);
    while(tst<=test)
    {
        long n;
        cin>>n>>seed;
        
        
        long double sa,sb,ma,mb;
        sa=ma=0;
        long round=n/BUFFER_SIZE;
        long i,j;
        long na=0;
        
        //beg=clock();
        
        long nb=BUFFER_SIZE;
        long double tmp;
        long double tsa,tma;
        
        
        for(i=1;i<=round;i++)
        {
            for(j=0,mb=0;j<BUFFER_SIZE;j++)
            {
                seed >>= 16;
                seed &= ( 1ULL << 32 ) - 1;
    
                seed *= seed;
                buffer[j]=seed * Z;
                
                mb+=buffer[j];
            }
            mb/=BUFFER_SIZE;
            for(j=0,sb=0;j<BUFFER_SIZE;j++)
            {
                tmp=buffer[j]-mb;
                sb+=tmp*tmp;
            }
            sb/=BUFFER_SIZE;
            
            tmp=na*ma+nb*mb;
            tma=tmp/(na+nb);
            tsa=(na*(sa+ma*ma)+nb*(sb+mb*mb)-tmp*tma)/(na+nb);
            
            
            
            ma=tma;
            sa=tsa;
            na+=BUFFER_SIZE;
        }
        nb=n%BUFFER_SIZE;
        if(nb>0)
        {
            for(i=0,mb=0;i<nb;i++)
            {
                seed >>= 16;
                seed &= ( 1ULL << 32 ) - 1;
    
                seed *= seed;
                buffer[i]=seed * Z;
                
                mb+=buffer[i];
            }
            mb/=nb;
            for(j=0,sb=0;j<nb;j++)
            {
                tmp=buffer[j]-mb;
                sb+=tmp*tmp;
            }
            sb/=nb;
            
            tmp=na*ma+nb*mb;
            tma=tmp/(na+nb);
            tsa=(na*(sa+ma*ma)+nb*(sb+mb*mb)-tmp*tma)/(na+nb);
            
            ma=tma;
            sa=tsa;
            
            
        }
        
        
        cout<<"Case #"<<tst<<": "<<(long double)sqrt(sa)<<endl;
        //cout<<clock()-beg<<endl;
        tst++;
    }
        
}

Observer · Post by **Observer** » Thu Aug 18, 2005 12:08 pm

Hi,

Looking for repeated numbers is a good idea to speed up. However, don't just compare generated numbers with given seed. Think about something else.

A big hint: note that the random number generator is somewhat biased.

sunnycare · Post by **sunnycare** » Thu Aug 18, 2005 12:19 pm

about math?
somewhat biased?

a bit more clearly please??
thanks

Observer · Post by **Observer** » Thu Aug 18, 2005 12:31 pm

Hi,

I've sent you a PM. Pls check that.

Don't wanna put spoilers here

sunnycare · Post by **sunnycare** » Fri Aug 19, 2005 10:32 am

thanks ,i have send you my reply

still confused

Emilio · Post by **Emilio** » Sun Aug 28, 2005 3:50 am

Hi!

Could anyone confirm this test cases?
And, if is possible, could anyone post any cases more?

Thanks!

input:

Code: Select all

41
2 16777216
2 4294967296
10000000 0
2 2147483648
10000 382759482784958
2 16777216
2 4294967296
10000000 0
2 2147483648
10000000 382759482784958
10000000 100012312311
123478 1238491234923
234 239401234
1 1
1 0
1 2
1 12341234
1 234234
213489 1238491234
234848 12341234
2345234 34544444444444
10000000 12341234
2345234 234523455555555
2345234 234525455555211
8689688 234523452345234
2458584 23452834858885
3458958 48293939495959
3848586 39495948383812
1111111 11111111111111
2345885 12348413288888
1234812 12348238488882
4389499 7777777777777
2374892 3848848848848
3882882 234832834
2348923 2349
28349   1000
12312   12333
12390   1233
8484888 23423423423444
2349999 2349949949499
9999999 99999999999999

output:

Code: Select all

Case #1: 0.00001
Case #2: 0.00000
Case #3: 0.00000
Case #4: 0.09375
Case #5: 1283729051.97967
Case #6: 0.00001
Case #7: 0.00000
Case #8: 0.00000
Case #9: 0.09375
Case #10: 76207822.73402
Case #11: 59904563.83775
Case #12: 929805899.63476
Case #13: 0.00020
Case #14: 0.00000
Case #15: 0.00000
Case #16: 0.00000
Case #17: 0.00000
Case #18: 0.00000
Case #19: 0.00018
Case #20: 0.00000
Case #21: 155101785.50391
Case #22: 0.00000
Case #23: 212045271.16418
Case #24: 60945782.01811
Case #25: 86269212.92848
Case #26: 190375740.31326
Case #27: 263576402.57860
Case #28: 222358956.13312
Case #29: 348571723.75213
Case #30: 38944756.42687
Case #31: 345224528.30211
Case #32: 66049058.13584
Case #33: 138875137.99072
Case #34: 0.00000
Case #35: 0.00000
Case #36: 0.00000
Case #37: 0.00000
Case #38: 0.00000
Case #39: 102242454.24967
Case #40: 169280278.11339
Case #41: 112433935.70919

sunnycare · Post by **sunnycare** » Tue Aug 30, 2005 3:20 pm

output from my accept code:
may be it is helpful

Code: Select all

Case #1: 0.00001
Case #2: 0.00000
Case #3: 0.00000
Case #4: 0.09375
Case #5: 1283729051.97967
Case #6: 0.00001
Case #7: 0.00000
Case #8: 0.00000
Case #9: 0.09375
Case #10: 76174674.36394
Case #11: 59904563.83775
Case #12: 866974033.35292
Case #13: 0.00020
Case #14: 0.00000
Case #15: 0.00000
Case #16: 0.00000
Case #17: 0.00000
Case #18: 0.00000
Case #19: 0.00018
Case #20: 0.00000
Case #21: 154819151.81345
Case #22: 0.00000
Case #23: 211325314.69601
Case #24: 60945782.01811
Case #25: 86220116.49176
Case #26: 189850674.44204
Case #27: 262191084.32908
Case #28: 221530779.38150
Case #29: 345373597.18507
Case #30: 38940382.45684
Case #31: 342123530.49527
Case #32: 66026810.32032
Case #33: 138673718.52556
Case #34: 0.00000
Case #35: 0.00000
Case #36: 0.00000
Case #37: 0.00000
Case #38: 0.00000
Case #39: 102162207.23129
Case #40: 168915285.73879
Case #41: 112325181.32280

Emilio · Post by **Emilio** » Wed Aug 31, 2005 8:07 pm

Thanks sunnycare!

I have got AC!

I could have made a force brute program to check my output.
Sometimes I seem stupid.

xiaomengxian · Post by **xiaomengxian** » Thu Apr 26, 2007 3:13 am

I've tried my best but I can't read the C code in the problem statement... Could anyone translate it into Pascal? Thanx in advance..