11021 - Tribbles

[sclo]

got AC already.

[david]

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).

[Krzysztof Duleba]

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 )

[Abednego]

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

[sclo]

thanks, I'll try the dp.

[Krzysztof Duleba]

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

I can send you my code if you want.

[Diego Caminha]

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.

[sclo]

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.

[Abednego]

Nice hint, sclo. I couldn't find a good way to give a hint without saying too much. You did it perfectly.

[Diego Caminha]

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.

[sohel]

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?

[tadeu]

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?

[Krzysztof Duleba]

Try doubles.

[tadeu]

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??

[sohel]

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