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]=0 , dp[2]=1 and dp[3]=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]=0 , dp[2]=1 , dp[3]=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].
Complexity :O(nlogn)
Solution: https://ideone.com/ST5D6r
Related Problems :
Practice : https://www.codechef.com/problems/BYTES12
Contest : https://www.codechef.com/BYTE2016/problems/BYTES12