tag:blogger.com,1999:blog-29632375.post2660466842899531705..comments2015-07-26T10:48:18.008-07:00Comments on vexorian's blog: SRM 555: 5555555555555555555555Unknownnoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-29632375.post-57785157028994256442012-09-11T08:25:15.824-07:002012-09-11T08:25:15.824-07:00The problem statement asks you to count the number...The problem statement asks you to count the number of ways to assign the muddy road. So that the NUMBER OF WAYS to move from 0 to N-1 is <b>EVEN</b>. <br /><br />So when I say parity, I mean the piirty OF the number of ways.<br /><br />It is the same as saying "Calculate the number of ways" modulo 2.<br /><br />So in fact f(x) is 0 if the number of ways to move from x to n-1 is even and 1 if it is odd.<br /><br />When you see it as parity, then you can see that making a certain road muddy will make its number of ways to go from that road to n-1 ZERO and zero is even, so the parity is 0. Thus making a road segment muddy is the same as forcing the parity (the result of f(x) ) to be 0.<br /><br />Otherwise, if we do not make the road segment muddy, then the parity of the number of ways to go from x to n-1 depends on : f(x+1) and f(x+2). Which takes us to the dp:<br /><br />dp[x][m][p1][p2]<br /><br />p1 is f(x+1) and p2 is f(x+2). So they are used to calculate the parity of f(x) <i>in case</i> we do not make the road muddy.<br /><br />It means we have two choices:<br />* Make road x muddy: f(x) becomes 0 and m is reduced by 1.<br />* Do not make road x muddy: f(x) = ( f(x+1) + f(x + 2) ) % 2 = (p1 + p2)%2, m stays the same.<br /><br />f(x) and p1 will become p1 and p2 for the next case.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-36831705303930711492012-09-11T08:16:22.775-07:002012-09-11T08:16:22.775-07:00Hi Vexorian,
I still don't understand SRM 555...Hi Vexorian,<br /><br />I still don't understand SRM 555 Div 2 Hard. What does parity have to do with finding the number of ways?<br />For prob statement N=10 and muddyroads as 4, I counted the VALID number of ways you can have 4 muddy roads and be able to get through to the friend's house as 5. Do we also count the last 1 b/c the other 64 ways are INVALID? Also, I did a quick test with how many ways you can have 4 muddy roads in 8 slots, and came up with 70?<br /><br />Please explain?<br /><br />Thanks,<br />tm3Tm3dantesnoreply@blogger.com