shahianshu's blog

By shahianshu, history, 10 months 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

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have the same query!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shahianshu (previous revision, new revision, compare).

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
10 months 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.

  • »
    »
    10 months 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??

    • »
      »
      »
      9 months 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.

  • »
    »
    10 months 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.

»
10 months 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 :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    And how is that you arrived at this formula? could you explain the proof.

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I wrote my idea in this link. (It's second answers). Sorry for my english.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    9 months 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.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shahianshu (previous revision, new revision, compare).