project euler problem 413

One child number

This problem is an interesting dynamic programming problem. It does not take me too long to figure out  how to solve the problem. 

I first used a lazy vector to handle the key component of the problem. It soon works after I fixed a couple of bugs. The issue was that my code ran too slow. I then found a better format to reorganize the data, the hashmap! The hashmap use less memory and better performance. But I did not write out a very detailed plan. It proved that this was a unwise decision. I made several stupid mistake and sometime contradictory implementation.  It takes me several hours debugging the code and actually making a plan during debugging. I should write out the plan before coding even if it is a rewrite. Finally I got it write again, the code runs for 6 seconds.

project euler problem 469

Empty Chairs

This is an interesting problem. But it is simple if one find the shortcut. I would not tell anything about the shortcut. It is fast to solve but you lose a lot to learn if you are only interested in the solution to be submitted. 

I investigated the problem a little bit and then find a recurrent equation. It is routine to find the differential equation that needs to be solved. I asked "Mr. wolframalpha" to solve the equation for me, then the problem becomes easy and clear. When I got the final solution, I was surprised that the result is related to one of Euler's well known contribution to math. I hope everyone can enjoy the problem.

Project Euler problem 443

GCD Sequence

This is an easy problem. It has been solved by 340 people in 4 months. Usually the difficult problems can only be solved by less than 150 people.  The problem is easy since it just take a few moment to find out how to solve the problem. Look at the sequence to 1e6 then one can figure out how to solve the problem. The problem is relative easy since the sequence up to 1e6 can be built in less than 1 second with purely brute force code. It takes two seconds to get the correct answer.

Project Euler problem 449

Chocolate covered candy

I do not like this problem too much since this is just a basic calculus problem, but it is not that straight forward to solve and the accuracy required is pretty high. One need to project the points on the old surface to the new one, it takes a little bit time to figure out how to find the volume, but anyway, it is an easy problem. 

project euler problem 452

long products

This problems looks very challenging, but actually it is not since the product is limited to 1e9 and 2^30 > 1e9.  But to solve the PE problems, we cannot be too lazy. I first tried to use recursion to solve the problem without any optimization, for those two given numbers, 10 takes no time, but 1e6 takes a little bit of time, this is a bad symptom. I then tried 1e9, it is extremely slow. But after a moment's thought, I found that I was too lazy and some basic optimization was omitted.  After one hour or so, the problem is solved. Not very difficult but need to keep optimization in mind!

project euler problem 458

Permutations of Project

I do not remember when I solved 3 PE problems in just one day. But it was definitely a long time ago. Just on March 24,  I solved 3 relatively easy PE problems in one day! 

I read the problem for 5 minutes or so before I fully I understood the problem. I was in the mood that I should use 26 letters! But after that the problem is simple and straight forward. The technique was used at least 3 times in previous problems, for example, problem 237, one of my favorite problems. After I set up everything correct, the first shot gave the correct answer.  Do not be misled by 7^7-7!(when did you see PE problem makers tell you how to solve the problem?), if you want to try it in a combinatoric way, you would struggle with the problem in a hard way.

project euler problem 461

Almost Pi

This problem is an easy problem if one plays with PE for some time. It uses the same algorithm as problem 266.

The algorithm is very fascinating! I really love the algorithm because I had a very painful time when I tried to solve problem 266. But this time, everything is easy! I wrote the code for 15 minutes or so and my first trial is the correct one.

project euler problem 463

A weird recurrence relation  

 I did not solve any PE problems recently because my work kept me very busy and I read some books recently such as Richard Stanley's famous book  Enumerative Combinatorics. It is an excellent book, but it takes a lot of time, the problems at the end of each chapter are very challenging!

 Just a couple days ago, I took a look at recent PE problems and found some of the problems are quite simple, for example, problem 463. 

This problem is not interesting at all. The recurrent equations looks difficult to human beings, but it is trivial for computers. After half an hour's coding and a few minutes debugging, the problem is solved!