Constraining the least greatest and the greatest least
This problem is a relatively easy one. We are given some numbers like 1e6, 1e12 and 1e18. 1e18 ruled out the possibility of any sort of brute force. 1e12 means that we need to do some optimization on the numbers from 1e6 to 1e12 since it is still a burden for computer. Well, 1e6 is not so big a number, we can do whatever we like.
After sometime's thought, I found that there is a neat formula for this problem(it is not difficult to derive the formula). With this formula, it is very easy to find the number of valid lists for certain gcd and lcm.(Well, after I read the discussion, I found that this formula may be derived after a moment's thought!) My code first ran for 5 seconds, then I did some optimization since 1e18 is too large in some sense, then the code runs for 0.18 second.
Friday, September 20, 2013
Sunday, September 8, 2013
project euler problem 265
Binary Circles
This is a very simple problem. A simple recursive function can get the correct answer. It only needs 50 ms to get the correct answer.
This is a very simple problem. A simple recursive function can get the correct answer. It only needs 50 ms to get the correct answer.
project euler problem 435
Polynomials of Fibonacci numbers
This problem is relatively simple. But a little bit math is required to avoid computer to do huge amount of work. This problem is very similar to some older problem. You may first ask yourself a simpler question, how to calculate the 10^15th Fibonacci number(mod n)?
After I get the answer for F_7(11) correct. I immediately get the correct solution for the problem. The only bad thing is that I used some sort of bigInteger in my code, but it may not be necessary if you handle the problem in a different approach.
This problem is relatively simple. But a little bit math is required to avoid computer to do huge amount of work. This problem is very similar to some older problem. You may first ask yourself a simpler question, how to calculate the 10^15th Fibonacci number(mod n)?
After I get the answer for F_7(11) correct. I immediately get the correct solution for the problem. The only bad thing is that I used some sort of bigInteger in my code, but it may not be necessary if you handle the problem in a different approach.
Saturday, September 7, 2013
project euler problem 266
Pseudo Square Root
This problem is not easy in my opinion. I forgot how I solved the problem for the first time. But I remembered that it was slow. I then read the discussion and found a clever solution for this problem. I was surprised that many people knew the algorithm or found the algorithm by themselves.
The algorithm can be used to solve problem 185 or problem 418 and now problem 461.
This problem is not easy in my opinion. I forgot how I solved the problem for the first time. But I remembered that it was slow. I then read the discussion and found a clever solution for this problem. I was surprised that many people knew the algorithm or found the algorithm by themselves.
The algorithm can be used to solve problem 185 or problem 418 and now problem 461.
Wednesday, August 28, 2013
project euler problem 418
Factorisation triples
This is an easy problem. When the problem is posted, I felt that it is not very difficult. It looks like similar to problem 266, but I did not play with it seriously. Today, I still do not have too much clue on it. I tried to answer some fundamental questions like "how to express 43! in terms of prime numbers and how many factors does 43! have". After a while, I see what I need to do. I implemented some simple code and it takes 500 seconds to get the answer! It is slow, however the answer is correct. I optimized my code and tried to start searching in a different place. It only takes 5 seconds to get the answer.
This is an easy problem. When the problem is posted, I felt that it is not very difficult. It looks like similar to problem 266, but I did not play with it seriously. Today, I still do not have too much clue on it. I tried to answer some fundamental questions like "how to express 43! in terms of prime numbers and how many factors does 43! have". After a while, I see what I need to do. I implemented some simple code and it takes 500 seconds to get the answer! It is slow, however the answer is correct. I optimized my code and tried to start searching in a different place. It only takes 5 seconds to get the answer.
Thursday, August 22, 2013
project euler problem 267
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.
A simple problem. The problem is about maximum and probability. Once this is understood, the rest part is very easy. It takes only 1ms.
Wednesday, August 14, 2013
project euler problem 268
Counting numbers with at least four distinct prime factors less than 100
A great problem.
I checked my old code. It runs very slow, near 40 seconds. The worst thing is that I do not know how to speed it up. I checked the discussion and found that it is still about principle of inclusion-exclusion, but our job is to remove the over-count. I wrote some new code and it only takes 0.15 second to get the answer.
A great problem.
I checked my old code. It runs very slow, near 40 seconds. The worst thing is that I do not know how to speed it up. I checked the discussion and found that it is still about principle of inclusion-exclusion, but our job is to remove the over-count. I wrote some new code and it only takes 0.15 second to get the answer.
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.
project euler problem 421
Prime factors of n15+1
I am very happy that this problem is solved. Although my solution is not as elegant as those guys who solved it in a couple of hours after the problem was posted. But it is not too bad. It takes 23 seconds to get the answer.
I do not know how to solve this problem after I read the problem. Although I knew how to do the factorization of n15+1(polynomial), but it is useless. The numbers are huge! Then, I found some old problems are closely related to this problem, i.e., problem 271 and 272. I reviewed the discussion of these two problems and found some real gems in the discussion! It really helps to solve the problem!
I really believe reading the discussion of a problem is as important as solving a problem by oneself. In some sense, it is even more important than solving a problem. A lot of genius gave incisive comments in the discussion that we may benefit from.
Friday, August 9, 2013
project euler problem 431
Square Space Silo
The funniest problem of all PE problems. Words like "have three squared decimal places" are really humorous. What a square paranoia Fred is! Well, the PE development team are integer paranoia!
The problem is not very difficult to solve since we only need to find the wasted volume. It is a one dimensional integration problem. One just needs to be careful about the accuracy. There is not too much trick in the problem.
The funniest problem of all PE problems. Words like "have three squared decimal places" are really humorous. What a square paranoia Fred is! Well, the PE development team are integer paranoia!
The problem is not very difficult to solve since we only need to find the wasted volume. It is a one dimensional integration problem. One just needs to be careful about the accuracy. There is not too much trick in the problem.
Wednesday, August 7, 2013
project euler problem 272
Modular Cubes, part 2
This problem is more difficult than problem 271. I lost my old code, so I wrote a new code. I made some mistakes in the code, but soon I fixed those bugs. I checked the clarification of the problem, but some of the guy's result is not correct. I spent a lot of time debugging the case of 3e7, 3e8. But finally I found my code is correct!
My code runs 2 second. One need to memorize some result to speed up the code. That being said, it is still very tricky to count the number of solutions of the same type!
Update: The discussion of this problem is very helpful. I learned a great deal from the discussion. I solved problem 421 with the help of the discussion.
This problem is more difficult than problem 271. I lost my old code, so I wrote a new code. I made some mistakes in the code, but soon I fixed those bugs. I checked the clarification of the problem, but some of the guy's result is not correct. I spent a lot of time debugging the case of 3e7, 3e8. But finally I found my code is correct!
My code runs 2 second. One need to memorize some result to speed up the code. That being said, it is still very tricky to count the number of solutions of the same type!
Update: The discussion of this problem is very helpful. I learned a great deal from the discussion. I solved problem 421 with the help of the discussion.
Sunday, August 4, 2013
project euler problem 271
Modular Cubes, part 1
This problem is simple. But pure brute force is not an option. I checked my old code, I kept a list of "possible solutions" and used something like bigInteger to do the modulo work since the numbers are too big. It only takes 17 ms, not too bad!
This time, I tried to avoid using bigIntegers since most of the problems with a number greater than 150 may be solved without the help of GMP. I found there is a better solution which used the famous Chinese Remainder Theorem. The problem is extremely simple after one understand what is going on inside CRT. Quite a few other project euler problems also check one's understanding of CRT, this one being the simplest one. It is a good opportunity to learn CRT!
My code runs less than 10 ms.
This problem is simple. But pure brute force is not an option. I checked my old code, I kept a list of "possible solutions" and used something like bigInteger to do the modulo work since the numbers are too big. It only takes 17 ms, not too bad!
This time, I tried to avoid using bigIntegers since most of the problems with a number greater than 150 may be solved without the help of GMP. I found there is a better solution which used the famous Chinese Remainder Theorem. The problem is extremely simple after one understand what is going on inside CRT. Quite a few other project euler problems also check one's understanding of CRT, this one being the simplest one. It is a good opportunity to learn CRT!
My code runs less than 10 ms.
project euler problem 417
Reciprocal Cycles II
This problem is very similar to problem 26. But it is much harder than problem 26. Problem was posted in 2002 while this problem was posted in 2013!
I checked my code for problem 26. I just tried it for the largest prime number less than 1e8, which is 99999989; it has a recurring cycle of 99999988. It takes 1.3 second to find the recurring period for this prime number! So it is nearly impossible to use similar code to handle problem 417!
I tried problem 417 a while ago, all effort in vain. But today I found more than 300 people has already solved it. It should be relatively simple. I carefully checked the discussion thread for problem 26, then I found some gems in it. For example, a key word multiplicative order pops up. Some more useful information can also be found in the discussion. Finally, the problem is solved after I did some research from the Internet!
Recently, PE are more difficult to solve. For example, the run time of some clever approach is about 15 to 25 seconds. This almost ruled out the possibility of some semi-bruteforce approaches!
This problem is very similar to problem 26. But it is much harder than problem 26. Problem was posted in 2002 while this problem was posted in 2013!
I checked my code for problem 26. I just tried it for the largest prime number less than 1e8, which is 99999989; it has a recurring cycle of 99999988. It takes 1.3 second to find the recurring period for this prime number! So it is nearly impossible to use similar code to handle problem 417!
I tried problem 417 a while ago, all effort in vain. But today I found more than 300 people has already solved it. It should be relatively simple. I carefully checked the discussion thread for problem 26, then I found some gems in it. For example, a key word multiplicative order pops up. Some more useful information can also be found in the discussion. Finally, the problem is solved after I did some research from the Internet!
Recently, PE are more difficult to solve. For example, the run time of some clever approach is about 15 to 25 seconds. This almost ruled out the possibility of some semi-bruteforce approaches!
Saturday, August 3, 2013
project euler problem 412
Gnomon numbering
This problem is relatively easy with the help of google.I did some search about the problem and find wikipedia and mathworld provide some very useful information. I do not want to give too much hint since the search takes little effort. After I understood what needs to be computed, the rest is really simple since 76543217 is a prime.
It takes 0.35 second to get the correct answer.
Thursday, August 1, 2013
project euler problem 374
Maximum Integer Partition Product
This problem is relatively easy to solve.
PE problems are more and more difficult to solve now since the number are huge! 1e14, 1e18 or 1e19 are very popular in problems with a problem number greater than 350. It means if you cannot find some formula, it is almost impossible to solve the problem.
I got some help from google. After that, the problem is very straight forward. But I still got stuck by overflow issue for some time. My code runs for 5 seconds.
This problem is relatively easy to solve.
PE problems are more and more difficult to solve now since the number are huge! 1e14, 1e18 or 1e19 are very popular in problems with a problem number greater than 350. It means if you cannot find some formula, it is almost impossible to solve the problem.
I got some help from google. After that, the problem is very straight forward. But I still got stuck by overflow issue for some time. My code runs for 5 seconds.
Saturday, July 27, 2013
project euler problem 392
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.
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.
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.
Sunday, June 30, 2013
project euler problem 231
The prime factorisation of binomial coefficients
This problem is very simple. It is actually almost doing the same thing as problem 429 does. I checked my old code. It takes more than 3 seconds to get the answer since I did not manage those factors very well. I revised the code a little bit. Now it only takes less than 0.5 second.
This problem is very simple. It is actually almost doing the same thing as problem 429 does. I checked my old code. It takes more than 3 seconds to get the answer since I did not manage those factors very well. I revised the code a little bit. Now it only takes less than 0.5 second.
Saturday, June 29, 2013
project euler problem 226
A Scoop of Blancmange
This problem is not very difficult. The most critical part is to find the intersection point between the curve and the circle. It looks like extremely difficult. But we just need an approximate answer. The rest part is just a numerical integral.
This problem is not very difficult. The most critical part is to find the intersection point between the curve and the circle. It looks like extremely difficult. But we just need an approximate answer. The rest part is just a numerical integral.
project euler problem 228
Minkowski Sums
This problem is simple once the property of Minkowski Sums is known. I learned it from Wikipedia. The problem is easy to solve. I guess this problem is created in honor of Hermann Minkowski since he was born in 1864 and passed away in January 12, 1909. Notice the problem is published in January 16, 2009.
This problem is simple once the property of Minkowski Sums is known. I learned it from Wikipedia. The problem is easy to solve. I guess this problem is created in honor of Hermann Minkowski since he was born in 1864 and passed away in January 12, 1909. Notice the problem is published in January 16, 2009.
Tuesday, June 25, 2013
project euler problem 429
Sum of squares of unitary divisors
Easiest problem in 2013. I take a look at the problem and find out it is extremely easy. No wonder 470+ people have already solved it. I wrote the code in 15 minutes and it is solved! I should admit that I used a few of my functions wrote for other problems. Without those functions, I will need a little bit more time.
Try it, it is easy. Everyone feels happy to solve this problem!
Easiest problem in 2013. I take a look at the problem and find out it is extremely easy. No wonder 470+ people have already solved it. I wrote the code in 15 minutes and it is solved! I should admit that I used a few of my functions wrote for other problems. Without those functions, I will need a little bit more time.
Try it, it is easy. Everyone feels happy to solve this problem!
project euler problem 354
Distances in a bee's honeycomb
This problem is relatively easy for people who have solved 300+ problems, although only 230 people solved it. But one needs to find the "magic formula" for this problem. It is not that hard to find the formula. Figuring out those examples are close. It takes 13 seconds for my code to get the answer.
This problem is relatively easy for people who have solved 300+ problems, although only 230 people solved it. But one needs to find the "magic formula" for this problem. It is not that hard to find the formula. Figuring out those examples are close. It takes 13 seconds for my code to get the answer.
Saturday, June 22, 2013
project euler problem 229
Four Representations using Squares
This problem is very difficult if one can fully understand the math behind the problem and solve it in a mathematical way. But If we do not mind to solve it in an easier way, it is kind of straight forward and the code is easy to write. We have used this method to find primes, factors of numbers, etc....
I tried to reduce the memory usage and break the whole range into a lot of small segments. The memory usage is reduced and the problem is solved in much less time! I used 11.8 seconds to get the answer.
Although I still need to understand more about the math behind the problem, I still learned some math about Jacobi symbol! The property of Jacobi symbol is really amazing!
This problem is very difficult if one can fully understand the math behind the problem and solve it in a mathematical way. But If we do not mind to solve it in an easier way, it is kind of straight forward and the code is easy to write. We have used this method to find primes, factors of numbers, etc....
I tried to reduce the memory usage and break the whole range into a lot of small segments. The memory usage is reduced and the problem is solved in much less time! I used 11.8 seconds to get the answer.
Although I still need to understand more about the math behind the problem, I still learned some math about Jacobi symbol! The property of Jacobi symbol is really amazing!
Thursday, June 20, 2013
project euler problem 230
Fibonacci Words
This problem is quite simple. It is straight forward to solve although the problem looks like formidable.
This problem is quite simple. It is straight forward to solve although the problem looks like formidable.
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.
Tuesday, June 18, 2013
project euler problem 224
Almost right-angled triangles II, revisit
This problem is related to problem 221 and 223. If you solve either of them, this one is not that hard. Otherwise, the solution might be very costly. I tried factorization method. Although I have used some of the result from previous problem, it is still very slow. It takes 20 seconds. I will try Doraki's algorithm tomorrow.
This problem is related to problem 221 and 223. If you solve either of them, this one is not that hard. Otherwise, the solution might be very costly. I tried factorization method. Although I have used some of the result from previous problem, it is still very slow. It takes 20 seconds. I will try Doraki's algorithm tomorrow.
Monday, June 17, 2013
project euler problem 223
Almost right-angled triangles I, Revisit
This problem is very difficult. One algorithm is easy to come up with. But it is not very efficient. It is quite slow. My code runs for 20 seconds. Doraki provided a very nice algorithm in the first page. It only takes a few seconds using Doraki's algorithm. I am very eager to know if there is any efficient method to solve it in one second.
This problem is very difficult. One algorithm is easy to come up with. But it is not very efficient. It is quite slow. My code runs for 20 seconds. Doraki provided a very nice algorithm in the first page. It only takes a few seconds using Doraki's algorithm. I am very eager to know if there is any efficient method to solve it in one second.
Sunday, June 16, 2013
project euler problem 225
Tribonacci non-divisors
This problem is not difficult since we are only required to find the 124th odd number. But the maths behind it is quite interesting.
This problem is not difficult since we are only required to find the 124th odd number. But the maths behind it is quite interesting.
Saturday, June 15, 2013
project euler problem 222
sphere packing
I learned quite a bit from this problem.
First, this problem can be solved by pencil and paper. I learned it from BrianHuffman on the third page of the discussion thread. BrianHuffman's explanation is very lucid. I like it.
I also practiced Dynamic programming method and random number method on this problem. Dynamic programming method gives me definite result but it takes a little bit more time(5-6 seconds). I also tried with some random number method, it seems inefficient but the result is just the opposite. It only takes 8ms.
I learned quite a bit from this problem.
First, this problem can be solved by pencil and paper. I learned it from BrianHuffman on the third page of the discussion thread. BrianHuffman's explanation is very lucid. I like it.
I also practiced Dynamic programming method and random number method on this problem. Dynamic programming method gives me definite result but it takes a little bit more time(5-6 seconds). I also tried with some random number method, it seems inefficient but the result is just the opposite. It only takes 8ms.
Thursday, June 13, 2013
project euler problem 221
Alexandrian Integers
My old code is close to brute force. It runs for 4.4 seconds after I restricted the number to be tested.
I used the algorithm that is used in problem 216. It is quite fast. Only 0.3 second needed. There is a few other algorithms that is also very fast to solve this problem.
My old code is close to brute force. It runs for 4.4 seconds after I restricted the number to be tested.
I used the algorithm that is used in problem 216. It is quite fast. Only 0.3 second needed. There is a few other algorithms that is also very fast to solve this problem.
Tuesday, June 11, 2013
project euler problem 217
Balanced Numbers
This is an interesting problem. My old code use very cumbersome sum and counting algorithms. But since we just need a number modulo 3^15, we can do it more efficiently. I do not understand why we are asked to give T(47), T(10000) is more challenging. I wrote poor quality code for T(47). But after I tried to solve T(10000), the algorithm need to be carefully thought over.
My algorithm can compute T(10000) in about 5 seconds. After I checked some of the code in the discussion. I can speed up my code by a factor of 2.x . I played with the code for two days for better performance.
This is an interesting problem. My old code use very cumbersome sum and counting algorithms. But since we just need a number modulo 3^15, we can do it more efficiently. I do not understand why we are asked to give T(47), T(10000) is more challenging. I wrote poor quality code for T(47). But after I tried to solve T(10000), the algorithm need to be carefully thought over.
My algorithm can compute T(10000) in about 5 seconds. After I checked some of the code in the discussion. I can speed up my code by a factor of 2.x . I played with the code for two days for better performance.
Sunday, June 9, 2013
project euler problem 218
Perfect right-angled triangles
The strangest problem of all PE problems. You will see what I mean when you solved the problem.
The strangest problem of all PE problems. You will see what I mean when you solved the problem.
Saturday, June 8, 2013
project euler problem 216
Investigating the primality of numbers of the form 2n^2-1
It is not so easy to find an efficient algorithm. I checked the discussion, a lot of people' code runs for several minutes to several hours. (If my code cannot finish in 15 minutes, I will definitely kill it). But still more than 2100 people solved it. It is really strange.
I checked my old code, it looks like that I googled out something from the Internet to solve this problem. Otherwise I have no idea how to solve it.
This time, I am equipped with a weapon that is related to quadratic residue. My first implementation needs 8 second. Then I checked the discussion, I found stubbscroll has a better solution. I used some of his idea, the run time is reduced to 5 seconds. I also run his code, it only takes 4 seconds. That is probably due to my powmod function.
It is not so easy to find an efficient algorithm. I checked the discussion, a lot of people' code runs for several minutes to several hours. (If my code cannot finish in 15 minutes, I will definitely kill it). But still more than 2100 people solved it. It is really strange.
I checked my old code, it looks like that I googled out something from the Internet to solve this problem. Otherwise I have no idea how to solve it.
This time, I am equipped with a weapon that is related to quadratic residue. My first implementation needs 8 second. Then I checked the discussion, I found stubbscroll has a better solution. I used some of his idea, the run time is reduced to 5 seconds. I also run his code, it only takes 4 seconds. That is probably due to my powmod function.
project euler problem 215
Crack-free Walls
This is a relatively easy problem. My code's run time is 20 ms. I did not get too much from the discussion.
This is a relatively easy problem. My code's run time is 20 ms. I did not get too much from the discussion.
project euler prolem 214
Totient Chains
This problem is not very interesting. It is pretty straight forward. I did not find a super fast solution in the discussion. My code's runtime is 2.2 second.
This problem is not very interesting. It is pretty straight forward. I did not find a super fast solution in the discussion. My code's runtime is 2.2 second.
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.
Friday, June 7, 2013
project euler problem 212
Combined Volume of Cuboids
This is an interesting problem. My old code used an inefficient algorithm(although the basic idea is in the right direction). It takes minutes to get the answer.
The discussion is very interesting. Robert_Gerbicz gave a very efficient algorithm that I missed. I wrote my code using the same idea, it only needs 80 ms while a lot of people needs 10 seconds to minutes to get the answer. Thank you Robert, for giving me a different view of the problem.
Thursday, June 6, 2013
project euler problem 211
Divisor Square Sum
I used two method to solve this problem. One is simple and straight forward. But the performance is poor, about 20 seconds. The second one is using recursion. It takes 2.4 seconds to get the answer.
I am surprised to see quite a few people using very slow brute force method in the discussion. It takes several hours or even days to get the answer. Why not think it over and let computer have a break?
I used two method to solve this problem. One is simple and straight forward. But the performance is poor, about 20 seconds. The second one is using recursion. It takes 2.4 seconds to get the answer.
I am surprised to see quite a few people using very slow brute force method in the discussion. It takes several hours or even days to get the answer. Why not think it over and let computer have a break?
Wednesday, June 5, 2013
project euler problem 210
Obtuse Angled Triangles
This problem is not very interesting. It is not difficult at all. A brute force solution is easy to be coded in 5 minutes. But one potential issue about accuracy may exist. I learned one trick from the discussion that removed the sqrt computation from most of my code. My original code runs for 1.2 second and my new code only needs 0.17 second.
The background of this problem is very famous. Those guys in discussion are quite knowledgeable. It seems that they knew everything about math and coding.
Tuesday, June 4, 2013
project euler problem 209
Circular Logic
This problem is relatively simple. The keyword is circular. We just need to find how many elements are in the same circle. Then we just need to find the number of different configurations that satisfy the condition. It is a simple dynamic programming problem.
project euler problem 208
Robot Walks
This problem is very interesting, and also very difficult. I like it. When I first tried to solve it, I have no clue. It take me several days to find out what I am supposed to do. I even used the pentaflake figure from mathworld to test some of my idea. Finally, I found the problem was simpler than I thought. The clarification of problem 208 is very useful. One may get a lot of hint from the discussion.
I first used quite complicated struct to solve this problem. It takes more than five seconds. After I simplified the struct to two integers, it is solved in less than 3 second.
Today, I reviewed the discussion. I found that I can use some symmetry properties to reduce the search space. Then it takes only less than 0.5 second to solve the problem.
Today, I reviewed the discussion. I found that I can use some symmetry properties to reduce the search space. Then it takes only less than 0.5 second to solve the problem.
Sunday, June 2, 2013
project euler problem 207
Integer partition equations
I do not understand why only less than 2700 people solved this problem. The problem is as simple as problem 206 and 205.
project euler problem 206
Concealed Square
The simplest problem after problem 200! If one thought it over, the problem can be solved faster.
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.
project euler problem 204
Generalized Hamming Numbers
This is a very simple problem. I used recursion. It only takes 40 ms.
project euler problem 203
Square-free Binomial Coefficients
This problem is too simple. The number of lines is too small, there are only limited numbers to be checked. I was using factorization in my old code, but I found that it was not necessary at all.
There are one or two more challenging PE problem closely related to this problem.
project euler problem 202
Laser beam
This looks more like a physics problem, but involved some math and coding. Once you understand what you should do, it is very simple. It takes less than 1 ms.
This looks more like a physics problem, but involved some math and coding. Once you understand what you should do, it is very simple. It takes less than 1 ms.
project euler problem 201
Subsets with a unique sum
The problem is not so interesting. I did not learn too much from the problem. Since there are so many combinations, even if my code has some logic bugs, I still get the correct answer. The ways to solve this problem are almost near brute force.
The problem is not so interesting. I did not learn too much from the problem. Since there are so many combinations, even if my code has some logic bugs, I still get the correct answer. The ways to solve this problem are almost near brute force.
project euler problem 200
Find the 200th prime-proof sqube containing the contiguous sub-string "200"
Not a very interesting problem. I do not like it very much. almost everyone is doing the same thing.
Not a very interesting problem. I do not like it very much. almost everyone is doing the same thing.
project euler problem 199
Iterative Circle Packing
This is a math problem. Not too much coding needed. If one can solve the geometry problem by himself, one may have a wonderful day.
This is a math problem. Not too much coding needed. If one can solve the geometry problem by himself, one may have a wonderful day.
project euler problem 198
Ambiguous Numbers
This is probably the most confusing problem in all PE problems. So many people are confused by the definition of amibuous number and cannot get the correct answer. The following sentence need to be carefully read and interpreted.
"We shall call a real number x ambiguous, if there is at least one denominator bound for which x possesses two best approximations."
A lot of hint and helpful message are given here. After we understand what "trivial" means, the rest are not so difficult.
Actually, there is some related problems to this one. The problem number is between 50 to 80. If the simpler problem can be solved efficiently, this one can be done similarly. My code finished in 0.2 second.
This is probably the most confusing problem in all PE problems. So many people are confused by the definition of amibuous number and cannot get the correct answer. The following sentence need to be carefully read and interpreted.
"We shall call a real number x ambiguous, if there is at least one denominator bound for which x possesses two best approximations."
A lot of hint and helpful message are given here. After we understand what "trivial" means, the rest are not so difficult.
Actually, there is some related problems to this one. The problem number is between 50 to 80. If the simpler problem can be solved efficiently, this one can be done similarly. My code finished in 0.2 second.
Saturday, June 1, 2013
project euler problem 197
Investigating the behaviour of a recursively defined sequence
The problem is very easy. But it is not easy to explain the math behind it.
The problem is very easy. But it is not easy to explain the math behind it.
project euler problem 196
Prime triplets
This problem is relatively simple. One just needs to find all primes in range [low, high]. The problem is well defined and easy to solve. My code is not so nice. But it runs under 1 second.
This problem is relatively simple. One just needs to find all primes in range [low, high]. The problem is well defined and easy to solve. My code is not so nice. But it runs under 1 second.
project euler problem 195
Inscribed circles of triangles with one angle of 60 degrees
I like this problem. When I first tried to solve this problem. I found some quick formula for the problem and solved the problem in 1 second. This time, I revised the code a little bit, checking gcd as the last criteria, my code's run time reduced to 0.47 second.
After I read the discussion thread, I recommend everyone read lomont's post on the second page. It is a brief but interesting tutorial about Eisenstein integers.
I like this problem. When I first tried to solve this problem. I found some quick formula for the problem and solved the problem in 1 second. This time, I revised the code a little bit, checking gcd as the last criteria, my code's run time reduced to 0.47 second.
After I read the discussion thread, I recommend everyone read lomont's post on the second page. It is a brief but interesting tutorial about Eisenstein integers.
Friday, May 31, 2013
project euler problem 194
Colored Configurations
This problem looks like quite difficult. Only 730 people solved it. But actually, it is quite simple, It is just a simple combination problem. Well, since the number is huge, we need a little bit help from computer to compute some parameters for our simple formula.
It runs under 1 ms.
This problem looks like quite difficult. Only 730 people solved it. But actually, it is quite simple, It is just a simple combination problem. Well, since the number is huge, we need a little bit help from computer to compute some parameters for our simple formula.
It runs under 1 ms.
project euler problem 192
Best Approximations
This problem is quite hard. My old code needs minutes to get the answer since I used my poor bigInteger class to find the best approximation. But if one asks google with appropriate key words, one can find some very useful web pages.
With the help of wikipedia, I find a better method. This method is quite fast, but for some situations, I still can not handle with only 64bit integers. I went back to my bigInteger class again to handle such situations and found the correct answer.
It takes 0.6 second.
This problem is quite hard. My old code needs minutes to get the answer since I used my poor bigInteger class to find the best approximation. But if one asks google with appropriate key words, one can find some very useful web pages.
With the help of wikipedia, I find a better method. This method is quite fast, but for some situations, I still can not handle with only 64bit integers. I went back to my bigInteger class again to handle such situations and found the correct answer.
It takes 0.6 second.
Thursday, May 30, 2013
project euler problem 193
Squarefree Numbers
This problem is not very difficult. There is a very famous principle to consider the double counting issue. I reviewed my old code and found it was not well written and takes 2.1 second to get the answer. This time I rewrote it with the same idea, it only takes 0.76 second.
I also tried to solve it with the idea I learned in problem 184. My code is not as efficient as Robert's code. I will reuse it when necessary. It is a great tool for more difficult problems.
This problem is not very difficult. There is a very famous principle to consider the double counting issue. I reviewed my old code and found it was not well written and takes 2.1 second to get the answer. This time I rewrote it with the same idea, it only takes 0.76 second.
I also tried to solve it with the idea I learned in problem 184. My code is not as efficient as Robert's code. I will reuse it when necessary. It is a great tool for more difficult problems.
Monday, May 27, 2013
project euler problem 191
Prize Strings
This is a simple dynamic programming problem. The time needed is less than 1 ms. I am surprised to find that I used a brute force style algorithm to get the answer in my old code.
This is a simple dynamic programming problem. The time needed is less than 1 ms. I am surprised to find that I used a brute force style algorithm to get the answer in my old code.
Sunday, May 26, 2013
project euler problem 189
Tri-colouring a triangular grid
I checked my old code. I could not fully understand it. I roughly understood that I was struggling with two different orientations of the triangles. But the run time is not too bad, 28ms.
I read the discussion today. I found that there was an easier way to solve the problem without considering too much about the orientations. The code is simple, easier to implement. But the only bad thing is that it took 0.6 second to get the answer.
But Robert_Gerbicz provided an ingenious way to solve the problem! (At least I found the algorithm in his post). It is much more efficient than his first approach. It is equivalent to use two different dynamic programmings in one problem.
I recommend everyone to read his post and figure out how his algorithm works. It is brilliant!
I checked my old code. I could not fully understand it. I roughly understood that I was struggling with two different orientations of the triangles. But the run time is not too bad, 28ms.
I read the discussion today. I found that there was an easier way to solve the problem without considering too much about the orientations. The code is simple, easier to implement. But the only bad thing is that it took 0.6 second to get the answer.
But Robert_Gerbicz provided an ingenious way to solve the problem! (At least I found the algorithm in his post). It is much more efficient than his first approach. It is equivalent to use two different dynamic programmings in one problem.
I recommend everyone to read his post and figure out how his algorithm works. It is brilliant!
Thursday, May 23, 2013
project euler problem 190
Maximising a weighted product
This is a simple problem. I solved it two minutes. A little bit calculus knowledge might be of help. If one has some knowledge about inequality, it can be easily solved.
This is a simple problem. I solved it two minutes. A little bit calculus knowledge might be of help. If one has some knowledge about inequality, it can be easily solved.
Wednesday, May 22, 2013
project euler problem 188
The hyperexponentiation of a number
Sigh! Another lesson of not learning from the discussion thread.
This problem needs a little bit background knowledge. It is called Euler's theorem. I think it is fair to reveal such kind of information. Otherwise, how can one solve this problem?
I do not even know there is a problem like this. After I solved this problem, I totally forgot it. I lost my old code. I do not even know how I solved it. Now I am trying to solve it again. I immediately realized how to solve it since I had experienced a hard time to solve problem 282: the Ackermann function. If I learned from problem 188, 282 is trivial.
Why 3390 people solved this problem but only 560 people solved problem 282? So many people left from project euler?
Sigh! Another lesson of not learning from the discussion thread.
This problem needs a little bit background knowledge. It is called Euler's theorem. I think it is fair to reveal such kind of information. Otherwise, how can one solve this problem?
I do not even know there is a problem like this. After I solved this problem, I totally forgot it. I lost my old code. I do not even know how I solved it. Now I am trying to solve it again. I immediately realized how to solve it since I had experienced a hard time to solve problem 282: the Ackermann function. If I learned from problem 188, 282 is trivial.
Why 3390 people solved this problem but only 560 people solved problem 282? So many people left from project euler?
project euler problem 187
Semiprimes
This is a really simple problem. It just shows the power of sieves one more time. No wonder more than 5500 people solved it.
This is a really simple problem. It just shows the power of sieves one more time. No wonder more than 5500 people solved it.
project euler problem 186
Connectedness of a network
This problem is simple if one have ever heard of the algorithm. I learned it in CLRS(ask google or amazon.com if you never heard of it). There is a chapter for this fancy data structure.
This problem is simple if one have ever heard of the algorithm. I learned it in CLRS(ask google or amazon.com if you never heard of it). There is a chapter for this fancy data structure.
project euler problem 185
Number Mind
This is one of the best problems in the first 200 problems. I really like this problem. But one thing I do not understand is that a lot of people solved it. Is it that simple?
This problem is very interesting and difficult. One does not need to have any background knowledge to solve this problem. I could not find a solution for a long time. I googled a lot and found some discussion from other forums. One mentioned that genetic algorithm may be used to solve this problem. I have no idea about genetic algorithm and found some knowledge in wikipedia. I followed the idea. I did not do well, but it was luckily solved in 2 to 3 minutes!
I reviewed the discussion. There are so many totally different approaches. I was surprised to find one from davy wybiral. He used some sort of simulated annealing algorithm. The run time is only two to three seconds! This is probably a rare problem that can be solved using random number algorithms
There are also a lot of other solutions. I want to understand hk's solution. But I do not know delphi. He solve the problem in 300 ms! What a pity! There are also some other great algorithms. I will update this post when I learned more.
This is one of the best problems in the first 200 problems. I really like this problem. But one thing I do not understand is that a lot of people solved it. Is it that simple?
This problem is very interesting and difficult. One does not need to have any background knowledge to solve this problem. I could not find a solution for a long time. I googled a lot and found some discussion from other forums. One mentioned that genetic algorithm may be used to solve this problem. I have no idea about genetic algorithm and found some knowledge in wikipedia. I followed the idea. I did not do well, but it was luckily solved in 2 to 3 minutes!
I reviewed the discussion. There are so many totally different approaches. I was surprised to find one from davy wybiral. He used some sort of simulated annealing algorithm. The run time is only two to three seconds! This is probably a rare problem that can be solved using random number algorithms
There are also a lot of other solutions. I want to understand hk's solution. But I do not know delphi. He solve the problem in 300 ms! What a pity! There are also some other great algorithms. I will update this post when I learned more.
project euler problem 184
Triangles containing the origin
A wonderful problem! If the radius is changed to 1200, I would say the difficulty is close to recent problems.
I did not notice how valuable it is when I first tried to solve it. My old code runs for 8 seconds. This time, I checked the discussion, I realized that I was almost doing brute force work on this problem. I used some wonderful properties of the problem, the run time is reduced to 0.07 second. Daniel challenged everyone for the case of r = 500. My code needs 34 second. I run Robert_Gerbicz's code. Oh, my god, 0.04 second, even faster than my r=105!
I reviewed his code, and found the trick that I missed. He is doing such a great job! There is some combinatoric property that we may explore. But this is not the end of the story! Robert find a much better algorithm and he can extend the problem to the case r = 2000000 solved in less than 1 minute!!!
IMHO, Robert beat everyone on this problem!
This is a great problem. I learned a great deal from Robert. I recommend everyone to take a look on Robert's second algorithm.
A wonderful problem! If the radius is changed to 1200, I would say the difficulty is close to recent problems.
I did not notice how valuable it is when I first tried to solve it. My old code runs for 8 seconds. This time, I checked the discussion, I realized that I was almost doing brute force work on this problem. I used some wonderful properties of the problem, the run time is reduced to 0.07 second. Daniel challenged everyone for the case of r = 500. My code needs 34 second. I run Robert_Gerbicz's code. Oh, my god, 0.04 second, even faster than my r=105!
I reviewed his code, and found the trick that I missed. He is doing such a great job! There is some combinatoric property that we may explore. But this is not the end of the story! Robert find a much better algorithm and he can extend the problem to the case r = 2000000 solved in less than 1 minute!!!
IMHO, Robert beat everyone on this problem!
This is a great problem. I learned a great deal from Robert. I recommend everyone to take a look on Robert's second algorithm.
Sunday, May 19, 2013
project euler problem 183
Maximum product of parts
This problem is too simple. I do not have anything to say about this problem.
This problem is too simple. I do not have anything to say about this problem.
project euler problem 182
RSA encryption
This problem is not very interesting. The math behind it is not very easy to figure out. But google can help a lot on this problem.
After I got the answer, I read the post by daniel.is.fischer and googled on the topic of m^e = m mod(p). I learned a lot from this problem.
This problem is not very interesting. The math behind it is not very easy to figure out. But google can help a lot on this problem.
After I got the answer, I read the post by daniel.is.fischer and googled on the topic of m^e = m mod(p). I learned a lot from this problem.
Saturday, May 18, 2013
project euler problem 181
Investigating in how many ways objects of two different colors can be grouped
This is an interesting problem. It is not so easy. What is more difficult is to implement an efficient algorithm.
My algorithm is trying to make each partition "ordered". But my code is not running very fast. It takes 1.8 second to get the answer.
After I checked the discussion. I found a very clever algorithm by daniel.is.fischer and implemented by Robert_Gerbicz. It is extremely fast, only need 4 ms or even less! This is an excellent example of dynamic programming!
This is an interesting problem. It is not so easy. What is more difficult is to implement an efficient algorithm.
My algorithm is trying to make each partition "ordered". But my code is not running very fast. It takes 1.8 second to get the answer.
After I checked the discussion. I found a very clever algorithm by daniel.is.fischer and implemented by Robert_Gerbicz. It is extremely fast, only need 4 ms or even less! This is an excellent example of dynamic programming!
Friday, May 17, 2013
project euler problem 180
Rational zeros of a function of three variables
This problem looks like very difficult, but actually the math and coding behind it is really simple. It is now only solved by 795 people. But at least 2000 people should have already solved it. One just needs to know a little bit about Fermat's story and a little bit about factorization.
60 ms.
This problem looks like very difficult, but actually the math and coding behind it is really simple. It is now only solved by 795 people. But at least 2000 people should have already solved it. One just needs to know a little bit about Fermat's story and a little bit about factorization.
60 ms.
Thursday, May 16, 2013
project euler problem 179
Consecutive positive divisors
Another simple problem, isn't it?
Yes, it is simple, but it is not so easy to get the answer in less than 0.3 second. I did not keep my old code, so I wrote one in five minutes. It takes 1.8 second to get the answer.
Then I checked some of discussion, I found I am too stupid that I missed an easy optimization. After that optimization, I can get the answer in 0.9 second.
I then checked robert_gerbicz's code. Oh, my god, he got it in 0.4 second! When I went to page 3, I found another interesting solution. ftfish managed to solve it in 0.3 second!
His algorithm is very interesting! (although cost a little bit more memory the robert's solution).
I learned some useful stuff for some more difficult problems.
Another simple problem, isn't it?
Yes, it is simple, but it is not so easy to get the answer in less than 0.3 second. I did not keep my old code, so I wrote one in five minutes. It takes 1.8 second to get the answer.
Then I checked some of discussion, I found I am too stupid that I missed an easy optimization. After that optimization, I can get the answer in 0.9 second.
I then checked robert_gerbicz's code. Oh, my god, he got it in 0.4 second! When I went to page 3, I found another interesting solution. ftfish managed to solve it in 0.3 second!
His algorithm is very interesting! (although cost a little bit more memory the robert's solution).
I learned some useful stuff for some more difficult problems.
project euler problem 178
step number
This is a very simple problem. It is no-brainer. It takes less than 4 ms.
This is a very simple problem. It is no-brainer. It takes less than 4 ms.
project euler problem 176
Rectangular triangles that share a cathetus
The problem looks like extremely difficult. But if you see this problem as a diophantine equation, it is not that difficult. Actually it can be calculated with a calculator.
The problem looks like extremely difficult. But if you see this problem as a diophantine equation, it is not that difficult. Actually it can be calculated with a calculator.
Wednesday, May 15, 2013
project euler problem 175
Fractions involving the number of different ways a number can be expressed as a sum of powers of 2
This problem is difficult, but no fun at all. I just observe the pattern for small numbers, and it is not too difficult to find what kind of numbers you are looking for. Then try to solve it.
Problem 169 is related to this problem.
This problem is difficult, but no fun at all. I just observe the pattern for small numbers, and it is not too difficult to find what kind of numbers you are looking for. Then try to solve it.
Problem 169 is related to this problem.
project euler problem 174
Counting the number of "hollow" square laminae that can form one, two, three, ... distinct arrangements
This problem is too simple. Everyone can solve it.
This problem is too simple. Everyone can solve it.
project euler problem 173
Using up to one million tiles how many different "hollow" square laminae can be formed?
This is a very simple problem. No wonder more than 4500 people solved it. I do not have anything to say about it.
This is a very simple problem. No wonder more than 4500 people solved it. I do not have anything to say about it.
Tuesday, May 14, 2013
project euler problem 172
Investigating numbers with few repeated digits
This problem is very similar to problem 171, another simple dynamic programming problem. Check the discussion of problem 171 if you feels this one difficult.
12ms.
This problem is very similar to problem 171, another simple dynamic programming problem. Check the discussion of problem 171 if you feels this one difficult.
12ms.
project euler problem 171
Finding numbers for which the sum of the squares of the digits is a square
My old code runs quite slow, needs 9 seconds to get the answer.
I changed my algorithm a little bit. My approach considered the combinations of those numbers and used recursion. It only takes 0.24 second to get the answer.
But it is still not good enough. I did not think thoroughly about this problem since my code runs quite fast. When I checked the discussion thread, I found that my approach is not as good as those guys who are using dynamic programming. I rewrote the code, it only needs 4ms to get the answer.
My old code runs quite slow, needs 9 seconds to get the answer.
I changed my algorithm a little bit. My approach considered the combinations of those numbers and used recursion. It only takes 0.24 second to get the answer.
But it is still not good enough. I did not think thoroughly about this problem since my code runs quite fast. When I checked the discussion thread, I found that my approach is not as good as those guys who are using dynamic programming. I rewrote the code, it only needs 4ms to get the answer.
Monday, May 13, 2013
project euler problem 170
Find the largest 0 to 9 pandigital that can be formed by concatenating products
This problem is not fun at all. I checked the discussion, I did not find any elegant method. A prev_permutation algorithm might be of help.
This problem is not fun at all. I checked the discussion, I did not find any elegant method. A prev_permutation algorithm might be of help.
project euler problem 169
Exploring the number of different ways a number can be expressed as a sum of powers of 2
This is a relatively simple problem. Although I did not find a recurrence relation for this problem. I still managed to explain it in my own way. less than 1 ms.
This is a relatively simple problem. Although I did not find a recurrence relation for this problem. I still managed to explain it in my own way. less than 1 ms.
Sunday, May 12, 2013
project euler problem 168
Number Rotations
This is a very simple problem. Why only 1284 people solved it ? Really strange.
I say it is simple because I solved a similar problem in elementary school. In that problem, I knew the multiplier is 3 and the last digit is 7 or something else. I followed the same idea, and solved it. It only needs 4 ms.
This is a very simple problem. Why only 1284 people solved it ? Really strange.
I say it is simple because I solved a similar problem in elementary school. In that problem, I knew the multiplier is 3 and the last digit is 7 or something else. I followed the same idea, and solved it. It only needs 4 ms.
project euler problem 167
Investigating Ulam sequences
I do not like this problem when I first tried to solve it simply because I googled a lot about this sequence and got a lot of information about it. Then I use some brute force method to solve it. It is fast, but I cheated. It took me 0.8 second.
Today, I read the discussion thread and find an algorithm that used bitset to solve this problem. I thought about it for some time, finally I understand why it works. Really amazing method! We can got the period and span with very simple code in a very short amount of time. It takes 60 ms to solve the whole problem!
I strongly recommend this problem! It is one of the most difficult problems in the first 200 problems. No wonder only 839 people solved it.
I do not like this problem when I first tried to solve it simply because I googled a lot about this sequence and got a lot of information about it. Then I use some brute force method to solve it. It is fast, but I cheated. It took me 0.8 second.
Today, I read the discussion thread and find an algorithm that used bitset to solve this problem. I thought about it for some time, finally I understand why it works. Really amazing method! We can got the period and span with very simple code in a very short amount of time. It takes 60 ms to solve the whole problem!
I strongly recommend this problem! It is one of the most difficult problems in the first 200 problems. No wonder only 839 people solved it.
Saturday, May 11, 2013
project euler problem 165
Intersections
This is a good exercise to learn a little bit computational geometry. I checked my old code. It takes 3.9 seconds to get the answer. I feels that my code is too slow but did not figure out how to speed it up.
I checked the discussion, Robert_Gerbicz gave me an idea how to optimize. It is very simple, avoid using set or map when possible. I followed his idea and removed set in my code, the run time is reduced to 1.4 second.
The set and map container are notorious in c++, probably because there was no hashset or hashmap available when STL was first published in 1990s. I had a lot of experience that set and map caused a lot of coding and performance issues.
This is a good exercise to learn a little bit computational geometry. I checked my old code. It takes 3.9 seconds to get the answer. I feels that my code is too slow but did not figure out how to speed it up.
I checked the discussion, Robert_Gerbicz gave me an idea how to optimize. It is very simple, avoid using set or map when possible. I followed his idea and removed set in my code, the run time is reduced to 1.4 second.
The set and map container are notorious in c++, probably because there was no hashset or hashmap available when STL was first published in 1990s. I had a lot of experience that set and map caused a lot of coding and performance issues.
project euler problem 166
Criss Cross
A not-so-interesting problem since most part of the problem is about brute force, but there is still something that we can explore. My old code needs 9.5 second to get the correct answer. I did not consider too much about how to stop the search if something is already invalid. So it is kind of pure brute force. This time I restricted the number of variables in the game to 8. The code runs much faster, only 0.26 second needed.
Update: I thought it over, there are two other symmetric properties that we may take advantage of. I would like to omit the first one since it is relative easy to find. The second is along the main diagonal in the very early stage of your loops. For example, a_{1,2} and a_{2,1} are symmetric. I changed my code just a little bit, the run time reduced to 0.144 second. Not bad!
A not-so-interesting problem since most part of the problem is about brute force, but there is still something that we can explore. My old code needs 9.5 second to get the correct answer. I did not consider too much about how to stop the search if something is already invalid. So it is kind of pure brute force. This time I restricted the number of variables in the game to 8. The code runs much faster, only 0.26 second needed.
Update: I thought it over, there are two other symmetric properties that we may take advantage of. I would like to omit the first one since it is relative easy to find. The second is along the main diagonal in the very early stage of your loops. For example, a_{1,2} and a_{2,1} are symmetric. I changed my code just a little bit, the run time reduced to 0.144 second. Not bad!
project euler problem 164
Numbers for which no three consecutive digits have a sum greater than a given value
This is a simple problem. No tricks in this problem. Use simple dynamic programming, it is solved. Less than 20 ms.
This is a simple problem. No tricks in this problem. Use simple dynamic programming, it is solved. Less than 20 ms.
Friday, May 10, 2013
project euler problem 162
Hexadecimal numbers
This is a simple problem. It can be solved analytically or using dynamic programming. I checked my old code. It still takes 0.4 second. This time I got a recursive relation, which got the result instantly.
This is a simple problem. It can be solved analytically or using dynamic programming. I checked my old code. It still takes 0.4 second. This time I got a recursive relation, which got the result instantly.
Wednesday, May 8, 2013
project euler problem 161
Triominoes
This is the first problem that is solved by less than 1000 people. 6 years has passed since this problem was posted. This might be one of the top five most difficult problem in the first 200 problems.
I checked my code, it runs quite fast. only 60 ms. The key point in this problem is to create states, find how states are converted from one to the other. Once this is done, the rest of the problem is just a very simple dynamic programming problem.
This is the first problem that is solved by less than 1000 people. 6 years has passed since this problem was posted. This might be one of the top five most difficult problem in the first 200 problems.
I checked my code, it runs quite fast. only 60 ms. The key point in this problem is to create states, find how states are converted from one to the other. Once this is done, the rest of the problem is just a very simple dynamic programming problem.
project euler problem 160
Factorial trailing digits
I like this problem. At first glance, it seems impossible to solve the problem since there are too many trailing zeroes for factorial(10^12). Then I took a look at my old code. I managed to get rid of all those 2 and 5 in the code. It works pretty good. Only 4 ms needed to solve this problem.
I like this problem. At first glance, it seems impossible to solve the problem since there are too many trailing zeroes for factorial(10^12). Then I took a look at my old code. I managed to get rid of all those 2 and 5 in the code. It works pretty good. Only 4 ms needed to solve this problem.
Tuesday, May 7, 2013
project euler problem 159
Digital root sums of factorisations
An excellent problem. I like it. Although it is easy to get the correct answer, but it is not that simple to solve it in 50 ms.
I checked my old code. I used pure brute force. It takes 3 seconds. I did some optimization and reduced to 0.5 second.
Then I read the discussion thread. I found the post from Robert_Gerbicz, a legendary figure in Project Euler forum. I tried his method. Oh, my god, he made it in 40ms. I read his post, it is really amazing!
An excellent problem. I like it. Although it is easy to get the correct answer, but it is not that simple to solve it in 50 ms.
I checked my old code. I used pure brute force. It takes 3 seconds. I did some optimization and reduced to 0.5 second.
Then I read the discussion thread. I found the post from Robert_Gerbicz, a legendary figure in Project Euler forum. I tried his method. Oh, my god, he made it in 40ms. I read his post, it is really amazing!
project euler problem 158
Exploring strings for which only one character comes lexicographically after its neighbor to the left
This problem is quite interesting. If one start from small numbers and organize things well, it is relatively easy to find the clue. The problem has an analytic expression. I was regret that I did not find it.
This problem is quite interesting. If one start from small numbers and organize things well, it is relatively easy to find the clue. The problem has an analytic expression. I was regret that I did not find it.
Monday, May 6, 2013
project euler problem 157
Solving the diophantine equation 1/a+1/b= p/10^n
This is a very simple problem. I did not see why only 1200 people solved it. If we can rephrase it, everybody can solve it. Actually, the list is a good hint, one need to investigate the list a little bit or reorder it.
This is a very simple problem. I did not see why only 1200 people solved it. If we can rephrase it, everybody can solve it. Actually, the list is a good hint, one need to investigate the list a little bit or reorder it.
view STL container using gdb
I am always using the gdb-stl-view to view vector or string values. It is very convenient to view those containers using command like pvec or pstr. But for some reasons, I cannot view set or map or priority_queue using pset and pmap.
Today, I searched for something to substitute it. I found a very useful webpage. The GDB 7.0 now include support for writing pretty-printers in Python. I followed the instruction and tried it. It works! The good thing is that you do not need to remember any command, just type "p vector_name", "p set_name" in terminal.
p myvec
std::vector of length 12, capacity 12 = {1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0}
p primeset
$15 = std::set with 17 elements = {
[0] = 11,
[1] = 17,
[2] = 19,
[3] = 23,
[4] = 29,
[5] = 31,
[6] = 37,
[7] = 41,
[8] = 43,
[9] = 47,
[10] = 53,
[11] = 59,
[12] = 61,
[13] = 67,
[14] = 71,
[15] = 73,
[16] = 79
}
You can also view iterator in the same way.
I do not know why I can not print an element of a vector(p myvec[2]) in my working place although I installed a gdb with-python. But I found that yolinux had updated the gdb-stl-view utility. I can view set or map using this utility again! I noticed the following comments in it.
Today, I searched for something to substitute it. I found a very useful webpage. The GDB 7.0 now include support for writing pretty-printers in Python. I followed the instruction and tried it. It works! The good thing is that you do not need to remember any command, just type "p vector_name", "p set_name" in terminal.
p myvec
std::vector of length 12, capacity 12 = {1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0}
p primeset
$15 = std::set with 17 elements = {
[0] = 11,
[1] = 17,
[2] = 19,
[3] = 23,
[4] = 29,
[5] = 31,
[6] = 37,
[7] = 41,
[8] = 43,
[9] = 47,
[10] = 53,
[11] = 59,
[12] = 61,
[13] = 67,
[14] = 71,
[15] = 73,
[16] = 79
}
You can also view iterator in the same way.
I do not know why I can not print an element of a vector(p myvec[2]) in my working place although I installed a gdb with-python. But I found that yolinux had updated the gdb-stl-view utility. I can view set or map using this utility again! I noticed the following comments in it.
# Modified to work with g++ 4.3 by Anders Elton # Also added _member functions, that instead of printing the entire class in map, prints a member.
project euler problem 152
Writing 1/2 as a sum of inverse squares
I checked my old code, it looks like OK. I used some sort of brute force method(but I tried my best to minimize the number of candidates, try to group the candidates, and consider large ones first). It only takes 1 second to get the answer. But after I changed the number limit from 80 to 100, I can not get the answer in 80 seconds! So it definitely needs to be optimized.
I am still working on it ...
The best solution is on page 2 in the discussion thread.
I checked my old code, it looks like OK. I used some sort of brute force method(but I tried my best to minimize the number of candidates, try to group the candidates, and consider large ones first). It only takes 1 second to get the answer. But after I changed the number limit from 80 to 100, I can not get the answer in 80 seconds! So it definitely needs to be optimized.
I am still working on it ...
The best solution is on page 2 in the discussion thread.
project euler problem 155
Counting Capacitor Circuits
My old code runs quite slow. I checked my code, I found that my code spent too much time on gcd. I optimized the code a little bit to reduce the cost and reduce the time from 18 second to 6 seconds.
I read the discussion thread and removed "set" in my code. It works faster. Only 1.1 second needed to get the answer. If I changed the number of capacitor to 20, It takes 8.5 second to get the answer.
Although I learned a little bit coding skill from the problem. This problem is somewhat flawed. The problem only considered simple connection in series or in parallel. It is possible to connect capacitors in Y or delta shape. Then the problem is very difficult to solve.
My old code runs quite slow. I checked my code, I found that my code spent too much time on gcd. I optimized the code a little bit to reduce the cost and reduce the time from 18 second to 6 seconds.
I read the discussion thread and removed "set" in my code. It works faster. Only 1.1 second needed to get the answer. If I changed the number of capacitor to 20, It takes 8.5 second to get the answer.
Although I learned a little bit coding skill from the problem. This problem is somewhat flawed. The problem only considered simple connection in series or in parallel. It is possible to connect capacitors in Y or delta shape. Then the problem is very difficult to solve.
Sunday, May 5, 2013
project euler problem 154
Exploring Pascal's pyramid
I lost my old code. What is embarrassing is that I do not know how to solve it after I read the problem. After sometime's thought, I decided to use brute force method(This proved to be the only way to solve it). After considering some symmetry property of this problem, I managed to reduce the run time to 6 seconds.
I checked some of the guy's code in c or c++, I found they can make it at 3 to 4 seconds! I compared the code for quite some time. Finally, I found that the order of checking criteria was very important since we run them for so many times! Just like if several conditions need to be checked, if we need to check gcd, it should always be the last one. Finally I can get the result in 3.5 seconds.
I lost my old code. What is embarrassing is that I do not know how to solve it after I read the problem. After sometime's thought, I decided to use brute force method(This proved to be the only way to solve it). After considering some symmetry property of this problem, I managed to reduce the run time to 6 seconds.
I checked some of the guy's code in c or c++, I found they can make it at 3 to 4 seconds! I compared the code for quite some time. Finally, I found that the order of checking criteria was very important since we run them for so many times! Just like if several conditions need to be checked, if we need to check gcd, it should always be the last one. Finally I can get the result in 3.5 seconds.
Saturday, May 4, 2013
project euler problem 153
Investigating Gaussian Integers
I checked my old code. It works, but the performance is poor, need 25 second to get the answer. I thought about it and then I found a very convenient formula for the problem when I was working on those real divisors. So I rewrote the code, and found the performance is greatly improved. It was reduced to 3 second.
Then I read the discussion thread, Eigenray gave a very useful expression which can further improve the performance(it is not so difficult to prove). I tried it, the run time is reduced to 1.5 second.
A great problem!
I checked my old code. It works, but the performance is poor, need 25 second to get the answer. I thought about it and then I found a very convenient formula for the problem when I was working on those real divisors. So I rewrote the code, and found the performance is greatly improved. It was reduced to 3 second.
Then I read the discussion thread, Eigenray gave a very useful expression which can further improve the performance(it is not so difficult to prove). I tried it, the run time is reduced to 1.5 second.
A great problem!
Subscribe to:
Posts (Atom)