Problem Description :
Given an integer N find the smallest time it takes to reach 0 if you can jump only factor length of the current block you are currently on backwards.
Problem Type : Easy-Medium/DP
Short Explanation :
Run a sieve and take a dp array with dp=0 , dp=1 and dp=1 .Run a loop from 3 to n and dp[i] would be 1+ min(dp[of all factors of i] ) .Final answer is dp[n] .
Detailed Exxplanation :
Run the sieve and for each number store the smallest prime number .
Now construct a dp array with dp=0 , dp=1 , dp=1 and run a loop from 3 to n .
For each i the answer to that ith state will be :
dp[i] = 1+ min(dp[all factors of i] )
where we can easily find all the factors of i in each step in log( n ) time using the array of smallest prime factor for each number we created during sieve .Final answer will be dp[n].
Related Problems :
Practice : https://www.codechef.com/problems/BYTES12