We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Project Euler #14: Longest Collatz sequence
Project Euler #14: Longest Collatz sequence
GiorgianB + 0 comments Thanks for this problem. Is was very interesting, and taught me the value of caching and meomization. Also learned some techique about it while doing so.Thanks shashank21j.
Tashaion + 0 comments Some Hints To Solve This :-
- Use MEMOIZATION.
- Recursion can be Super-Useful.
- Take care of special-cases:- i.)if x=x*3+1 ,for cache[x] x>5000001 it can be error or deadlock,because we declared cache[5000001] only
At last to find max result ,use memoization too ,means store the result already.
i am giving my solution ,which passed all test cases successfully.......
#include <bits/stdc++.h> using namespace std; typedef unsigned long long int ulli; typedef signed long long int lli; ulli *arr=new ulli[5000001]; ulli countchain(ulli num) { ulli temp=0; // cout<<num<<" : "<<arr[num]<<endl; if(arr[num]!=0) { return arr[num]; } if(num%2==0) { temp=num/2; arr[num]=1+countchain(temp); return arr[num]; } temp=num*3+1; ulli count=1; while(temp>5000001) { if(temp%2==0) { temp/=2; } else { temp=temp*3+1; } count++; } arr[num]=count+countchain(temp); return arr[num]; } int main() { memset(arr,0,sizeof(arr)); ulli count=0; arr[1]=1; for(ulli a=2;a<=5000001;a=a*2) { ++count; arr[a]=count; } for(ulli a=1;a<=5000001;++a) { //cout<<a<<" : "<<countchain(a)<<endl; countchain(a); } ulli *results=new ulli[5000001]; results[1]=1; for(ulli a=2;a<=5000001;++a) { if(arr[a]>=arr[results[a-1]]) { results[a]=a; } else { results[a]=results[a-1]; } } ulli test_case=0; cin>>test_case; ulli end_number,max_answer=0,result=0; while(test_case--) { cin>>end_number; cout<<results[end_number]<<endl; } delete[] results; delete[] arr; return 0; }
sean_wlx + 0 comments Finally passed all tests with my Python3 implementation without timing out. Some lessons learned:
- Casting is very expensive, so instead of doing divide + cast to int, try doing shift
- Python dictionaries are insanely expensive compared to lists
- Lists are expensive compared to storing state in the framestack, aka recursion
- Getting fancy with pre-computing low-hanging fruit results usually doesn't pay off, just keep it simple. Exhaustive search with memoization is fast enough.
luka_null + 0 comments Did anyone solve this in Python3? I spend 2 hours trying to optimize the code, but I still get a timeout during memoization. Same code in Java runs in under 1s.
c650Alpha + 0 comments Thought I did it well. And then I saw the Editorial.
Load more conversations
Sort 186 Discussions, By:
Please Login in order to post a comment