### shahianshu's blog

By shahianshu, history, 15 months ago, ,

Hello,

in the editorial for the problem BBRICKS one of the guy posted his solution which uses matrix exponentiation to solve the problem and i couldn't make much from his solution on how to solve the question using matrix exponentiation, so if anyone could please just tell me how this problem can be solved using matrix exponentiation.

solution which uses matrix exponentiation

Even the editorialist has no clue on how to solve it using matrix exponentiation.

update :- the blog written by abba5 explains the solution of the problem using matrix exponentiation very nicely .

• +12

 » 15 months ago, # |   0 I have the same query!
 » 15 months ago, # |   0 Auto comment: topic has been updated by shahianshu (previous revision, new revision, compare).
 » 15 months ago, # |   +3 Can someone please explain the solution, I am very curious now.
 » 15 months ago, # |   0 You should start by solving it with dp[N][K][state of last two columns]. The second dimension denotes the number of bricks already used. Then you remove the first dimension by matrix exponentiation.
•  » » 15 months ago, # ^ |   +3 could you please explain how to remove the first dimension by matrix exponentiation??
•  » » » 15 months ago, # ^ |   +1 Forget about [K] for a moment (so, now we count all possible ways, not caring about the number of bricks). Then apply the matrix exponentiation just like in computing the n-th Fibonacci number.And that [K] gives us one extra dimension. You can see in the code you linked that it's represented as a vector, and multiplied like a polynomial.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +1 Errichto can you please explain what what will be transformation matrix and how to find it? You can probably make a video for the solution and explain it there. DP with matrix exponentiation with multiple dimension is a difficult topic to learn. You can help out many of us.
 » 15 months ago, # |   +1 This can be actually converted into a single dimension dp by the formula:i*D(i) = 2*(n-k+1)*D(i-1) + (i-2)*D(i-2); D(0)=1 and D(1)=2*(n-k+1)Compute for i in range 2<=i<=k, answer is D(k) Try yourself for the proof :)
•  » » 6 months ago, # ^ |   0 And how is that you arrived at this formula? could you explain the proof.
 » 15 months ago, # | ← Rev. 2 →   0 I wrote my idea in this link. (It's second answers). Sorry for my english.
 » 14 months ago, # |   0 https://discuss.codechef.com/questions/140916/bbricks-solution-using-matrix-exponentiation May be this will be helpful to you
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 Hi, when I wrote the editorial, when I came up with the solution for sub task #1, I knew of this solution, using method of generating functions and matrix expo.It can be solved in O(23·k·logk·logN) time using fft using this method, but that would be a huge overkill and UN-necessary info IMO, and hence I did not mention it, since the problem can be solved using basic combinatorical interpretation in O(K) time.
 » 13 months ago, # |   0 Auto comment: topic has been updated by shahianshu (previous revision, new revision, compare).