## 10431 - Normal Distribution

Moderator: Board moderators

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:

### 10431 - Normal Distribution

What is the "percentage of population T falling in Q(z) area" in the output? I don't understand what it means.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It means n*Q(z) (but my team had a hard time to understand it during the contest, we got it only by trying).

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Thanks. It seems that the most difficult part of this problem is to guess the meaning of the answers.

lowai
New poster
Posts: 48
Joined: Mon Apr 29, 2002 1:26 pm

### 10431 any data?

can anyone provide some test data of 10431 (Normal Distribution)?
thanks.
my code goes here.
[pascal]
const
p = 0.2316419;
b1 = 0.319381530;
b2 = -0.356563782;
b3 = 1.781477937;
b4 = -1.821255978;
b5 = 1.330274429;
var
i, n : longint;
x : integer;
s : double;
sum : double;
sigma, z, miu : double;
caseno : integer;
t, c, r, qz : double;
nq : integer;
begin
caseno := 0;
while not eof do
begin
if n = 0 then break;

inc(caseno);
sum := 0; sigma := 0;
for i := 1 to n do
begin
sum := sum + s;
sigma := sigma + s * s;
end;
sum := sum / n;
sigma := sigma - n * sqr(sum);
if n > 1 then
begin
sigma := sigma / (n-1);
sigma := sqrt(sigma);
end
else sigma := 0;

writeln('Data Set #', caseno);
writeln('Mean = ', sum : 0 : 4);
writeln('Standard Deviation = ', sigma : 0 : 4);

while nq > 0 do
begin
z := (z - sum) / sigma;
t := 1 / (1 + p * abs(z));
c := 1 / sqrt(2 * pi) * exp(-z*z/2);
r := 0;
z := t; r := r + b1 * z;
z := z * t; r := r + b2 * z;
z := z * t; r := r + b3 * z;
z := z * t; r := r + b4 * z;
z := z * t; r := r + b5 * z;
qz := c * r;
writeln('P(z) = ', 1-qz : 0 : 4, ', Q(z) = ', qz : 0 : 4,', T = ', n * qz : 0 : 4);

dec(nq);
end;
writeln;
end;
end.
[/pascal]

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
huuuu.....
I always got WA, on this problem.

I use double for calculation. Is there any tricky input...

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:

### Help!

Can anyone help me with this problem?

Here's my code:

[pascal]
Const
p = 0.2316419; b1= 0.319381530; b2=-0.356563782;
b3= 1.781477937; b4=-1.821255978; b5= 1.330274429;

Var
c,i,n,qi: integer;
f,m,qr,s,t,z: real;

Begin
c:= 1;
While (not eof(input)) do
begin
if c<>1 then writeln(output);
m:= 0; s:= 0;
for i:= 1 to n do
begin
m:= m+t;
s:= s+ sqr(t);
end;
s:= sqrt((n*s -sqr(m))/(n*(n-1)));
m:= m/n;
writeln(output,'Data Set #',c);
writeln(output,'Mean = ',m:0:4);
writeln(output,'Standard Deviation = ',s:0:4);
for i:= 1 to qi do
begin
z:= (z-m)/s;
t:= 1/(1+p*abs(z));
f:= (1/sqrt(2*pi))*exp(-z*z/2);
qr:= f*t*(b1 +t*(b2 +t*(b3 +t*(b4 +t*b5))));
writeln(output,'P(z) = ',(1-qr):0:4,', Q(z) = ',qr:0:4,', T = ',n*qr:0:4);
end;
Inc(c);
end;
End.
[/pascal]

I changed the last writeln for writeln('Testing!'); and I got WA on the same time, which means I'm failing even with the first test!

Any help aprecciated!

PS: I have also tried changing real for extended and integer for longint, but that didn't helped.
There are 10 kind of people on this world: those who understand binary and those who don't!

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

### Re: Help!

Pier wrote:Can anyone help me with this problem?

Any help aprecciated!

PS: I have also tried changing real for extended and integer for longint, but that didn't helped.
Try to This input
1
10
2
10 20
I don't know if this is useful

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am
Whats your output fot the above test case?

I got standard deviation = Nan.

SD = 1/(n-1) * sum sqrt(xi-Mean) .
SD = 1/0 * 0.

Any hint?

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
Red Scorpion wrote:Whats your output fot the above test case?

I got standard deviation = Nan.

SD = 1/(n-1) * sum sqrt(xi-Mean) .
SD = 1/0 * 0.

Any hint?
I don't know . My program runs Output Exceed

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Try:

Code: Select all

``````1
10
3
5 10 15
5
10 10 10 10 10
3
5 10 15
``````
You can find the correct answers if you imagine how the distribution curve looks in these cases.
There is no data like the second case in the judges input (my first program didn't handle it, but got AC), although I think there should be.

There is an error in the problem description:
and then percentage of population `T' falling in Q(z) area
It should be the 'number' (n*Q(z)) and not the 'percentage' (100*Q(z)).

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
Here are my answers for those inputs. Are these correct?

Data Set #1
Mean = 10.0000
Standard Deviation = 0.0000
P(z) = 1.0000, Q(z) = 0.0000, T = 0.0000
P(z) = 0.0000, Q(z) = 1.0000, T = 1.0000
P(z) = 1.0000, Q(z) = 0.0000, T = 0.0000

Data Set #2
Mean = 10.0000
Standard Deviation = 0.0000
P(z) = 1.0000, Q(z) = 0.0000, T = 0.0000
P(z) = 0.0000, Q(z) = 1.0000, T = 5.0000
P(z) = 1.0000, Q(z) = 0.0000, T = 0.0000
There are 10 kind of people on this world: those who understand binary and those who don't!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
No, they're not. Q(z) is the area under the normal curve left of point z (figure 2 in the problem description is wrong), so for any z1>z2 it holds that Q(z1)>=Q(z2) (and P(z1)<=P(z2)).
In the two cases I gave, the normal curve is a spike located at z=10, so Q(z) should be 1 for z>=10 and 0 for z<10 (the step function).

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Hi Pier,

Your program is fine, it's just that you lose precision when you compute the deviation. Your formula is:

Code: Select all

``s:= sqrt((n*s -sqr(m))/(n*(n-1)));``

Code: Select all

``s:= sqrt((s -m*m/n)/(n-1));``
My formula was also not in the simplest form and I was constantly getting WA. But when I changed it like above, I got ACC.

Pier
New poster
Posts: 38
Joined: Thu Mar 27, 2003 9:12 pm
Location: Aguascalientes, Mexico
Contact:
Thanks a lot! I would never thought of that!
There are 10 kind of people on this world: those who understand binary and those who don't!