I don't quite understand why do you consider a[i][j] = 0, if i < j [I'm considering that a[i][j] means state where team A have done i goals and team B have done j goals]. I think it would be more correct if it were three states
dp[i][j][k], where team A have done i goals, team B have done j goals, and we have had already k*5 minutes played. so dp[0][0][0] = 1.0, but you would need to consider as well the possibility that both teams score in that interval, so the DP would be dp[i][j][k] = (pA/100 * (1- pB/100))*dp[i][j-1][k-1] + (pB/100 * (1 - pA/100))*dp[i-1][j][k-1] + pA/100 * pB/100 * dp[i-1][j-1][k-1]; and this would solve. On 31 October 2011 09:01, mohit verma <[email protected]> wrote: > Hey guys , > I am trying to solve a simple DP problem : > http://community.topcoder.com/stat?c=problem_statement&pm=10033 SRM 422 > division 2 level 2. > > I have derived a recurrence for prime scores of player A like this > > a[i][j] = 0 if i<j > pow(p,i) if i==j > (~p) * a[i-1][j] + p * a[i][j-1] > > where i : interval (max 18 ) , j : sum ( max 18) > > Now after populating entries in this matrix , for each prime score : 2 , > 3 , 5 ... so on upto 17 i find the probability of A for all possible > prime scores. > I am not saying that this recurrence is to solve this problem. > > Can someone please tell me if this recurrence is right or not ? > > -- > Mohit > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- Renato Parente MSc candidate @ IME - Universidade de São Paulo -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
