shahianshu's blog

How to solve BBRICKS of codechef using matrix exponentiation ?
By shahianshu, history, 6 years ago, In English

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 .

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

Comments Comments (9)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have the same query!

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

Can someone please explain the solution, I am very curious now.

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

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    could you please explain how to remove the first dimension by matrix exponentiation??

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

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

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 :)

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

https://discuss.codechef.com/questions/140916/bbricks-solution-using-matrix-exponentiation May be this will be helpful to you

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply