Problem Link :Author : JannikTester : Misha ChorniyEditorialist : Anand JaisinghPreRequisites :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. Subtask #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}^{i2} dp[k][j1] \cdot 2 + dp[i1][j1] $. If any column $ \le i2 $ 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 $(i1)^{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 $(i1)^{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[i1][j1]+dp[i2][j1]+dp[i1][j]$, by using prefix sum optimization. Just compare the terms difference in the terms added by $dp[i][j]$ and $dp[i1][j]$ tp get to this faster recurrence. Precompute 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 $ Subtask #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 characterset $ {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(i1,j)+f(i1,j1)$. We can precompute this table in $O(K^2)$ time. Now, for a fixed $N,K$, the answer is : $ \sum_{j=0}^{k1} f[k][j] \cdot \binom{nj}{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 $nk$ $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 $nk$ 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+nkj1}{k+11} = \binom{nj}{k}$. Now, $\binom{i}{j}= \frac{i}{ j! \cdot (ij)! }$, We can calculate this by first taking product of all integers $x, x \le i, x > (ij)$ , there can be at max $k$ such numbers, and then multiplying by $ (j!)^{1} $, which we can precompute 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)$ precomputation, 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
This question is marked "community wiki".
asked 20 Oct '18, 15:21

Here is my solution (code). Using Matrix exponentiation. answered 21 Oct '18, 16:56
1
this is cool, do you mind explaining your solution ?
(22 Oct '18, 16:49)
Assume T(n) = dp(n, n) * x^n + dp(n, n  1) * x^(n  1) + ... + dp(n, 0) * x^0 => T(n) = (x + 1)T(n  1) + xT(n  2). We want dp(N, K) with K <= 1000 so we store first (K + 1) first element of T(n) and calculate on this. Use Matrix exponentiation [T(n) T(n  1)] (x +1) 1 = [T(n + 1) T(n)]
Cost for multiplication two matrix is O(8 * K ^ 2). Sorry for my english. Happy coding <3.
(03 Nov '18, 15:26)

I solved it by Let f(n, k) denote the answer then we have the recurrence $$f(n, k)  f(n  1, k) = f(n 1, k  1) + f(n 1, k  2) $$ Now $f(n, 1) = 2n$, which is linear, which implies that $f(n, 2)$ must be quadratic, which implies that $f(n, 3)$ must be cubic and so on.. So for fixed $k$, $f(n, k)$ will be a kth degree polynomial in $n$, and therefore i precomputed $f(n, k)$ for $n, k$ upto 2000 and then I answered queries in $O(n)$ using Lagrange Interpolation. So overall time complexity $O(K^2 + TN)$ answered 20 Oct '18, 20:14

Here is a nice paper: Selections Without Adjacency on a Rectangular Grid I tried everything written here before I noticed what was wrong in my solution, a little bug in binomial mod function :P answered 20 Oct '18, 16:20

This can also be solved fully using divide and conquer with Dynamic programming. Direction of this approach: Break the 2 * n matrix into two halves. Now, (number of ways to fill k bricks in 2 * n matrix) will be equal to (number of ways to fill 0 brick in left half) * (number of ways to fill k tiles in right half) + (number of ways to fill 1 brick in left half) * (number of ways to fill k1 brick in right half) + ...other terms. Recurrent relation will look similar to this. (n, k) = (n/2, 0)(nn/2, k0) + (n/2, 1)(nn/2, k1) + ..... + (n/2, k1)(n/2, 1) + (n/2, k)(n/2, 0) NOTE: This is not correct relation. Try to think in this direction. Time complexity of this solution is O(k^2 * log(n)). answered 20 Oct '18, 19:43

Here is my short and simple solution. Number of ways = (Number of ways of forming i nonempty groups of k columns) * (Number of ways of placing this i groups around nk columns) *for i=1,2,3..k* Number of ways of forming i groups of k columns = (Number of ways of distributing k objects into i groups) * (2^i) where in each group alternate bricks of row 1,2 are selected and each group can have two orientation (either first brick is from first row or second) Thus, Number of ways = sum( (k1)C(i1) * 2^i * (nk+1)C(i) ) for i=1,2,..k Extended the logic of single row to two rows :) ... Time Complexity = O( T . K^2 ) answered 22 Oct '18, 16:30

Why? How? Where did this derivation come from? What I mean to point out is, dont you think its highly weird to just write the recurrence here as "we can optimize this to ___" and skip the part of how we got that? No offence, but I feel skipping of that part shouldnt be done. BTW  Anguepa's answer here is a very neat explanation of how to derive the recurrence  https://math.stackexchange.com/questions/2945440/numberofwaystoselectknonadjacentboxesina2timesnboard/2945878 answered 20 Oct '18, 16:31
It's simply prefix sum optimization. I think anyone who reads both recurrences properly, will understand that quite easily.
(21 Oct '18, 17:31)
2
Still, I feel if we can write a part or explain about something, we shouldnt just assume that anyone familiar with it will get it. The editorial is also for people who are unfamiliar with it and I think it benefits them if explanation is included. A personal opinion though :)
(21 Oct '18, 18:32)
2
I edited that part.
(22 Oct '18, 16:50)

Can it be solved using Matrix exponentiation? answered 20 Oct '18, 23:31
I don't think so, because $K$ is around $1000$, and exponentiating $1000$ sized matrices is almost impossible here.
(21 Oct '18, 17:54)
Yes it can be solved using Matrix exponentiation. Links: https://discuss.codechef.com/questions/137810/bbrickseditorial?page=1#137989
(01 Nov '18, 13:47)
Yes it can be solved using Matrix exponentiation. Links: https://discuss.codechef.com/questions/137810/bbrickseditorial?page=1#137989
(01 Nov '18, 13:47)

I also want to know how to do it with Matrix Exponentiation? answered 21 Oct '18, 16:04

Can anyone please explain this part...
answered 21 Oct '18, 16:25

Solved in $O(K)$. The new bricks are arranged in a number of contiguous groups, between $1$ and $K$ such groups. For any one such value $g$ of the number of groups, there will be $\binom{k1}{g1}$ ways of splitting up the new bricks and $\binom{nk+1}{g}$ of inserting those groups into the path. Each group can be laid $2$ ways of course, left or righthand start, so there is also a factor of $2^g$. Then iterate from $g=1$ up to $g=k$ (or $g=nk+1$ if smaller), updating the binomial coefficients stepwise rather than recalculating, using modular inverses up to $1000$ which are precalculated. answered 26 Oct '18, 20:20
