darkshadows's blog

By darkshadows, 10 years ago, In English

Hi all,

I have tried to write a tutorial on how matrix exponentiation can be used in dynamic programming. Check the post out!

http://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation

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

»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

There is a neater and more intuitive way (in my opinion) to realize the solutions of the non linear recurrences.

It uses the number of paths in a graph of length N. (Exponentiate the adjency matrix of the graph to N and the value of the (i, j)th element in the exponentiated matrix is the number of paths of length N from the ith vertex to jth vertex).

Now, in each of these problems, consider the states as vertices and keep on adding edges from each vertex and then find the answer. :)

Like, in "ASC1 Nice Patterns Strike Back", each bitmask is a vertex, from each bitmask, find to which all bitmasks you can go by checking all of the others. The graph is made! Now simply exponentiate and find the answer! :)

In, World War II, a vertex will be represented in a triplet (i, j) i.e. (coloumn number, row number % 2) i.e. a total of 60 vertices. According to the given rules, the transitions should be fairly obvious. :)

Finally in "Solving the Practice contest", a vertex is a triplet, (number of problems coded by k % K, was the last problem coded by J, has V coded any problem), there are 40 such vertices. Once you build the graph and exponentiate, the answer will be the number of paths from (0, 0, 0) to (0, 1, 1) and from (0, 0, 0) to (0, 0, 1). :D