10417 - Gift Exchanging

[jaivasanth]

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

please help

[minhaz]

it is a problem of probability of statistics.so think it from statistics view

[minhaz]

it is a problem of probability of statistics.so think it from statistics view

[Tobbi]

Could anyone please tell me, what's the correct answer for

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

???

Thanks in advance,
Tobias

[Caesum]

1 0.500

[Tobbi]

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[5], n, t;
double prob[5][12];
double res[5];
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[0]+res[1]+res[2]+res[3]+res[4])/num[bestpos-1]);
}
return 0;
}[/cpp]

[windows2k]

I don't know how to solve the problem at all
I am bad at math
Could someone give me some hints?

[newtype feng]

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.

[Christian Schuster]

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]

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.. ^_^

[mf]

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]

what a nice explanation..
thanks a lot.. ^^

[daveon]

Strange..., they might have fixed this as I always choose the one with the smallest box.