The part2 only works if you are dealing with probability instead of the
actual count.
Here is a modification of your part2, which give you the correct
probability.
*from fractions import FractionT = int(input())for cas in range(T): m,
k0 = [int(s) for s in input().split(" ")] edges = m*(m-1)//2 dp =
[(k0+1)*[0] for _ in range(m+1)] dp[0][0] = 1 for j in range(m+1):
for k in range(k0+1): cnt = dp[j][k] if j < m-1
and k < k0: cntA = cnt*Fraction((m-j)*(m-j-1)//2,
(m-j)*(m-j-1)//2 + j*(m-j)) newj = j+2 newk =
k+1 dp[newj][newk] = dp[newj][newk]+cntA if j <
m: cntB = cnt*Fraction(j*(m-j), (m-j)*(m-j-1)//2 + j*(m-j))
newj = j+1 newk = k
dp[newj][newk] = dp[newj][newk] + cntB good = dp[m][k0]*
* print("Case #{}: {}".format(cas + 1, good)) *
It prints the expected probability when you run it against the sample test
cases. Hope it helps
*Case #1: 3/7Case #2: 4/7Case #3: 1/21*
在2022年8月8日星期一 UTC-7 08:15:09<gyorok...@gmail.com> 写道：
> Hi,
>
> I can't figure this out, even after reading the analysis. Based on the
> first part I came up with this code:
>
> m, k0 = [int(s) for s in input().split(" ")]
> edges = m*(m-1)//2
> dp = [[(k0+1)*[0] for _ in range(m+1)] for _ in range(edges+1)]
> dp[0][0][0] = 1
> for i in range(edges):
> for j in range(m+1):
> for k in range(k0+1):
> cnt = dp[i][j][k]
> if j < m-1 and k < k0:
> cntA = cnt*(m-j)*(m-j-1)//2
> newj = j+2
> newk = k+1
> dp[i+1][newj][newk] = (dp[i+1][newj][newk]+cntA)%MOD
>
> if j < m:
> cntB = cnt*j*(m-j)
> newj = j+1
> newk = k
> dp[i+1][newj][newk] = (dp[i+1][newj][newk]+cntB)%MOD
>
> cntC = cnt*(j*(j-1)//2-i)
> newj = j
> newk = k
> dp[i+1][newj][newk] = (dp[i+1][newj][newk]+cntC)%MOD
>
> good = dp[edges][m][k0]
>
> This works well for part 1 but for part 2 I get memory limit exceeded.
> Then the next step in the analysis suggests to remove i from the index
> and only care about the first two types of edges, which would correspond to
> this code:
>
> dp = [(k0+1)*[0] for _ in range(m+1)]
> dp[0][0] = 1
> for j in range(m+1):
> for k in range(k0+1):
> cnt = dp[j][k]
> if j < m-1 and k < k0:
> cntA = cnt*(m-j)*(m-j-1)//2
> newj = j+2
> newk = k+1
> dp[newj][newk] = (dp[newj][newk]+cntA)%MOD
> if j < m:
> cntB = cnt*j*(m-j)
> newj = j+1
> newk = k
> dp[newj][newk] = (dp[newj][newk]+cntB)%MOD
> good = dp[m][k0]
>
> However this is clearly wrong, e.g. for the input 5 2 I get good=180
> instead of the correct good=1555200. So what is the correct
> interpretation of the optimization for part 1?
>
> Also for part 2 it casually mentions that it's a convolution and we can
> use FFT... but as I never really dug into those concepts this is not very
> useful.
>
> Regards,
> Péter
>
--
-- You received this message because you are subscribed to the Google Groups
Code Jam group. To post to this group, send email to
google-code@googlegroups.com. To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com. For more options, visit this group at
https://groups.google.com/d/forum/google-code?hl=en
---
You received this message because you are subscribed to the Google Groups
"Google Code Jam" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to google-code+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/c4ddb33d-2a4c-442e-a33d-b237f4c37a9bn%40googlegroups.com.
