Sort 162 Discussions, By:
Please Login in order to post a comment
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.
Thank you :)
Keep solving :)
I used up a lot of time, can you please improve sir?
Can you help me please. I dont know why I'm getting bad answer from the test case 9
What is the concept of cahing and meomization you mentioned above? Could you please explain me about that. Or please tell me where can I get informatio about that for clear understanding. I always do programming in C only. Is that concept works in C language?
Have you studied dynamic programming? If not, I suggest you do. It will teach you those concepts:).
Finally passed all tests with my Python3 implementation without timing out. Some lessons learned:
I've followed all your suggestions, but I still get timed out. What am I doing wrong?
cache_limit = 5000001
results =  * cache_limit
results = 1
if starting_number < cache_limit and results[starting_number - 1] != 0:
return results[starting_number - 1]
result = 0
if starting_number % 2 == 0:
result = 1 + create_sequence(starting_number >>1)
result = 1 + create_sequence(3 * starting_number + 1)
if starting_number < cache_limit:
results[starting_number-1] = result
for i in range(1, 5000000):
t = int(input().strip())
for a0 in range(t):
n = int(input().strip())
print(n - results[0:n][::-1].index(max(results[0:n])))
The issue was on the last line of code, where I was looking for the max lenght for every n. I've just created a second list with the actual results for each n before reading the input and it worked!
Some Hints To Solve This :-
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.......
using namespace std;
typedef unsigned long long int ulli;
typedef signed long long int lli;
ulli *arr=new ulli;
ulli countchain(ulli num)
// cout<<num<<" : "<<arr[num]<<endl;
//cout<<a<<" : "<<countchain(a)<<endl;
ulli *results=new ulli;
Indeed very beautiful solution and indeed very well written
thank for your good idea ! you write "recursion" very good ,
it help me pass 3 last testcases;
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.
ya facing the same problem.. altough it is pretty much acceptable that python being a interpreted language is a bit slower than C or Java...
I was able to solve it in Python 3. It passes all test cases.
I use recursive functions and all computations is done before reading the inputs.
I'm struggling tp solve it in Python3. My code is: http://termbin.com/9rft
When I try to precompute up to 5*10^6 I get MemoryError
I tried to use lru_cache from functuls: in this case I can stay in memory, but test are timeouted at 10 seconds.
I had to do it in C. If I try the same concept on python it gets timed out. Sad.
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.
You are doing too much complications
Keep it simple
keep 1 array for lookups and what you can't find compute and store.
Some un-necessary things that you can remove immediately
Dictionary keys to be integers and not string
remove main function, it take 1 extra second
remove try/catch bring in if/else
eliminationg try/except along with keeping dict keys ints and removing the main function seemed to get the program running at the required speed. Unfortunately for the last few tests I would get runtime errors which I assume was a result the inefficient data storage of a dictionary. Converted the system to a list and it passes fine. So thanks for your assistance.
we can remove main function? that sounded weird in java... guess that can be done in python
finally got it...
don't use dict,
To explain: use the array to cache when n is in scope, otherwise we just compute the result on the fly.
I am getting runtime error!!!
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.
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 i in range(1,5*10**6):
for i in range(1,5*10**6):
for i in range(num):
could u please explain why did u used this range range(1,5*10**6)
that the range given in question so..
For the ones who are struggling with Python3: the trick for me was to swtich from dictionaries to list