Tobby_And_Friends's blog

By Tobby_And_Friends, history, 2 years ago, , 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.  Comments (4)
 » (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?Take note that they have to be chosen in such a way that they have consistent transitions. A natural choice would be the number of ways Luke can reach the cells on 2 consecutive diagonals. For instance, [(2, 0), (1, 1), (0, 2), (1, 0), (1, 1)] would be the 2nd subset, consisting of the 2nd and 3rd rightmost diagonal. The transitions would be: - for the lower diagonal, just copy the values of the previous upper diagonal, - for the higher diagonal, in each cell, sum up the values of there Luke could have been before this. Note that these locations are always in the last 2 diagonals. Is this performant?Matrix exponentiation is O(n3logk), where n is the dimension of the matrix, and k is the exponent. The problem is, n is quite big for something cubed in the complexity, so although there does exist a matrix exponentiation solution, it might not be fast enough What simple problem does this look like?Let's say Luke was not allowed to make diagonal moves. Then I think you can derive a closed-form using combinations. (Hint: think of making a string of "Up" and "Right" that moves Luke. How many strings gets you to Vader?) Why think about this?The one thing preventing us from using this are the diagonal moves. Why? Because a string of "Up", "Right" and "UpRight" that brings us to Vader does not have a fixed length. However, the bounds allow us (I think, I have not paid close attention to the complexity) to iterate across the length of this string (or, more accurately, the number of "UpRight"s), and count how many strings of such length get you to the destination.
 » Read up this — Delannoy Numbers. You don't need Matrix Exponentiation here.
 » Can anyone provide some standard tutorial/resources to learn it. I stuck on a task of october long challenge :(
•  » » Wait until the bloody contest is over.