10431 - Normal Distribution

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10431 - Normal Distribution

Post by cytse » Sat Feb 08, 2003 8:43 am

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Feb 08, 2003 11:34 pm

It means n*Q(z) (but my team had a hard time to understand it during the contest, we got it only by trying).

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

Post by cytse » Sun Feb 09, 2003 5:20 pm

Thanks. It seems that the most difficult part of this problem is to guess the meaning of the answers. :roll:

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

10431 any data?

Post by lowai » Thu Jun 05, 2003 10:01 am

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
readln(n);
if n = 0 then break;

inc(caseno);
sum := 0; sigma := 0;
for i := 1 to n do
begin
read(s);
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);

readln(nq);
while nq > 0 do
begin
read(z);
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

Post by Red Scorpion » Fri Jul 11, 2003 8:23 am

huuuu..... :evil: :evil: :evil:
I always got WA, on this problem.

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

Please help.... :( :( :( :(

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

Help!

Post by Pier » Fri Aug 01, 2003 6:26 am

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);
readln(input,n);
m:= 0; s:= 0;
for i:= 1 to n do
begin
read(input,t);
m:= m+t;
s:= s+ sqr(t);
end;
readln(input);
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);
readln(input,qi);
for i:= 1 to qi do
begin
read(input,z);
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;
readln(input);
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!

Post by windows2k » Tue Aug 05, 2003 6:34 am

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

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Tue Aug 05, 2003 6:41 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?
:lol:

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

Post by windows2k » Tue Aug 05, 2003 6:50 pm

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?
:lol:
I don't know . My program runs Output Exceed :(

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

Post by little joey » Tue Aug 05, 2003 7:12 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)).

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

Post by Pier » Sat Aug 16, 2003 6:13 am

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!

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

Post by little joey » Sat Aug 16, 2003 8:23 am

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

Post by BiK » Fri Oct 22, 2004 8:03 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)));
This can be made simpler:

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.

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

Post by Pier » Sat Oct 23, 2004 5:43 am

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!

Post Reply

Return to “Volume 104 (10400-10499)”