Hello,
BBRICKS — link
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.
Thanks in advance :)
update :- the blog written by abba5 explains the solution of the problem using matrix exponentiation very nicely .
I have the same query!
Can someone please explain the solution, I am very curious now.
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.could you please explain how to remove the first dimension by matrix exponentiation??
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.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.
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 :)
https://discuss.codechef.com/questions/140916/bbricks-solution-using-matrix-exponentiation May be this will be helpful to you
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.