BYTES12 - Editorial

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

//