tag:blogger.com,1999:blog-29632375.post4307913312763279385..comments2023-04-30T13:56:10.923-07:00Comments on vexorian's blog: Thoughts after SRM 508Unknownnoreply@blogger.comBlogger9125tag:blogger.com,1999:blog-29632375.post-53982800000325899832011-06-06T07:15:57.650-07:002011-06-06T07:15:57.650-07:00Since all Rs are equal in div2 1000. Then for ever...Since all Rs are equal in div2 1000. Then for every 1 bit in R there can be only one Ai that is equal to R until that prefix. <br /><br />For example, let us say that R is 101001. And N is 3<br /><br />Then you have some possibilities:<br /><br />a) The last 1 bit of R to be used is the left-most one.<br /><br />100???<br />0?????<br />0?????<br /><br />Each ? sign can be 0 or 1 (but note that you can only have one 1 per row). Note that we have to multiply by three, because the 100??? row can be any of the three ones.<br /><br />b) The last 1 bit of R to be used is the second one from the left.<br /><br />101000<br />0?0???<br />0?0???<br /><br />c) No 1 bit from R is used:<br /><br />0?????<br />0?????<br />0?????<br /><br />syco's solution tries each of these possibilities and uses combinatorics.<br /><br /><a href="http://apps.topcoder.com/wiki/display/tc/SRM+508" rel="nofollow">Editorial released</a>vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-15268853418125591762011-06-06T04:38:23.097-07:002011-06-06T04:38:23.097-07:00For the problem YetAnotherORProblem2, I found syco...For the problem YetAnotherORProblem2, I found syco's solution is amazing, but I cannot figure it out yet.<br /><br />Here is my rewrite of his solution:<br /><br />int countSequences(int N, int R) {<br /> long long ans = 1, x = 1;<br /> for ( ; R > 1; R /= 2) {<br /> if (R & 1) ans = (ans + N * x) % MOD;<br /> else ans = N * ans % MOD;<br /> x = x * (N + 1) % MOD;<br /> }<br /> return (x + N * ans) % MOD;<br />}JYhttps://www.blogger.com/profile/06133384347588330758noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-60023896788999332652011-06-05T17:20:59.254-07:002011-06-05T17:20:59.254-07:00I noticed it is impossible to explain it easily.
...I noticed it is impossible to explain it easily.<br /><br />In theory, last night I finished the editorial in which I really do a huge effort to explain it, and it should be good, but before that the editorial has to be uploaded. It is probably not many hours away of being posted though.<br /><br />@bloops: Thanks man.vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-66128622040418325342011-06-04T10:58:45.183-07:002011-06-04T10:58:45.183-07:00I can't grasp the idea behind your 500. Suppos...I can't grasp the idea behind your 500. Suppose the input is {5,9}. :)<br /><br />If the second bit is set in first number than the 3rd bit can not be set.<br />If third or second bit is set in the second number than 4th bit can not be set. Your solution takes this into account (you check if the bit is 0 in R[i]) but I fail to see why it is correct.Muxecoidhttps://www.blogger.com/profile/01245041086555036600noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-66738617081629256852011-06-03T21:18:43.319-07:002011-06-03T21:18:43.319-07:00Congratulations for your maximum rating! Your expl...Congratulations for your maximum rating! Your explanations are really helpful. Thanks for posting them. :)bloopsnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-90567565070903663722011-06-03T09:16:34.765-07:002011-06-03T09:16:34.765-07:00Don't make me turn anonymous posting off.Don't make me turn anonymous posting off.vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-25546383895413361632011-06-03T08:35:06.892-07:002011-06-03T08:35:06.892-07:00MADOKA IS WATCHING YOU!MADOKA IS WATCHING YOU!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-43325360627659089522011-06-02T16:33:24.353-07:002011-06-02T16:33:24.353-07:00You believe well.You believe well.vexorianhttps://www.blogger.com/profile/09588316922172217808noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-36912795645336825572011-06-02T12:25:35.821-07:002011-06-02T12:25:35.821-07:00I believe this post is about SRM 508, not 507.I believe this post is about SRM 508, not 507.Anonymousnoreply@blogger.com