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
[email protected]. To unsubscribe from this group, send email to
[email protected]. 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 [email protected].
To view this discussion on the web visit
https://groups.google.com/d/msgid/google-code/3cf2f170-95f2-4a95-a048-7ee338e2867cn%40googlegroups.com.
