Tobby_And_Friends's blog

Matrix exponentiation for 2 Dimensional Recurrence
By Tobby_And_Friends, history, 7 years ago, In English

I was trying this problem from SPOJ: http://www.spoj.com/problems/LVADER/en/. I figured out the recurrence for the problem which is f(x, y) = f(x — 1, y) + f(x, y — 1) + f(x — 1, y — 1), f(x, 0) = f(0, y) = 1. The constraints of the problem does not allow me to use normal DP and I'm not aware how to use matrix exponentiation technique for 2-D recurrence. I read this article: https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation but I could not fully understand the idea. Any help is really appreciated.

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

(We can always translate Luke's position to (0, 0).) Sorry if something is unclear, please clarify if needed.

With matrix exponentiation, you have a list of subsets of states, where the transitions between these states are (almost) the same. For instance, in the "find n-th Fibonacci number in O(logn)" problem, the 'subsets of states' are (Fn - 1, Fn) for positive n.

What could the subsets of states be?
What simple problem does this look like?
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Read up this — Delannoy Numbers. You don't need Matrix Exponentiation here.

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Can anyone provide some standard tutorial/resources to learn it. I stuck on a task of october long challenge :(

→ Reply