Salom. Kim buSamsung Galaxy smartfonimdan yuborildi. -------- Asl xabar --------Kimdan: porker2008 <[email protected]> Sana: 16/08/22 09:31 (GMT+05:00) Kimga: Google Code Jam <[email protected]> Mavzu: [code jam] Re: Intranets (2022 Round 1C) I might be wrong, but I think there is an error in the analysis.i itself can only goes from k to floor(m/2), since the size of a matching in a graph of M node cannot exceed floor(m/2).This should solve your issue where m - 2*j can go negative.在2022年8月15日星期一 UTC-7 05:28:35<[email protected]> 写道：Thanks, that solution works.Now I'm confused again on the solution for test set 2.The formula for g(x) is a product of Fraction(1, math.comb(m, 2)-math.comb(m-2*j, 2))where j goes from 1 to i, but then i itself goes from k to m. This means that m-2*j can go negative, e.g. with k=2 and m=5, we should have i=2, 3, 4, 5, and when i=3, we should have j=1, 2, 3. When i=3 and j=3, m-2*j=5-2*3=-1. How should this case be handled/avoided?On Thursday, 11 August 2022 at 20:19:56 UTC+1 porker2008 wrote: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 helpsCase #1: 3/7Case #2: 4/7Case #3: 1/21在2022年8月8日星期一 UTC-7 08:15:09<[email protected]> 写道：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/71fd2790-4863-4c58-9d19-3828efea1207n%40googlegroups.com. -- -- 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/636a4fd1.050a0220.8ef68.b6e9%40mx.google.com.
