Paper sheets of standard sizes: an expected-value problem
I checked my old code today. I was surprised to find that I used monte carlo method to run simulations. I do not know how I get the right answer at that time. But I simulated 1e8 times, still quite far from the correct answer. Shame on me!
I rewrote the code, using an appropriate method to solve it. Actually it is a simple Markov chain problem. The size of the matrix is very small. But to generate the matrix, it takes me quite a while. Then it is solved in 50 ms. There are a few Markov chain problems in PE, this one being the simplest one.
Update: I read the discussion thread, I realized that my matrix solver is a dense one, so it cost a lot of unnecessary computation. I rewrote the code, in a recursive way, solved the problem in 2 ms.
No comments:
Post a Comment