I did my first dynamic programming problem successfully today here The editorial says that it can be solved int (log n) time with binary exponentiation of a 2x2 matrix. Can someone tell me how to convert a dynamic programming problem into a binary exponentiation problem ?
I don't want code. I want to practice the coding and implementation part myself. I want to know how to get the matrix from the recursive equations.
Let f(X, n) represent the number of paths ending in D with n moves left if the ant is at vertex X.
Then, f(D, 0) = 1, f(A/B/C, 0) = 0
Also, f(D, n) = 3f(A/B/C, n-1) f(A/B/C, n) = f(D, n-1) + 2f(A/B/C, n — 1)
How can I convert these equations into a matrix which needs to be exponentiated ?
You can see that from state n we always go to state n + 1. We need two values f(D), f(ABC).
The following is true:
Thanks a lot ! The insight that n can be written as a power of the function rather than another argument to the function solved it for me. I understand now. Only one question — I understood how the algorithm takes a logarithmic number of multiplications in n, but doesn't matrix multiplication itself take cubic time ? Also, can you recommend some simple problems from this website where I can apply binary exponentiation ? Thanks.
Thanks a lot for your help. I learnt a lot and got acceptance too. Can you recommend some problems on this website which use this concept ?