Billionaire
A simple problem. The problem is about maximum and probability. Once this is understood, the rest part is very easy. It takes only 1ms.
Showing posts with label probability. Show all posts
Showing posts with label probability. Show all posts
Thursday, August 22, 2013
Sunday, August 11, 2013
project euler problem 430
Range flips
This problem looks like very difficult, but actually it is not. It is a very simple probability problem. After some derivation, I got a formula and there is no need to write any code!
The key point in this problem is that "range" is a misleading word.
This problem looks like very difficult, but actually it is not. It is a very simple probability problem. After some derivation, I got a formula and there is no need to write any code!
The key point in this problem is that "range" is a misleading word.
Wednesday, July 3, 2013
project euler problem 239
Twenty-two Foolish Primes
This problem is really simple. The code is less than 15 lines. The key principle is well-known. I used this principle to solve quite a few PE problems.
This problem is really simple. The code is less than 15 lines. The key principle is well-known. I used this principle to solve quite a few PE problems.
Thursday, June 20, 2013
project euler problem 227
The Chase
This problem is a very easy problem. It is about basic probability theory. The solve of the matrix is also very easy. But I do not see why only 1100 people solved it.
This problem is a very easy problem. It is about basic probability theory. The solve of the matrix is also very easy. But I do not see why only 1100 people solved it.
Saturday, June 8, 2013
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.
Sunday, June 2, 2013
project euler problem 205
Dice Game
This is a very simple problem. I am surprised why more than 7500 people solved it. For problem with an ID greater than 200, usually only less than 1000 people can solve it.
Thursday, April 18, 2013
project euler problem 121
Disc game prize fund
This is a very simple probability problem. I have nothing to say about this problem.
This is a very simple probability problem. I have nothing to say about this problem.
Wednesday, March 6, 2013
project euler problem 298
Selective Amnesia
This is not an easy problem. I gave up on this problem for a couple of times. Finally, I made all my effort to simplify this problem, it is solved!
The first part is to transform the pairs of numbers into states, which is quite complicated. I spent half a day or even longer on this part. After this part is done, the task left is just to solve a very easy probability problem. Quite a few problems in Project Euler require such sort of abstraction. For example, problem 324, building a tower.
It takes my code 0.17s to find the answer. It looks like there is still some potential to speed up.
After this problem is solved. I entered level 14. Still another 25 problems left to enter level 15.
This is not an easy problem. I gave up on this problem for a couple of times. Finally, I made all my effort to simplify this problem, it is solved!
The first part is to transform the pairs of numbers into states, which is quite complicated. I spent half a day or even longer on this part. After this part is done, the task left is just to solve a very easy probability problem. Quite a few problems in Project Euler require such sort of abstraction. For example, problem 324, building a tower.
It takes my code 0.17s to find the answer. It looks like there is still some potential to speed up.
After this problem is solved. I entered level 14. Still another 25 problems left to enter level 15.
Monday, February 25, 2013
project euler problem 316
Numbers in decimal expansions
This is another probability problem. I knew how to solve it from the very beginning, but my code is not very efficient. I also got accuracy issues in this problem. But I was too lazy to rewrite the code and somehow managed to solve it.
If you do not know how to solve such kind of problem, try to read some probability book. You will find how to solve such kind of problems. For example,
Introduction to probability models by Ross Sheldon
This is another probability problem. I knew how to solve it from the very beginning, but my code is not very efficient. I also got accuracy issues in this problem. But I was too lazy to rewrite the code and somehow managed to solve it.
If you do not know how to solve such kind of problem, try to read some probability book. You will find how to solve such kind of problems. For example,
Introduction to probability models by Ross Sheldon
project euler problem 280
ants and seeds
I have studied probability theory for some time, and I thought that I should not have too much difficulty to solve probability problems, but actually I still have quite a few probability problems unsolved.
This is a probability and combinatoric problem. It looks quite difficult at first thought but after I tried, it is actually not difficult at all. I recently began to use Lapack and I tried Lapack in this problem. The code runs quite fast, only 1.4 second, with some potential for further optimization.
After I solved this problem, I read some posts in discussion thread and luckytoilet's blog since I knew that he has two post about this problem (I resist the temptation to read it before I solved the problem). I am surprised to find that there is quite a few different approaches to solve it. I believe my method is quite straight forward and efficient. Maybe the combinatoric part scared the people.
Manually solve a 2x2 problem is helpful to solve the 5x5 problem.
Excellent problem! I like it.
I have studied probability theory for some time, and I thought that I should not have too much difficulty to solve probability problems, but actually I still have quite a few probability problems unsolved.
This is a probability and combinatoric problem. It looks quite difficult at first thought but after I tried, it is actually not difficult at all. I recently began to use Lapack and I tried Lapack in this problem. The code runs quite fast, only 1.4 second, with some potential for further optimization.
After I solved this problem, I read some posts in discussion thread and luckytoilet's blog since I knew that he has two post about this problem (I resist the temptation to read it before I solved the problem). I am surprised to find that there is quite a few different approaches to solve it. I believe my method is quite straight forward and efficient. Maybe the combinatoric part scared the people.
Manually solve a 2x2 problem is helpful to solve the 5x5 problem.
Excellent problem! I like it.
Monday, February 18, 2013
project euler problem 253
tidying up
A very difficult probability problem. It takes me quite some time to write the code for a brute force method(well, it is not Monte Carlo). I found it was too slow, and also took too much memory. Then based on this brute force version, I did some optimization to reduce the memory cost since something are actually equivalent. However, after the optimization, It still took 16 seconds.
Please read the discussion thread, there is a very smart way to solve this problem.
A very difficult probability problem. It takes me quite some time to write the code for a brute force method(well, it is not Monte Carlo). I found it was too slow, and also took too much memory. Then based on this brute force version, I did some optimization to reduce the memory cost since something are actually equivalent. However, after the optimization, It still took 16 seconds.
Please read the discussion thread, there is a very smart way to solve this problem.
Subscribe to:
Posts (Atom)