Enmeshed unit circle
This problem is very straight forward. I will not say it is simple, but if you know how to solve it, it is not difficult at all. It is just a small optimization problem since N is only 400. I solved it in an iterative way.
I spent half an hour or so to formulate the problem. Then take an hour coding while watching TV. Then I found a small bug in my code during initialization. Then it is solved. It only takes 50 ms to get the answer while some optimization is still possible since I did not consider too much about symmetry.
Saturday, July 27, 2013
Wednesday, July 17, 2013
project euler problem 245
Coresilience
A very difficult problem.
I lost my old code. I only left a several-lines comment in my computer. It says my old code runs for 80 seconds to get the answer.
This time, I want to see if I can make it faster by myself. I found that I cannot solve it! I believe it can be solved only by brute force. After some time's thought, and with the help of my comment. The problem is solved in one minute. My method is almost all brute force, but I found some property from the equation that can reduce the search space.
I read the discussion, I found there is a much better way to solve the problem. I implemented the new method. The problem is solved in 5 seconds.
Wednesday, July 10, 2013
project euler problem 244
Sliders
A simple problem. My old code used priority_queue. It takes 0.4 second to get the answer. I read the discussion and found this problem can also be solved by dynamic programming approach.
A simple problem. My old code used priority_queue. It takes 0.4 second to get the answer. I read the discussion and found this problem can also be solved by dynamic programming approach.
Sunday, July 7, 2013
project euler problem 251
Cardano Triplets
This problem is very difficult. I checked my old code, it runs very slow because I was using a very inefficient factor method. So I changed to a sieve method for factorization, which is much faster. My original code runs for 3 and a half minutes. After this optimization, my code runs for 7 seconds.
After I checked the discussion, I found a very efficient algorithm by linguo in the second page. It only takes 1.6 second. The extended euclidean algorithm in his code is very fast.
This problem is very difficult. I checked my old code, it runs very slow because I was using a very inefficient factor method. So I changed to a sieve method for factorization, which is much faster. My original code runs for 3 and a half minutes. After this optimization, my code runs for 7 seconds.
After I checked the discussion, I found a very efficient algorithm by linguo in the second page. It only takes 1.6 second. The extended euclidean algorithm in his code is very fast.
Saturday, July 6, 2013
project euler problem 249
Prime Subset Sums
This problem is relatively simple, just another exercise of dynamic programming. I checked my old code, it takes 3.5 second. I found I created extra vectors in a loop which is not necessary. After my optimization, the code runs for 1.5 second.
This problem is relatively simple, just another exercise of dynamic programming. I checked my old code, it takes 3.5 second. I found I created extra vectors in a loop which is not necessary. After my optimization, the code runs for 1.5 second.
project euler problem 248
Numbers for which Euler’s totient function equals 13!
This problem looks like very difficult since 13! is a very large number. But after some analysis, it is still manageable. My old code runs for 0.4 second. But the code looks ugly and lengthy. I rewrote the code and it is 40 lines less and only takes 100ms now.
This problem looks like very difficult since 13! is a very large number. But after some analysis, it is still manageable. My old code runs for 0.4 second. But the code looks ugly and lengthy. I rewrote the code and it is 40 lines less and only takes 100ms now.
Friday, July 5, 2013
project euler problem 247
Squares under a hyperbola
This is an interesting and simple problem. If the question asks for(4,4) instead of (3, 3), then it is quite difficult. My old code runs for 1.3 second to get the answer for (3, 3). I read the discussion immediately after I solved the problem a year ago. One Eulerian raise the question to find the largest S_n for (4, 4). I tried it with my poor code, I found that I got an out-of-memory error. I added a comment in my old code then left. What a bad habit!
This time, after I thought it over, I find I have plenty of room for further optimization. The first optimization is to prune the tree as early as possible. After that I reduce the runtime to 0.6 second for (3,3). I used the same code to solve (4,4). It takes 37 seconds, still too long! I then found that some extra and fancy manipulation of my algorithm is totally unnecessary! I used a stack to solve the problem. This time, the run time is quite satisfactory.
(3, 3) 20 ms
(4, 4) 6 seconds
This is an interesting and simple problem. If the question asks for(4,4) instead of (3, 3), then it is quite difficult. My old code runs for 1.3 second to get the answer for (3, 3). I read the discussion immediately after I solved the problem a year ago. One Eulerian raise the question to find the largest S_n for (4, 4). I tried it with my poor code, I found that I got an out-of-memory error. I added a comment in my old code then left. What a bad habit!
This time, after I thought it over, I find I have plenty of room for further optimization. The first optimization is to prune the tree as early as possible. After that I reduce the runtime to 0.6 second for (3,3). I used the same code to solve (4,4). It takes 37 seconds, still too long! I then found that some extra and fancy manipulation of my algorithm is totally unnecessary! I used a stack to solve the problem. This time, the run time is quite satisfactory.
(3, 3) 20 ms
(4, 4) 6 seconds
project euler problem 246
Tangents to an ellipse
This problem involves quite a bit math. It took me an hour or so to get the correct formula. The rest of the thing is easy. Code is very simple and runs in no time.
I am surprised to find that this problem can be solved in an algorithmic way(xsd in the first page). It involves less math and still quite efficient.
This problem involves quite a bit math. It took me an hour or so to get the correct formula. The rest of the thing is easy. Code is very simple and runs in no time.
I am surprised to find that this problem can be solved in an algorithmic way(xsd in the first page). It involves less math and still quite efficient.
Thursday, July 4, 2013
project euler problem 238
Infinite string tour
This problem looks very difficult, but actually it is not that difficult. The first thing that need to be done is to investigate the "blum blum shub" sequence. After the property of the sequence is understood, one just need to take an eye on the result. It takes 7.2 second to get the answer.
This problem looks very difficult, but actually it is not that difficult. The first thing that need to be done is to investigate the "blum blum shub" sequence. After the property of the sequence is understood, one just need to take an eye on the result. It takes 7.2 second to get the answer.
Wednesday, July 3, 2013
project euler problem 243
Resilience
This problem is a very easy problem. Nearly 4000 Eulerians have solved it. There is a small trick before one get the correct answer.
This problem is a very easy problem. Nearly 4000 Eulerians have solved it. There is a small trick before one get the correct answer.
project euler problem 240
Top Dice
The problem is not a difficult one. My old code runs for near 1 second. I checked it and did some small modification, the the run time is reduced to 0.2 second(debug version) with some room for further optimization. The combination property is essential for this problem.
The problem is not a difficult one. My old code runs for near 1 second. I checked it and did some small modification, the the run time is reduced to 0.2 second(debug version) with some room for further optimization. The combination property is essential for this problem.
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.
Tuesday, July 2, 2013
project euler problem 236
Luxury Hampers
This problem is quite difficult. My first code runs for a couple of minutes to get the answer. After I read the discussion, I found I missed an important fact from those five integer pairs given in the problem.
I optimized my code using this important and obvious fact, my code's run time is reduced to 16 seconds. Still too slow! Finally, I realized that it really matters how you search the space. By changing the search order, the search space can be greatly reduced. After this important optimization, it only take 0.6 second to get the answer!
This problem is quite difficult. My first code runs for a couple of minutes to get the answer. After I read the discussion, I found I missed an important fact from those five integer pairs given in the problem.
I optimized my code using this important and obvious fact, my code's run time is reduced to 16 seconds. Still too slow! Finally, I realized that it really matters how you search the space. By changing the search order, the search space can be greatly reduced. After this important optimization, it only take 0.6 second to get the answer!
Monday, July 1, 2013
project euler problem 235
An Arithmetic Geometric sequence
This problem needs some numerical analysis work. I checked the discussion. Some of the people used bisection method. But I would recommend Newton-Raphson method. It is way faster.
This problem needs some numerical analysis work. I checked the discussion. Some of the people used bisection method. But I would recommend Newton-Raphson method. It is way faster.
project euler problem 234
Semidivisible numbers
This is a very simple problem. It seems quite difficult since the upper bound is very large. But after you did a little bit math, you will find some magic formula for this problem and the result is straight forward.
This is a very simple problem. It seems quite difficult since the upper bound is very large. But after you did a little bit math, you will find some magic formula for this problem and the result is straight forward.
project euler problem 233
Lattice points on a circle
This is a problem of great importance. Many problems are based on the math theory of this one. It would be nice that one can spend an hour or two on this subject. I learned it from Ivan Niven's book. It takes 40 ms for my code to get the answer. The only advise is that do not miss any possible combinations. Problem 354 is an advanced version of this problem.
This is a problem of great importance. Many problems are based on the math theory of this one. It would be nice that one can spend an hour or two on this subject. I learned it from Ivan Niven's book. It takes 40 ms for my code to get the answer. The only advise is that do not miss any possible combinations. Problem 354 is an advanced version of this problem.
project euler problem 220
Heighway Dragon
This problem is a very interesting problem. When I tried to solve it a year ago, I had no clue about it until I figured out the relation between D_n and D_{n-1}. Then the problem is relatively simple and easy to code.
I took a look at the discussion. I find the dragon curve has very nice math properties. I do not know how to prove those properties. But even if one does not know the math, the problem can still be solved in an elegant approach.
This problem is a very interesting problem. When I tried to solve it a year ago, I had no clue about it until I figured out the relation between D_n and D_{n-1}. Then the problem is relatively simple and easy to code.
I took a look at the discussion. I find the dragon curve has very nice math properties. I do not know how to prove those properties. But even if one does not know the math, the problem can still be solved in an elegant approach.
Subscribe to:
Posts (Atom)