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 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. 

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.

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.

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!

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.

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? 

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.

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.

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.

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 183

Maximum product of parts

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. 

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!

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.

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. 

project euler problem 178

step number

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. 

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.

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.  

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. 

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. 

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. 

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. 

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.

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.

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.

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.

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!

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. 

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. 

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.

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.

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!

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 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.

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.

#   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.

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.

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.

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!

project euler problem 151

Paper sheets of standard sizes: an expected-value problem

I checked my old code today. I was surprised to find that I used monte carlo method to run simulations. I do not know how I get the right answer at that time. But I simulated 1e8 times, still quite far from the correct answer. Shame on me!

I rewrote the code, using an appropriate method to solve it. Actually it is a simple Markov chain problem. The size of the matrix is very small. But to generate the matrix, it takes me quite a while. Then it is solved in 50 ms. There are a few Markov chain problems in PE, this one being the simplest one.

Update: I read the discussion thread, I realized that my matrix solver is a dense one, so it cost a lot of unnecessary computation. I rewrote the code, in a recursive way, solved the problem in 2 ms.

project euler problem 383

Divisibility comparison between factorials

This problem is not quite interesting. But from this problem, I realize that learning something is more important than just solving some problems! 

I have been reviewing all my solved problems recently, and after I learned something from an old problem, I realized that I should give this problem a shot.

Since the problem asks n < 10^18, we can not check each number. The first thing is to find an equivalent problem that can be relatively easy solved. If you say you cannot find it, I would recommend you to review all problem between 140 and 150 and read TAOCP volume 1, 1.2.6 exercise. 

The second thing is to solve this relatively easy problem. I should admit that the logic is still not so straight forward to be translated into code. I spent quite some time debugging n=100 and n=1000 until I found that I have some logic error. After that, the problem is solved with in 1 ms!