10417 - Gift Exchanging

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
jaivasanth
New poster
Posts: 10
Joined: Tue Nov 26, 2002 4:19 pm

10417 - Gift Exchanging

Post by jaivasanth » Tue Nov 26, 2002 5:49 pm

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
New poster
Posts: 5
Joined: Sat Oct 19, 2002 4:20 am
Location: Dhaka,Bangladesh
Contact:

Post by minhaz » Sat Nov 30, 2002 6:17 pm

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
Location: Dhaka,Bangladesh
Contact:

Post by minhaz » Sat Nov 30, 2002 6:19 pm

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

Post by Tobbi » Sat Jan 25, 2003 3:12 pm

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
Experienced poster
Posts: 225
Joined: Fri May 03, 2002 12:14 am
Location: UK
Contact:

Post by Caesum » Sat Jan 25, 2003 8:32 pm

1 0.500

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

Post by Tobbi » Sun Jan 26, 2003 1:59 am

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
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Wed Jul 02, 2003 8:23 am

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

newtype feng
New poster
Posts: 8
Joined: Thu Jul 31, 2003 2:36 pm

Post by newtype feng » Sun Sep 05, 2004 4:51 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

User avatar
Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

Post by Christian Schuster » Thu Dec 08, 2005 2:42 pm

More than one year since the last post - let me revive that one! :D

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

10417 - Gift Exchanging

Post by helloneo » Thu Jan 26, 2006 4:29 pm

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:

Post by mf » Thu Jan 26, 2006 5:39 pm

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

Post by helloneo » Thu Jan 26, 2006 6:32 pm

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

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

Post by daveon » Sun Jul 30, 2006 4:14 pm

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

Post Reply

Return to “Volume 104 (10400-10499)”