project euler problem 213

Flea Circus

This is a simple probability problem.  I lost my old code. But based on the discussion thread, I guess I used a Markov-Chain approach. This time,  it puzzled me for half an hour.  I suddenly figured out that this is similar to the "birthday problem", then it is solved. It only takes 200 ms for my new code. I then considered the symmetric property, the run time is reduce to 50 ms.

project euler problem 151

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.