×

# BBRICKS solution using Matrix Exponentiation

 6 3 Problem In this Editorial solve this problem using Matrix Exponentiation and polynomial. This logic is not mine but I understood by the comment in BBRICKS EDITORIAL (vuvth) First observation this question can be solve by DP my first solution for 25 point is using 3 state DP $dp(position, remain, previous\ brick) =dp(n, k, 0/1)$ in this equation i can say that if previous brick is 0 then i can skip this state or i have two chance where to color brick $dp(n, k, 0) = dp(n -1, k , 0 ) + 2\ dp(n - 1, k - 1, 1 )$ but if previous brick is 1 then i can skip this state or i have one chance to color brick because I can not color adjacent brick so $dp(n, k, 1) = dp(n -1, k , 0 ) + dp(n - 1, k - 1, 1 )$ for ans is $dp(n+1,k,0)$ using bottom-up approach we define array dp[2][k][2] and solve. but after some observation and help of OEIS I found two state dp :- $dp(n,k) = dp(n-1, k) + dp(n-1, k-1) + dp(n -2, k -1) \ \ ... \ \ (1)$ $if \ (k > n) \ then \ dp(n,k) = 0$ it is equation $Eq - 1$ which help us most in matrix exponentiation we define polynomial $T(n) = dp(n,n)\ x^n + dp(n, n - 1) \ x^\left(n-1\right) + ...+dp(n,0) x^0$ now put $Eq - 1$ in polynomial Equation you will find new recurrence relation (its really easy to see) you just need pen and paper $T(n) = (x + 1)\ T(n-1) + x\ T(n-2)$ so we got Equation which can be use in matrix exponentiation $\begin{bmatrix} \ T(n + 1)\ \\ T(n) \end{bmatrix} = \begin{bmatrix} \ x + 1 & x\ \\ 1 &0 \end{bmatrix} \begin{bmatrix} \ T(n)\ \\ T(n-1) \end{bmatrix}$ $\begin{bmatrix} \ T(n + 1)\ \\ T(n) \end{bmatrix} = \begin{bmatrix} \ x + 1 & x\ \\ 1 &0 \end{bmatrix}^n \begin{bmatrix} \ T(1)\ \\ T(0) \end{bmatrix}$ $where \ T(1) = 2x + 1\ and\ T(0) = 1$ but for $N = 10^9$ we can't make array but here is the good news $K <= 1000$ only make array for size $k+1$ we don't require more at end we need to find coefficient of $x^k$ to do we just multiply $(2x + 1)(x(1,0)) + x(1,1)$ and sum of $x^k$ coefficient will be your ans this is my code and this code from where I understood the idea. Time complexity $O ( lgN \ 8 \ k^2 )$ some people find ans in $O(k)$ using this equation but i don't know how it comes so please comment if someone have proof $D(i) = (2\ (n-k+1)\ D(i-1) + (i-2)\ D(i-2))/i$ $D(0)=1 \ and \ D(1)=2\ (n-k+1)$ for more information about Matrix exponentiation asked 21 Nov '18, 18:57 5★abba5 113●3 accept rate: 0%

 0 finally , thanks brother. answered 03 Dec '18, 17:48 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,212
×303
×35
×11

question asked: 21 Nov '18, 18:57

question was seen: 890 times

last updated: 03 Dec '18, 17:48