Sort 182 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:).
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;
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!
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.
This has helped me. My final mistake was that I used a dictionary for storing the results. After storing them in an array, all the tests passed.
I had to do it in C. If I try the same concept on python it gets timed out. Sad.