tag:blogger.com,1999:blog-31847281.post7242884474853421518..comments2023-04-10T02:40:58.057-07:00Comments on Entropy always increases: ICPC Problem H: PachinkoUnknownnoreply@blogger.comBlogger4125tag:blogger.com,1999:blog-31847281.post-38585212310363061232015-01-10T09:43:25.710-08:002015-01-10T09:43:25.710-08:00Oh, wait a minute. I think I see the issue. I was ...Oh, wait a minute. I think I see the issue. I was - naively - trying to compute the absorption probabilities for all initial states to all absorbing states (of which there are over 8,000 for the largest test case), then obtain the aggregate absorption probabilities by summing over the start states.<br /><br />After reading SnapDragon's post, I realize that you instead compute the expected number of times the chain is in a state directly via a linear system of equations with only one right-hand side, rather than 20x8000 individual probabilities. That should fit the time envelope.Godmar Backhttps://www.blogger.com/profile/05064247891002006433noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-8166975681603472152015-01-09T10:40:37.721-08:002015-01-09T10:40:37.721-08:00Can you give a hint as to what representation you&...Can you give a hint as to what representation you're using for M and b?<br /><br />I tried Gaussian with a COO-style representation for both, along with column indices, but can't get it under 1:22m for test2.in. Though (I-M) stays reasonable sparse, the 'b' side of the augmented matrix quickly fills in.<br /><br />Also, do you exploit the fact that you need at most the first 20 values of (I-M)^-1 * b?<br /><br />I also tried LU factorization of the entire matrix (which has roughly 2M nonzeros for both L/U), which would require roughly 18 GFlop to solve for ~8,000 rhs - so no go.Godmar Backhttps://www.blogger.com/profile/05064247891002006433noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-35122126067406639622014-07-12T04:58:48.808-07:002014-07-12T04:58:48.808-07:00@mahbub: I didn't follow it fully either, but ...@mahbub: I didn't follow it fully either, but Petr has a description on his <a href="http://petr-mitrichev.blogspot.com/2014/06/this-week-in-competitive-programming_29.html" rel="nofollow">blog</a>.Bruce Merryhttps://www.blogger.com/profile/02150601792587963530noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-56613918995339019662014-07-01T23:32:56.183-07:002014-07-01T23:32:56.183-07:00Wondering if you can slightly describe gawry's...Wondering if you can slightly describe gawry's method, since it is a bit difficult to understand from the translated text.mahbubhttps://www.blogger.com/profile/17762750597357893116noreply@blogger.com