can u explain how to solve it
Bro I uses different test cases.
Yes, will try my test in the next contest.
Thanks for the suggestion buddy.
1 Like
Its a simple dynamic programming problem
Step1:- Precompute all prime factors of number at ith index in an adjacentcy list
Step2:- Apply Top down Dp approach same as you apply for finding paths reaching nth step using recursion +dp
Step3 go for every prime factor in both the directions and update the dp[i][j],
where dp[i][j]=true if and only if you reached i in exactly j steps.
MY Simple solution can describe more.
Solution
1 Like
Thanks for explanation but I see many solution using matrix exponentiation.
Any idea?
My solution was of pure recursion ā¦ It was giving TLE, but after setting max. recursive calls, it ran in almost 0.97 sec with ACā¦
I avoided visited placesā¦
I caught the point that if we have cycles then we can actually waste some moves to sum up to M(if we reach last position before M moves)
You could find solution here
We donāt need to compute all primes since N<=40 and we cannot jump more than 37 steps
We can just check in the first 12 primes.
O(1) solution for SMVOL using 64-bit integers.
If n = 1 : return 1
Else return 2*(4+3*n*(n-2))
It is derived from the fact that a^3 - b^3 = (a-b)^3 + 3*a*b*(a-b).
Substitute a= n;b = n-2; and solve.
1 Like
same approach ,that cube term got cancelled
1 Like
Ya If you consider my solution I am also oscillating inside the bounds 1 to n and not outside the bonds that why I will not go for all primes in my recursive dp. I have just precomputed as I refrain from writing certain checks with if and else and putting such extra things which will obviously not fetch me nothing less than 0.73 sec solution.
1 Like