ghoshsai5000's blog

How to convert a dynamic programming problem to a binary exponentiation problem ?
By ghoshsai5000, history, 8 years ago, In English

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 ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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:

as we go on finding the next values, we are basically multiplying the matrix as many times. In this way, you can find that value of f(D) for nth step in O(logn). For binary exponentiation of matrix and its applications, see this.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply