project euler problem 350

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.

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.

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.

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.

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.

project euler problem 116, 117

Red, green or blue tiles

This problem is too simple. Coding takes less than 5 minutes. I used a function that was used in problem 113, 114, then I got the answer.

Problem 117 is just a little bit more difficult than problem 116, but it is still easier than 113 and 114. My code runs less than 1ms.

These two problem should have been solved by more than 10000 people. 

project euler problem 113

Non-bouncy numbers

I did not think about the problem and directly go to computer for help. The problem is simple, which can be solved by dynamic programming. But after I read the discussion, I suddenly realize that this problem can be solved analytically.   

Think more about this problem before coding!

project euler problem 111

Primes with runs

From problem 110, the answer became large, so nobody can guess. And this also force us to think about some clever ways to solve the problem. 

I checked my old code, it is not too bad, so I decided not to rewrite it. To solve problem like this one,  I learned how to find the next combination number, something like next_permutation in STL. If one does not want to do it this way, the easiest way is probably recursion.

It takes 24ms to get the answer,  not bad.

project euler problem 364

Comfortable distance

This problem is not a very difficult one. But in my opinion, it is not easy.

When I first tried to solve this problem, the first and the last seat are quite troublesome. I also felt that occupancy of one seat would affect its neighbors,  so it was difficult to use dynamic programming method.  

I thought it over and finally found that this was just an relatively complicated combination problem. Several different situations needs to be handled. In each situation, it is relatively easy to find the number of ways to make all people seated following the rule. 

My code's efficiency is not too bad. It takes less than 0.6 second to get the correct answer. 

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.