Re: [code jam] Re: Intranets (2022 Round 1C)
Salom. Kim buSamsung Galaxy smartfonimdan yuborildi.
Asl xabar Kimdan: porker2008 Sana:
16/08/22 09:31 (GMT+05:00) Kimga: Google Code Jam
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 写道：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 写道：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.
--
-- You re
[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 写道：
> 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] = 1for 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+2newk = k+1*
>>
>> *dp[newj][newk] = dp[newj][newk]+cntAif j <
>> m:cntB = cnt*Fraction(j*(m-j), (m-j)*(m-j-1)//2 + j*(m-j))*
>>
>>
>> *newj = j+1newk = 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 写道：
>>
>>> 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
[code jam] Re: Intranets (2022 Round 1C)
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] = 1for 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+2newk = k+1*
>
> *dp[newj][newk] = dp[newj][newk]+cntAif j <
> m:cntB = cnt*Fraction(j*(m-j), (m-j)*(m-j-1)//2 + j*(m-j))*
>
>
> *newj = j+1newk = 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 写道：
>
>> 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/7a936a92-353c-4c69-9d51-daf6f960f5bdn%40googlegroups.com.
[code jam] Re: Intranets (2022 Round 1C)
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)//2dp =
[(k0+1)*[0] for _ in range(m+1)]dp[0][0] = 1for 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+2newk =
k+1dp[newj][newk] = dp[newj][newk]+cntAif j <
m:cntB = cnt*Fraction(j*(m-j), (m-j)*(m-j-1)//2 + j*(m-j))
newj = j+1newk = k
dp[newj][newk] = dp[newj][newk] + cntBgood = 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 写道：
> 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.
