BBRICKS - Editorial
#Problem Link :
[Division 1][1]
[Division 2][2]
#Author : [Jannik][3]
#Tester : [Misha Chorniy][4]
#Editorialist : [Anand Jaisingh][5]
#Pre-Requisites :
Binomial Coefficients
#Problem :
You are given $2 \times N $ grid. Now, you need to color $K$ cells in this grid, such that no two colored cells are adjacent. Find the number of ways to do so.
#Explanation :
First of all, we can obviously note that no two bricks will be placed in the same column. So, let's just forget this scenario. Let us try and find the number of ways to place $k$ bricks so that no two adjacent columns contain a brick in the same row.
**Sub-task #1 :**
Here, $N$ is only up to $1000$. So, we can maybe write some kind of $O(N \cdot K ) $ dp, to pass this subtask. Consider the following dp :
$ dp[i][j] $ = Number of ways to place $ j $ bricks among the first $i$ columns in a valid way, such that the $i^{th}$ column contains the last brick placed.
So, $ dp[i][j] = \sum_{k=0}^{i-2} dp[k][j-1] \cdot 2 + dp[i-1][j-1] $. If any column $ \le i-2 $ contains the last placed brick, then we can place a new brick in the $i^{th}$ column in any of the two rows, and if the $(i-1)^{th}$ row contains the last placed brick, then we can place a brick in the $i^{th}$ column only in the row not equal to the row of the $(i-1)^{th}$ column's brick.
But this $ dp $ is still $ O(N^2 \cdot K) $. We can optimize this dp, coming to $ dp[i][j] = dp[i-1][j-1]+dp[i-2][j-1]+dp[i-1][j]$. pre-compute dp[i-1][j-1]+dp[i-2][j-1]+dp[i-1][j]$, by using prefix sum optimization. Just compare the terms difference in the terms added by $dp[i][j]$ and $dp[i-1][j]$ tp get to this faster recurrence. Pre-compute this dp for all $1 \le n,k \le 1000$, and we can for fixed $N,K$ sum up all values $ dp[i][K] , K \ i \le N $.
Time Complexity $ O(maxn \cdot maxk + \sum N_i ) $, where $ maxn=maxk=1000 $
**Sub-task #2 :**
Here , $N$ is up to $ 10^9 $. Now, we need to make more observations. Let us consider the state each column can be in. Let the state $\left[{1\atop 0}\right]$ denote we place a brick in the first row of this column, and nothing in the second row, Similarly, let the state $ \left[{0\atop 1}\right]$ denote we place a brick in the second row and nothing in the first row, and let the state containing all zeros denote we place nothing in this row. Now, we need exactly $ K $ columns to be in state $ 1/2$ and the rest in state $3$.
Also, in the final arrangement we need that no two columns that are in state $1/2$ to be adjacent to a column in the same state. Let's rename the states, consider state $ 1= a$, state $ 2 = b $ and state $ 3 = c $. We can now solve an equavalent problem : Find the number of $N$ length strings of character-set $ {a,b,c} $ consisting of exactly $K$ $a/b's$, such that no two $a's$ are adjacent and no two $b's$ are adjacent.
Now, consider the number of $i$ length strings consisting of only $ a/b's $ and the number of positions $j$ where a character equals its previous character. We can store this in $ f(i,j)$,
$ f(1,0)={a,b}=2 $
$ f(i,j)=f(i-1,j)+f(i-1,j-1)$.
We can pre-compute this table in $O(K^2)$ time. Now, for a fixed $N,K$, the answer is :
$ \sum_{j=0}^{k-1} f[k][j] \cdot \binom{n-j}{k} $. This can be derived from the stars and bars method. We have finished placing the $a's$ and $b's$, $k$ of them and we have $n-k$ $c's$ left. Now, when there are exactly $j$ positions when a character equals its previous character, then we compulsorily need to place a $c$ between them. Let's try and place $c's $ in between any $2$ adjacent positions in the string of length $k$, or in the beginning/end.
So, this is : we have to represent the number $n-k$ as the sum of $k+1$ numbers, but $j$ numbers have to be at least $1$. So, by the stars and bars method, this is :
$ \binom{k+1+n-k-j-1}{k+1-1} = \binom{n-j}{k}$.
Now, $\binom{i}{j}= \frac{i}{ j! \cdot (i-j)! }$, We can calculate this by first taking product of all integers $x, x \le i, x > (i-j)$ , there can be at max $k$ such numbers, and then multiplying by $ (j!)^{-1} $, which we can pre-compute initially in $O(K) time $
It is easy to prove that $ f(i,j)$ is actually a binomial coefficient multiplied by some constant. So, we can also solve this problem in $O(K)$ time per test too, without using $O(K^2)$ pre-computation, enabling solutions for $ K \le 10^5 $ too, but that is unnecessary here.
As a closing comment, I have to say, many people might have just used oeis, and if that site didn't exist, the number of ac submissions might have been lower.
#Time Complexity : $ O ( K^2 + T \cdot K^2 ) $
Also, you can read about multiple different solutions to this problem in the comments section below, check it out.
#My Code : [Link][6]
[1]: https://www.codechef.com/OCT18A/problems/BBRICKS
[2]: https://www.codechef.com/OCT18B/problems/BBRICKS
[3]: https://www.codechef.com/users/neutron_byte
[4]: https://www.codechef.com/users/mgch
[5]: https://www.codechef.com/users/anand20
[6]: https://www.ideone.com/pDcORE