Odd period square roots
This problem is interesting in the early problems. My method is not elegant and I learned a little bit math in the discussion thread which I have no idea how to prove it. My method ran in 0.1 second and my new version only take 0.02 second.
The old day's project Euler problem are quite friendly. For example, This
problem only asks find the numbers less than 10,000. If this problem is posted in 2013, I guess it might be 1,000,000 or even larger.
I tested my code, if the number changed to 1,000,000. My old version takes 29.6s while new version takes 7s. Not too bad.
Wednesday, February 27, 2013
Monday, February 25, 2013
project euler problem 223 and 224
Almost right-angled triangles
Let us first take a look how many people solved these two problems.
Problem 223: 732
Problem 224: 626
No doubt, problem 224 are much more difficult than problem 223. But here
is a pitfall that almost all new project euler users (including me) are get trapped. We cared about how many problems we solved much more
than how these problems are solved. We seldom take part in the brainstorm in
the discussion thread for each problem. There is some very sad truth. We can do much better and learn much more and save a lot of time in the future if we read the post carefully and give these problems a second shot.
These two problems are very good examples.
Problem 223 can be solved in some kind of brute force way but 224 cannot.
If one solved problem 223 and read the discussion, one may find that there
is a very clever way to solve problem 224 just in the first page. But why there is still more than 100 people did not solve problem 224?
Let us first take a look how many people solved these two problems.
Problem 223: 732
Problem 224: 626
No doubt, problem 224 are much more difficult than problem 223. But here
is a pitfall that almost all new project euler users (including me) are get trapped. We cared about how many problems we solved much more
than how these problems are solved. We seldom take part in the brainstorm in
the discussion thread for each problem. There is some very sad truth. We can do much better and learn much more and save a lot of time in the future if we read the post carefully and give these problems a second shot.
These two problems are very good examples.
Problem 223 can be solved in some kind of brute force way but 224 cannot.
If one solved problem 223 and read the discussion, one may find that there
is a very clever way to solve problem 224 just in the first page. But why there is still more than 100 people did not solve problem 224?
project euler problem 316
Numbers in decimal expansions
This is another probability problem. I knew how to solve it from the very beginning, but my code is not very efficient. I also got accuracy issues in this problem. But I was too lazy to rewrite the code and somehow managed to solve it.
If you do not know how to solve such kind of problem, try to read some probability book. You will find how to solve such kind of problems. For example,
Introduction to probability models by Ross Sheldon
This is another probability problem. I knew how to solve it from the very beginning, but my code is not very efficient. I also got accuracy issues in this problem. But I was too lazy to rewrite the code and somehow managed to solve it.
If you do not know how to solve such kind of problem, try to read some probability book. You will find how to solve such kind of problems. For example,
Introduction to probability models by Ross Sheldon
project euler problem 280
ants and seeds
I have studied probability theory for some time, and I thought that I should not have too much difficulty to solve probability problems, but actually I still have quite a few probability problems unsolved.
This is a probability and combinatoric problem. It looks quite difficult at first thought but after I tried, it is actually not difficult at all. I recently began to use Lapack and I tried Lapack in this problem. The code runs quite fast, only 1.4 second, with some potential for further optimization.
After I solved this problem, I read some posts in discussion thread and luckytoilet's blog since I knew that he has two post about this problem (I resist the temptation to read it before I solved the problem). I am surprised to find that there is quite a few different approaches to solve it. I believe my method is quite straight forward and efficient. Maybe the combinatoric part scared the people.
Manually solve a 2x2 problem is helpful to solve the 5x5 problem.
Excellent problem! I like it.
I have studied probability theory for some time, and I thought that I should not have too much difficulty to solve probability problems, but actually I still have quite a few probability problems unsolved.
This is a probability and combinatoric problem. It looks quite difficult at first thought but after I tried, it is actually not difficult at all. I recently began to use Lapack and I tried Lapack in this problem. The code runs quite fast, only 1.4 second, with some potential for further optimization.
After I solved this problem, I read some posts in discussion thread and luckytoilet's blog since I knew that he has two post about this problem (I resist the temptation to read it before I solved the problem). I am surprised to find that there is quite a few different approaches to solve it. I believe my method is quite straight forward and efficient. Maybe the combinatoric part scared the people.
Manually solve a 2x2 problem is helpful to solve the 5x5 problem.
Excellent problem! I like it.
Saturday, February 23, 2013
project euler problem 368
A Kempner-like series
This problem does not look like a puzzle but a research project. After some reading from Internet, the problem is solved. The idea behind the problem is very interesting.
If the key word Kempner is not provided in the problem, it may take me a lot more time.
This problem does not look like a puzzle but a research project. After some reading from Internet, the problem is solved. The idea behind the problem is very interesting.
If the key word Kempner is not provided in the problem, it may take me a lot more time.
Thursday, February 21, 2013
project euler problem 395
Pythagorean tree
The graph looks nice, but the problem is not so interesting. If you have some
graph tools, it helps a lot. Otherwise accuracy is always a headache.....
The graph looks nice, but the problem is not so interesting. If you have some
graph tools, it helps a lot. Otherwise accuracy is always a headache.....
Wednesday, February 20, 2013
project euler problem 269
Polynomials with at least one integer root
This problem is only solved by 400 people. But actually it is not a so difficult problem. I just felt that it was too complicated to consider all situations and never gave it a try.
Finally I decided to solve it. I am surprised to find that it was not difficult to implement. The algorithm was used again and again in PE problems. The code ran very fast, less than 0.1 second.
The math involved is not that much(All the ideas involved has been used many times). If you go this far, you definitely can solve it.
This problem is only solved by 400 people. But actually it is not a so difficult problem. I just felt that it was too complicated to consider all situations and never gave it a try.
Finally I decided to solve it. I am surprised to find that it was not difficult to implement. The algorithm was used again and again in PE problems. The code ran very fast, less than 0.1 second.
The math involved is not that much(All the ideas involved has been used many times). If you go this far, you definitely can solve it.
Monday, February 18, 2013
project euler problem 255
Rounded Square Roots
The first time I saw this problem, I feels that this is a Monte Carlo problem. But I did not try MC, since that is a no-brainer. No way! There are so many
14 digits number and the problem asked for 10 decimal places.
I thought about this problem for months, I always got bored by it in a few minutes.
Then finally one day I see something in 5 digits case. The problem is solved. I love it so much now! Evil!
I feel problems between 250 and 260 are very difficult to solve.
252 convex hole
253 caterpillar
254 sum of digit factorial
255 rounded square root
256 tatami
257 angular bisetctor
258 lagged fibonacci sequence
261 pivotal square sum
Some of the problems are still unsolved, some of them took me very long time to figure
out how to solve.
I am addicted to PE.....
The first time I saw this problem, I feels that this is a Monte Carlo problem. But I did not try MC, since that is a no-brainer. No way! There are so many
14 digits number and the problem asked for 10 decimal places.
I thought about this problem for months, I always got bored by it in a few minutes.
Then finally one day I see something in 5 digits case. The problem is solved. I love it so much now! Evil!
I feel problems between 250 and 260 are very difficult to solve.
252 convex hole
253 caterpillar
254 sum of digit factorial
255 rounded square root
256 tatami
257 angular bisetctor
258 lagged fibonacci sequence
261 pivotal square sum
Some of the problems are still unsolved, some of them took me very long time to figure
out how to solve.
I am addicted to PE.....
project euler problem 177
Integer angled Quadrilaterals
I solved this problem after I solved more than 300 problems. I was worried about accuracy too much. But actually it is not an issue. Two key words need one's attention, convexity and distinct (non-similar) solutions. I strongly recommend one to solve it independently. After I solved it, I was so happy! However it is not an easy problem. More than five years passed, only 600+ people solved this problem. So this is definitely the most difficult problem in the first 200 PE problem.
I am curious how this problem is created. Genius!
I solved this problem after I solved more than 300 problems. I was worried about accuracy too much. But actually it is not an issue. Two key words need one's attention, convexity and distinct (non-similar) solutions. I strongly recommend one to solve it independently. After I solved it, I was so happy! However it is not an easy problem. More than five years passed, only 600+ people solved this problem. So this is definitely the most difficult problem in the first 200 PE problem.
I am curious how this problem is created. Genius!
project euler problem 237
Tours on a 4 x n playing board
A very interesting problem. There are two ways to solve it , a mathematical way and a CS way, both are very interesting. The method I learned in the discussion thread was used again and again in other problems.
I feel this problem is a difficult one. But more than 800 peoples solved this problem. It is amazing!
A very interesting problem. There are two ways to solve it , a mathematical way and a CS way, both are very interesting. The method I learned in the discussion thread was used again and again in other problems.
I feel this problem is a difficult one. But more than 800 peoples solved this problem. It is amazing!
project euler problem 253
tidying up
A very difficult probability problem. It takes me quite some time to write the code for a brute force method(well, it is not Monte Carlo). I found it was too slow, and also took too much memory. Then based on this brute force version, I did some optimization to reduce the memory cost since something are actually equivalent. However, after the optimization, It still took 16 seconds.
Please read the discussion thread, there is a very smart way to solve this problem.
A very difficult probability problem. It takes me quite some time to write the code for a brute force method(well, it is not Monte Carlo). I found it was too slow, and also took too much memory. Then based on this brute force version, I did some optimization to reduce the memory cost since something are actually equivalent. However, after the optimization, It still took 16 seconds.
Please read the discussion thread, there is a very smart way to solve this problem.
project euler problem 356
largest roots of cubic polynomials
Interesting problem! Evil problem! 'Simple' problem!
After I solved it, it looks so simple. Why I can not solve it for months? Well, I did get a somewhat not so useful hint from the PE forum a long time ago. One guy suggested to solve problem 318 first. (It is actually very helpful!)
Finally, something came to my mind and I found how these two problems are related to each other. There is a little bit math involved in it, but this is very popular, everyone knows about it. I learned the knowledge in high school. Well, in this problem, it is a little bit more complicated than high school math.
There is still another programming component in this problem for you to identify, this part is not difficult since some earlier problems has used it a couple of times.
If you still cannot solve this problem, please stare at the title of this problem for 1 minute.
Interesting problem! Evil problem! 'Simple' problem!
After I solved it, it looks so simple. Why I can not solve it for months? Well, I did get a somewhat not so useful hint from the PE forum a long time ago. One guy suggested to solve problem 318 first. (It is actually very helpful!)
Finally, something came to my mind and I found how these two problems are related to each other. There is a little bit math involved in it, but this is very popular, everyone knows about it. I learned the knowledge in high school. Well, in this problem, it is a little bit more complicated than high school math.
There is still another programming component in this problem for you to identify, this part is not difficult since some earlier problems has used it a couple of times.
If you still cannot solve this problem, please stare at the title of this problem for 1 minute.
Sunday, February 17, 2013
project euler problem 025
1000 digits fibonacci number
a pure mathematical flavor problem. No coding needed if you read fibonacci number on wikipedia.
a pure mathematical flavor problem. No coding needed if you read fibonacci number on wikipedia.
project euler problem 024
Lexicographic permutations
Permutation is a routine task for programming. STL is ideal for this problem since it has next_permutation in "algorithm".
Problem 336: Maximix Arrangements is a little bit more difficult problem. But the idea is similar.
There is a trick to speed up these two problems. Using the same idea, the problem may be solved by hand.
My code runs for 8ms.
Permutation is a routine task for programming. STL is ideal for this problem since it has next_permutation in "algorithm".
Problem 336: Maximix Arrangements is a little bit more difficult problem. But the idea is similar.
There is a trick to speed up these two problems. Using the same idea, the problem may be solved by hand.
My code runs for 8ms.
project euler problem 023
non abundant sums
check my comments on problem 021, same method. Once the algorithm is understood, this problem is simple.
Probably the most difficult one so far.
check my comments on problem 021, same method. Once the algorithm is understood, this problem is simple.
Probably the most difficult one so far.
project euler problem 021
amicable numbers
There is a neat solution in the discussion thread. It got 5 kudos, which worth a careful read(in page 1)! This problem is very similar to problem 12.
There is a neat solution in the discussion thread. It got 5 kudos, which worth a careful read(in page 1)! This problem is very similar to problem 12.
project euler problem 020
factorial digit sum
simple and fast.
bigInteger is not necessary.
simple and fast.
bigInteger is not necessary.
project euler problem 019
counting sundays
another boring problem. But just a few such kind of problem.
another boring problem. But just a few such kind of problem.
project euler problem 018, 067
maximum path sum
If you can solve problem 15, this one is similar.
If you say you can brute force it, can you brute force problem 67?
Project euler become more interesting when one solved more than 150 problems simply because the answer to the problems are huge and cannot be solved by brute force and solving a PE problem is such a fantastic pleasure.
If you can solve problem 15, this one is similar.
If you say you can brute force it, can you brute force problem 67?
Project euler become more interesting when one solved more than 150 problems simply because the answer to the problems are huge and cannot be solved by brute force and solving a PE problem is such a fantastic pleasure.
project euler problem 017
number letter count
I do not like this problem. Very boring.
I do not like this problem. Very boring.
project euler problem 016
power digit sum
problem is simple. but a neat solution is not that easy.
There are many ways to solve this problem. mathematica, python, gmp, etc.
My first version also used my bigInteger class. But actually this is overkill.
One may use two bitset as carry and one vector to solve this problem. I learnt
this in the discussion thread.
problem is simple. but a neat solution is not that easy.
There are many ways to solve this problem. mathematica, python, gmp, etc.
My first version also used my bigInteger class. But actually this is overkill.
One may use two bitset as carry and one vector to solve this problem. I learnt
this in the discussion thread.
project euler problem 015
lattice paths
In math, it is a combination problem. Very simple and straight forward.
But I would like to treat it as a dynamic programming problem. There are so many dynamic programming problems in PE.
Actually, just set some points to be inadmissible, the problem is much harder, see problem 408. Dynamic programming still helps in solving the problem. Well not very efficient though. There is a brilliant approach to solve 408!
In math, it is a combination problem. Very simple and straight forward.
But I would like to treat it as a dynamic programming problem. There are so many dynamic programming problems in PE.
Actually, just set some points to be inadmissible, the problem is much harder, see problem 408. Dynamic programming still helps in solving the problem. Well not very efficient though. There is a brilliant approach to solve 408!
project euler problem 014
It looks like this problem is relatively easy since brute force is not that slow.
My code takes 0.4s.
My code takes 0.4s.
project euler problem 013
large sum
I do not have my original code for this problem, but probably I used my bigInteger class. After reviewing this problem, I realized that it is not necessary to use such kind of tools, long long is sufficient.
"
Well, unless the test case is a corner case with flood of "9s. This is something that projectEuler did poorly in early problems. Later on, the problem is always a sum of different cases which is harder to pass for buggy code.
I do not have my original code for this problem, but probably I used my bigInteger class. After reviewing this problem, I realized that it is not necessary to use such kind of tools, long long is sufficient.
"
Well, unless the test case is a corner case with flood of "9s. This is something that projectEuler did poorly in early problems. Later on, the problem is always a sum of different cases which is harder to pass for buggy code.
project euler problem 012
This is not a difficult problem. You may try a much more difficult one, problem 378. After I solved 378, I feel my divisor function is too complicated.
I rewrote the code, now it has only 30 lines. It took 0.004 second (my debug version).
I rewrote the code, now it has only 30 lines. It took 0.004 second (my debug version).
Saturday, February 16, 2013
project euler problem 011
largest product in a grid
I do not like such kind of problem, Basically, we need to brute force it. However, your code should not exceed 0.5 second. Otherwise, you need to check your code.
Update:
I read my code a few days ago, I failed to understand what was going on in my code. It was really messy! I found that I used meaningless variable names like i, j, k and use some magic numbers like 17 and 37, etc. The logic under the code is not lucid at all.
I started trying to modify the old code, and begin to use meaningful names like row and col. After a few minutes, I found that some of my code can be reorganized in a simpler way. I did it and then found a better way to handle the main diagonal and off-diagonal. The code is cleaner now and very easy to understand.
I should be more serious on all coding problems even if I got the correct answer and the problem is believed to be really simple!
I do not like such kind of problem, Basically, we need to brute force it. However, your code should not exceed 0.5 second. Otherwise, you need to check your code.
Update:
I read my code a few days ago, I failed to understand what was going on in my code. It was really messy! I found that I used meaningless variable names like i, j, k and use some magic numbers like 17 and 37, etc. The logic under the code is not lucid at all.
I started trying to modify the old code, and begin to use meaningful names like row and col. After a few minutes, I found that some of my code can be reorganized in a simpler way. I did it and then found a better way to handle the main diagonal and off-diagonal. The code is cleaner now and very easy to understand.
I should be more serious on all coding problems even if I got the correct answer and the problem is believed to be really simple!
project euler problem 010, very interesting problem
If you can solve problem 7, there is no difficulty to solve this one. This can be a very simple problem using the sieve method.
But if you are really interested to count the primes or count the sum of primes under N, the sieve method is not efficient at all when N is large. In the discussion of this problem, a dynamic programming approach is suggested and it is a fast method to count prime numbers. Please do not miss the opportunity to learn if you do not know this method! The code is written in python, and lucy did an excellent job in his post!
But if you are really interested to count the primes or count the sum of primes under N, the sieve method is not efficient at all when N is large. In the discussion of this problem, a dynamic programming approach is suggested and it is a fast method to count prime numbers. Please do not miss the opportunity to learn if you do not know this method! The code is written in python, and lucy did an excellent job in his post!
project euler problem 009
Special Pythagorean triplet
This problem is easy. There are many different approaches. If you use brute force on this problem(sqrt, check whether a number is an integer, etc), please learn from the discussion thread. The best approach is used again and again in many project Euler problems.
This problem is easy. There are many different approaches. If you use brute force on this problem(sqrt, check whether a number is an integer, etc), please learn from the discussion thread. The best approach is used again and again in many project Euler problems.
project euler problem 008
largest product in series
Very basic problem.
Very basic problem.
project euler problem 007
This is a warm-up problem. Very basic. Read the discussion thread if your code took more than 0.2 second.
project euler problem 006
sum square difference
please do it in O(1) time;
please do it in O(1) time;
project euler problem 005
smallest multiple
calculator problem, every one can solve it.
calculator problem, every one can solve it.
project euler problem 004
largest palindrome product
This problem is simple. We will see other palindromic numbers related problems later.
This problem is simple. We will see other palindromic numbers related problems later.
project euler problem 003
largest prime factor
I use C or C++ to solve project euler problems. But I rarely use long long in coding. After I solved 50 to 100 problems, I found long long is necessity. The problem is easy, even one use some kind of brute force method. One may read the book from CLRS and try some fancy method.
It is interesting to notice that for most of the project euler problems that require an integer as an answer, number is usually less than 2^64.
I use C or C++ to solve project euler problems. But I rarely use long long in coding. After I solved 50 to 100 problems, I found long long is necessity. The problem is easy, even one use some kind of brute force method. One may read the book from CLRS and try some fancy method.
It is interesting to notice that for most of the project euler problems that require an integer as an answer, number is usually less than 2^64.
project euler problem 002
even Fibonacci numbers
around problem 400, there are a lot of problems about Fibonacci numbers. Some on quite difficult to solve. This one is the easiest one that is somewhat related to Fibonacci number.
around problem 400, there are a lot of problems about Fibonacci numbers. Some on quite difficult to solve. This one is the easiest one that is somewhat related to Fibonacci number.
project euler problem 001
Multiples of 3 and 5
I first started working on project euler in Aug 2011, I really enjoyed solving most of the problems.
This is an extremely easy problem, everyone can solve it. No comments needed.
I first started working on project euler in Aug 2011, I really enjoyed solving most of the problems.
This is an extremely easy problem, everyone can solve it. No comments needed.
Subscribe to:
Posts (Atom)