Hack Lockdown 1.0 Editorials

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.

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

can u please explain the solution of SIMNUM briefly.