## 11021 - Tribbles

Moderator: Board moderators

### 11021 - Tribbles

Last edited by sclo on Wed Apr 05, 2006 9:47 am, edited 1 time in total.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

First try to compute the probability that all descendants of one tribble will be dead after m generations, and then the general problem is easily solved. (As an aside, I had also to make use of the fact that the answer must be accurate only to within 10^-6 to avoid TLE during the contest).
david
Learning poster

Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

That probability can be computed accurately with a simple DP (just don't use long doubles, it's too acurate and you'll get WA )

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

To Krzyszof: really!? That's not good. I'll look into it.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

thanks, I'll try the dp.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

Abednego wrote:To Krzyszof: really!? That's not good. I'll look into it.

I can send you my code if you want.

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

Can anyone help me? I know the problem is solved with DP but my probability skills are limited and I can't think a way of solving it properly! The only way I found that solves the problem is (or something very similar, i didn't coded it, just solved the sample input):

P(k, m) = p0^k + W(k,1)*P(1, m-1) + W(k,2)*P(2,m-1) + ... + W(k, k*(n-1))*P(k*(n-1), m-1);

Where:
- k, m, n, p are the same as in text
- P(k, m) is the probability of k Tribbles will be dead after m generations
- W(k, x) is the number of ways k Trilbbles can give birth to x Tribbles

For instance:

when n = 3, k = 2, m = 3;
P(2,3) = P(0, 2) + 2*P(1, 2) + 3*P(2, 2) + 2*P(3,2) + 1*P(4,2);
and:
P(4,2) = P(0,1) + 4*P(1,1) + 10*P(2,1) + ... + ?*P(8,1);

As you can see, the number of Tribbles and the combinations (W) grow a lot.

Is there a way where the problem is solved having to worry with fewer things? Please, any hint would be welcome.
Diego Caminha
New poster

Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil

Diego Caminha wrote:Can anyone help me? I know the problem is solved with DP but my probability skills are limited and I can't think a way of solving it properly! The only way I found that solves the problem is (or something very similar, i didn't coded it, just solved the sample input):

P(k, m) = p0^k + W(k,1)*P(1, m-1) + W(k,2)*P(2,m-1) + ... + W(k, k*(n-1))*P(k*(n-1), m-1);

Where:
- k, m, n, p are the same as in text
- P(k, m) is the probability of k Tribbles will be dead after m generations
- W(k, x) is the number of ways k Trilbbles can give birth to x Tribbles

For instance:

when n = 3, k = 2, m = 3;
P(2,3) = P(0, 2) + 2*P(1, 2) + 3*P(2, 2) + 2*P(3,2) + 1*P(4,2);
and:
P(4,2) = P(0,1) + 4*P(1,1) + 10*P(2,1) + ... + ?*P(8,1);

As you can see, the number of Tribbles and the combinations (W) grow a lot.

Is there a way where the problem is solved having to worry with fewer things? Please, any hint would be welcome.

I see where you're going with it, I originally thought of this dp but it is not going to work.

First, let P(k,m) be as above. First, we try to find the dp for P(1,m):
We can see that if m>=1 then P(1,m) = sum_{i=0}^{n-1} p_i * P(i,m-1).
and we define P(0,0) = 1, and P(k,0) = 0 for any k!=0.

Now try to find a relationship between P(k,m) and P(1,m) and you will finish this problem. (Hint: You don't need to define any functions other than P.)

It simplifies the notation if we assume 0^0 = 1.
sclo
Guru

Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm

Nice hint, sclo. I couldn't find a good way to give a hint without saying too much. You did it perfectly.
Let's hope Yury doesn't notice that I'm solving problems again.

Abednego
A great helper

Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA

After trying a lot I got it. So many things come to my mind but not the relationship between P(k, m) and P(1, m). When I finally understood it was really simple.

Thanks sclo.
Diego Caminha
New poster

Posts: 5
Joined: Wed Mar 16, 2005 1:40 am
Location: Brazil

I got P.E for this problem..
.. that was because I forgot to write the 'case' part.

printf("%.7lf\n",memo(M, K) );

But later I got WA, when I added 'Case'

printf("Case #%d: %.7lf\n",cases++, memo(M, K) );

The first printf() resulted P.E
but the second WA.

What could be the reason?

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

### Precision

I think I'm getting W.A.'s because of floating point precision, although I'm using long doubles all around, and pow() instead of multiplications =(

Can someone check my implementation, please?
New poster

Posts: 5
Joined: Tue Apr 04, 2006 8:42 am
Location: Florian

Try doubles.

Krzysztof Duleba
Guru

Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland

Still the same problem with doubles or floats, but I'm getting the right results here with my tests.

I am printing the numbers with fixed a precision of 8 (using iostream). Can it be a rounding problem?? Does the judge only ignore the numbers after the 7th place after the dot, or does it compare the whole number and check for error < 1e-6??
New poster

Posts: 5
Joined: Tue Apr 04, 2006 8:42 am
Location: Florian

### the two codes..

This is the code that gets P.E

Code: Select all
`#include<stdio.h>#include<math.h>int main() { int t, i; for( scanf("%d", &t); t--; ) {  scanf("%d %d %d", &n, &K, &M);  for(i=0;i<n;i++) scanf("%lf", &pro[i]);  for(i=1;i<=M;i++) dp[i] = -1;  printf("%.7lf\n", memo(M, K) ); } return 0;}`

And this one gets WA..

Code: Select all
`#include<stdio.h>#include<math.h>int main() { int t, i, cases = 1; for( scanf("%d", &t); t--; ) {  scanf("%d %d %d", &n, &K, &M);  for(i=0;i<n;i++) scanf("%lf", &pro[i]);  for(i=1;i<=M;i++) dp[i] = -1;  printf("Case #%d: %.7lf\n",cases++, memo(M, K) ); } return 0;}`

Both are identical codes, except in the 2nd one I added the 'Case #x: ", as I should', but got WA.. whereas in the first code i got P.E omitting 'Case #1: '..

Is this some sort of bug, or am i missing something..

sohel
Guru

Posts: 862
Joined: Thu Jan 30, 2003 5:50 am
Location: University of Texas at San Antonio

Next