Sort 166 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.
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.
I wonder how it is possible to perform all calculations in runtime using Python. I copied the code from Editorial and it runs on my machine for more than 1 minute to finish all calculations. My own solution can obtain the same results in 20 seconds, but it's still too slow for submission. If it is TopCoder or Google Code Jam it would be disastrous.
Code from editorial runs in 11s on my relatively old CPU. Hackerrank environment has faster CPU cores and it runs in less than 10 seconds.
Sorry for asking old topic but does anyone finish this challenge by ruby?
I can't finish when set the max number is 5*10^6, seem like the speed of ruby is not enough :(
this is my code, please help me find out :(
# Enter your code here. Read input from STDIN. Print output to STDOUT
t = gets.strip.to_i
def steps n
start = 0
break if n == 1
if n % 2 == 0
n = n / 2
n = 3*n + 1
start += 1
numbers = [1,1,2]
max = 5000000
current_number = 2
current_step = 1
(3..max).each do |number|
step = steps(number)
if step >= current_step
current_number = number
current_step = step
numbers << current_number
t.times do |time|
n = gets.strip.to_i
steps() using full loop is too slow. You can use recursion and memoization. But whith memoization there is a problem how to fit in memomory.