Moderator: Board moderators

jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

Can any body explain the algo....... Is it pure math....??
I try calculating the probabilities ... but i always endup getting wrong answer

minhaz
New poster
Posts: 5
Joined: Sat Oct 19, 2002 4:20 am
Contact:
it is a problem of probability of statistics.so think it from statistics view

minhaz
New poster
Posts: 5
Joined: Sat Oct 19, 2002 4:20 am
Contact:
it is a problem of probability of statistics.so think it from statistics view

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe

### 10417

2
2 0 0 0 0
0.5 0.0 0.0 0.5 0.0
0.4 0.0 0.2 0.4 0.0
Is it

Code: Select all

``1 0.556``
or

Code: Select all

``1 0.500``
???

Tobias

Caesum
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:
1 0.500

Tobbi
New poster
Posts: 17
Joined: Sat Jan 25, 2003 3:06 pm
Location: Europe
Thanks for the lightning fast response, but then I've no clue what's wrong with my code... I'm just checking all possible distributions of the gifts and multiply up the respective probabilities:

[cpp]#include <iostream>
#include <stdio.h>

int num, n, t;
double prob;
double res;
int bestpos;

double calc(int fr) { // friend
if (fr>=n) return 1.0; // all friends checked
double P=0.0;
for(int i=0;i<5;i++) { // for each kind of gift
if (num) {
--num;
P += prob[fr] * calc(fr+1); // recursive call
++num;
}
if (!fr) { // best friend
res = P;
if (!bestpos || res[bestpos-1]<P) bestpos=i+1;
P = 0.0;
}
}
return P;
}

int main() {
cin>>t; // number of testcases (1<=t<=10)
while(cin>>n) { // number of friends (1<=n<=12)
t--;
bestpos=0;
for(int i=0;i<5;i++) cin >> num; // read number of gifts of each kind
for(int j=0;j<n;j++) for(int i=0;i<5;i++) cin >> prob[j]; // read probabilities

calc(0); // start rec. calc with first friend

printf( "%d %0.3f\n", bestpos, res[bestpos-1]/(res+res+res+res+res)/num[bestpos-1]);
}
return 0;
}[/cpp]

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
I don't know how to solve the problem at all Could someone give me some hints? newtype feng
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm
Tobbi wrote:Thanks for the lightning fast response, but then I've no clue what's wrong with my code... I'm just checking all possible distributions of the gifts and multiply up the respective probabilities:

i think your max is the one not div num.
if div it result will be different.
My english is poor,hope this will help.
I like AC

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
More than one year since the last post - let me revive that one! I finally got this one AC after lots of WAs. The essential point is not to write "1 0.251" when you could write "2 0.251".

Personally, I think this is misleading and incorrect, as box 1 with a value of 0.2514 is definitely a better choice than box 2 with 0.2505.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

could somebody explain the sample I/O ..?
I'm so poor at math. .;

input

Code: Select all

``````2
1 0 0 1 0
0.5 0.0 0.0 0.5 0.0
0.4 0.0 0.5 0.1 0.0
``````
output

Code: Select all

``````4 0.800
``````
thanks.. ^_^
Last edited by helloneo on Tue May 22, 2007 8:09 am, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
In the first sample case, there are two guests.
The 1st person (your friend), can bring a box of type A or D with equal probability.
The 2nd person can bring boxes: A with probability 0.4, C - 0.5, D - 0.1.
You also know, that there is 1 box of type A, and 1 box of type D.

Let's make a table, which lists all possible combinations of gifts, which could be brought by the guests, and their probabilities:

Code: Select all

``````1st person's box  2nd person's box  Probability
A                 A                 0.5*0.4 = 0.20
A                 C                 0.5*0.5 = 0.25
A                 D                 0.5*0.1 = 0.05
D                 A                 0.5*0.4 = 0.20
D                 C                 0.5*0.5 = 0.25
D                 D                 0.5*0.1 = 0.05
``````
Of all these cases, you are only interested in those, in which there's one box of type A and one box of type D, namely:

Code: Select all

``````1st 2nd Probability
A   D   0.05
D   A   0.20
``````
Now, if you choose a box of type A, the chances that it's from your friend (the 1st person) are: (1*0.05 + 0*0.20) / (0.05+0.20) = 0.20.

If you choose a box of type D, you'll pick the right box with probability: (0*0.05 + 1*0.20) / (0.05+0.20) = 0.80.

So, in order to maximize the probability of picking a box from your friend, you should pick a box of type D (type #4), and the probability will be: 80%.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
what a nice explanation..
thanks a lot.. ^^

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am