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.
No comments:
Post a Comment