You are not logged in. Please login at www.codechef.com to post your questions!

×

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

abba5's gravatar image

5★abba5
1133
accept rate: 0%

edited 21 Nov '18, 19:27


finally , thanks brother.

link

answered 03 Dec '18, 17:48

toxico_brains's gravatar image

3★toxico_brains
11
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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