project euler problem 083 path sum: four ways

The problem is not hard to solve once I realized that this is a standard problem for Dijkstra's algorithm. I used priority_queue in STL to solve this problem and succeeded. Everything looks great and I immediately started working on the next problem.

But I did not think it over. I read the related sections about the Dijkstra in CLRS.
One paragraph is focused on a function called decreaseKey. The weird thing is that there is no such functionality in STL and CLRS has no code snippet for it. So I just ignored it! 

My experience with later-on project euler problems was awful when I can recognize that it is a Dijkstra problem, but with STL, my code ran extremely slow and required huge amount of memory! The root cause is simply that I do not have a function to fulfill the functionality of decreaseKey!

I reviewed this problem for one time two years ago, but I did not review the problem carefully and missed another learning opportunity!

The projecteuler+ on this problem also requires an efficient implementation of Dijkstra.

Learning is of top priority and the number of problem solved is not that important!

project euler 054

Poker Hands

This problem is easy but a little bit boring. And it is not really hard to get the correct answer.  One thing that I found in hackerrank.com is that my code give the wrong answer on a special straight or straight flush like
"1H 2H 3H 4H 5H     2H 3H 4H 5H 6H". The second hand is larger that the first hand.

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!