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<gyorok...@gmail.com> 写道：
> 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 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/71fd2790-4863-4c58-9d19-3828efea1207n%40googlegroups.com.
