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.

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.

Some Hints To Solve This :-

1. Use MEMOIZATION.
2. Recursion can be Super-Useful.
3. 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

4. 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;
}

Thought I did it well. And then I saw the Editorial.

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.

Been banging my heads against this one for a while, and I've just completely run out of ideas for ways to increase the efficiency. I'm working in python 2. I would love if someone could take a look at this submission and perhaps nudge me towards a better solution. https://www.hackerrank.com/contests/projecteuler/challenges/euler014/submissions/code/2416055

I am getting case 0 to 4 proper, but case 5 to 8 are returned as wrong answer and remaining cases goes for time out. https://www.hackerrank.com/contests/projecteuler/challenges/euler014/submissions/code/1301211928

Lesson learned: Caching is important for speed but don't cache everything. A naive approach is to use a built-in cache like "lru_cache" or set up your own cache using a dictionary to store everything. But there are too many numbers to cache; I kept track of the highest number occuring in a Collatz sequence after running N up to 5x10^6: 1318802294932. That number and other high numbers will likely never be called once they are cached. Set the cache to only store lengths for numbers less than 5 million or so. If a number is less than your chosen cache size then don't store it. Then, because your cache size is set, use a list instead of a dictionary to save space. I used Python 3.

For the ones who are struggling with Python3: the trick for me was to swtich from dictionaries to list