Counting rectangles
Since an analytical formula is available for total the number of rectangles, the rest is simply sweeping all possible length and width. It takes less than 1ms to find the answer.
Sunday, March 31, 2013
project euler problem 081, 082, 083
Path sum: two ways, three ways, four ways
project euler problem 081, two ways
Very simple dynamic programming problem. Warm up for the next two problem.
project euler problem 082, three ways
A little bit more complicated. Still simple dynamic programming problem. warm up problem.
project euler problem 083 four ways
This is a real problem. Not that simple. I used the C++ STL priority_queue to solve this problem, fast and simple. 16ms with my debug version.
project euler problem 081, two ways
Very simple dynamic programming problem. Warm up for the next two problem.
project euler problem 082, three ways
A little bit more complicated. Still simple dynamic programming problem. warm up problem.
project euler problem 083 four ways
This is a real problem. Not that simple. I used the C++ STL priority_queue to solve this problem, fast and simple. 16ms with my debug version.
Saturday, March 30, 2013
project euler problem 080
Square root digital expansion
This is an interesting problem. I checked my old code, I used my bigInteger class, and used Newton's method iteratively to get the accurate result. It takes 0.7 second to find the number.
This time I used continued fraction method, and I can figure out as many digits of p/q as required. The code is fast although my bigInteger class is slow. It only takes 1.6ms to find the answer.
I also verified the result for the first 1000 digits of sqrt(2) to sqrt(99) as it is given in the discussion thread. It takes 0.77 second.
Update: 09/26/2017
Python is a great helper. With Decimal, this problem is no-brainer.
This is an interesting problem. I checked my old code, I used my bigInteger class, and used Newton's method iteratively to get the accurate result. It takes 0.7 second to find the number.
This time I used continued fraction method, and I can figure out as many digits of p/q as required. The code is fast although my bigInteger class is slow. It only takes 1.6ms to find the answer.
I also verified the result for the first 1000 digits of sqrt(2) to sqrt(99) as it is given in the discussion thread. It takes 0.77 second.
Update: 09/26/2017
Python is a great helper. With Decimal, this problem is no-brainer.
project euler problem 078
Coin partitions
This problem is similar to problem 076, but need some math knowledge, otherwise, it becomes terrifically difficult. I was forced to find some useful formula, and finally succeed. I need to check how to prove this useful formula.
This problem is similar to problem 076, but need some math knowledge, otherwise, it becomes terrifically difficult. I was forced to find some useful formula, and finally succeed. I need to check how to prove this useful formula.
project euler problem 077
Prime summations
Similar to problem 76.
This is not a difficult problem. But there is a lot math to be learned in the discussion thread. Euler is really a genius!
Update 09/25/2017:
The recursive method used in my previous code is too slow. I did not notice that until I tried to find the number of ways to express 1000 in primes. It is too slow! I used the dynamic programming approach to solve this knapsack problem and it takes less than 1ms to get the result!
Similar to problem 76.
This is not a difficult problem. But there is a lot math to be learned in the discussion thread. Euler is really a genius!
Update 09/25/2017:
The recursive method used in my previous code is too slow. I did not notice that until I tried to find the number of ways to express 1000 in primes. It is too slow! I used the dynamic programming approach to solve this knapsack problem and it takes less than 1ms to get the result!
Friday, March 29, 2013
project euler problem 076
Counting summations
Project Euler problems become interesting from 60--70. The first 50 problems are mainly warm-up problems. Now, we can see some interesting math problems such as Pell equations and partition.
This problem is interesting but still simple. It is very similar to problem 31 and can be solved recursively or with generating function.
update: 09/25/2017: The simplest way of solving this problem is using dynamic programming, this is a knapsack problem.
The answer for N = 10000 can be found in 0.74 second.
Project Euler problems become interesting from 60--70. The first 50 problems are mainly warm-up problems. Now, we can see some interesting math problems such as Pell equations and partition.
This problem is interesting but still simple. It is very similar to problem 31 and can be solved recursively or with generating function.
update: 09/25/2017: The simplest way of solving this problem is using dynamic programming, this is a knapsack problem.
The answer for N = 10000 can be found in 0.74 second.
project euler problem 075
Singular integer right triangles
A simple problem, very easy if one knew the algorithm. I am just wondering if there is any simpler algorithm without the help of a counter array?
A simple problem, very easy if one knew the algorithm. I am just wondering if there is any simpler algorithm without the help of a counter array?
Subscribe to:
Posts (Atom)