Sort 7 Discussions, By:
Please Login in order to post a comment
you can find my java solution here
Very easy after all the training from previous problems. At the beginning, generate a list of all sums of factors in a manner similar to how we use Sieve of Eratosthenes. You may refer to Problem 21 which is related to amicable numbers.
Then use a queue to trace the chain for every iteration, and only update the answer if an occurrence of the first element in the chain is found (though you would still have to break the chain if there is any repeating element, otherwise it will never quit). You may refer to Problem 74 which is related to measuring the length of a chain.
Note that every member in the same chain has the same length, so once you are done with the smallest member, you won't have to care about the rest. As a result, you should store the intermediate elements you've gone through so you don't have to do the same thing again, as they are definitely not a smallest element in the chain, or you would have seen them before (because you've finished every candidate smaller than it before this iteration step).
And, you may have noticed, that not every number can form a chain in this case. For example, when you hit a prime number, it goes to and stops at .
Small hint if you're still struggling with time constaints, the result doesn't change for N>1E6.
Debug info from gdb:
Could not attach to process. If your uid matches the uid of the target
process, check the setting of /proc/sys/kernel/yama/ptrace_scope, or try
again as the root user. For more details, see /etc/sysctl.d/10-ptrace.conf
ptrace: Operation not permitted.
Got a SIGSEGV while executing native code. This usually indicates
a fatal error in the mono runtime or one of the native libraries
thi is what i got...
Is there a time constraint for problems like these, my code takes more than 30 seconds for n = 16000 , PS. Im new to hackerrank contests