Answers to: BBRICKS - Editorialhttps://discuss.codechef.com/questions/137810/bbricks-editorial<h1>Problem Link :</h1>
<p><a href="https://www.codechef.com/OCT18A/problems/BBRICKS">Division 1</a></p>
<p><a href="https://www.codechef.com/OCT18B/problems/BBRICKS">Division 2</a></p>
<h1>Author : <a href="https://www.codechef.com/users/neutron_byte">Jannik</a></h1>
<h1>Tester : <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></h1>
<h1>Editorialist : <a href="https://www.codechef.com/users/anand20">Anand Jaisingh</a></h1>
<h1>Pre-Requisites :</h1>
<p>Binomial Coefficients</p>
<h1>Problem :</h1>
<p>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. </p>
<h1>Explanation :</h1>
<p>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.</p>
<p><strong>Sub-task #1 :</strong></p>
<p>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 :</p>
<p>$ 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. </p>
<p>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. </p>
<p>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]$, 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 $. </p>
<p>Time Complexity $ O(maxn \cdot maxk + \sum N_i ) $, where $ maxn=maxk=1000 $</p>
<p><strong>Sub-task #2 :</strong></p>
<p>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$. </p>
<p>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. </p>
<p>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)$, </p>
<p>$ f(1,0)={a,b}=2 $</p>
<p>$ f(i,j)=f(i-1,j)+f(i-1,j-1)$.</p>
<p>We can pre-compute this table in $O(K^2)$ time. Now, for a fixed $N,K$, the answer is : </p>
<p>$ \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.</p>
<p>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 :</p>
<p>$ \binom{k+1+n-k-j-1}{k+1-1} = \binom{n-j}{k}$.</p>
<p>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 $ </p>
<p>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.</p>
<p>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.</p>
<h1>Time Complexity : $ O ( K^2 + T \cdot K^2 ) $</h1>
<p>Also, you can read about multiple different solutions to this problem in the comments section below, check it out. </p>
<h1>My Code : <a href="https://www.ideone.com/pDcORE">Link</a></h1>enFri, 26 Oct 2018 20:20:29 +0530Answer by joffanhttps://discuss.codechef.com/questions/137810/bbricks-editorial/138757<p><a href="https://www.codechef.com/viewsolution/21213603">My Python code</a></p>
<p>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{k-1}{g-1}$ ways of splitting up the new bricks and $\binom{n-k+1}{g}$ of inserting those groups into the path. Each group can be laid $2$ ways of course, left- or right-hand start, so there is also a factor of $2^g$.</p>
<p>Then iterate from $g=1$ up to $g=k$ (or $g=n-k+1$ if smaller), updating the binomial coefficients stepwise rather than recalculating, using modular inverses up to $1000$ which are precalculated.</p>joffanFri, 26 Oct 2018 20:20:29 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/138757Answer by sumesh_pandithttps://discuss.codechef.com/questions/137810/bbricks-editorial/138703<p><a href="/users/284778/vuvth">@vuvth</a> plz share your approach. Do mail me at sumeshkpandit@<a href="http://gmail.com">gmail.com</a></p>sumesh_panditFri, 26 Oct 2018 01:49:31 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/138703Answer by codemaster3840https://discuss.codechef.com/questions/137810/bbricks-editorial/138188<p><a href="http://www.codechef.com/viewsolution/20580951">Here</a> is my short and simple solution.</p>
<p><strong>Number of ways = (Number of ways of forming <em>i</em> non-empty groups of <em>k</em> columns) * (Number of ways of placing this <em>i</em> groups around <em>n-k</em> columns) *for i=1,2,3..k</strong>* </p>
<p>Number of ways of forming <em>i</em> groups of <em>k</em> columns = (Number of ways of distributing <em>k</em> objects into <em>i</em> groups) * (2^i)</p>
<p>where in each group alternate bricks of row <em>1,2</em> are selected and each group can have two orientation (either first brick is from first row or second)</p>
<p>Thus, <strong>Number of ways = sum( (k-1)C(i-1) * 2^i * (n-k+1)C(i) ) for i=1,2,..k</strong></p>
<p>Extended the logic of single row to two rows <em>:)</em> ...</p>
<p>Time Complexity = O( T . K^2 )</p>codemaster3840Mon, 22 Oct 2018 16:30:56 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/138188Answer by ankit_btechhttps://discuss.codechef.com/questions/137810/bbricks-editorial/138187<p><a href="/users/284778/vuvth">@vuvth</a> , can you please explain your approach?
How did you use Matrix Exponentiation for recurrence in two variables?</p>ankit_btechMon, 22 Oct 2018 16:27:48 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/138187Answer by vuvthhttps://discuss.codechef.com/questions/137810/bbricks-editorial/137989<p>Here is my solution (<a href="https://www.codechef.com/viewsolution/20553858">code</a>).
Using Matrix exponentiation.</p>vuvthSun, 21 Oct 2018 16:56:43 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137989Answer by dushyant7917https://discuss.codechef.com/questions/137810/bbricks-editorial/137980<p>Can anyone please explain this part... </p>
<pre><code>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)
</code></pre>dushyant7917Sun, 21 Oct 2018 16:25:23 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137980Answer by siriuslighthttps://discuss.codechef.com/questions/137810/bbricks-editorial/137979<p>I also want to know how to do it with Matrix Exponentiation?</p>siriuslightSun, 21 Oct 2018 16:04:48 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137979Answer by rahul1995https://discuss.codechef.com/questions/137810/bbricks-editorial/137885<p>Can it be solved using Matrix exponentiation?</p>rahul1995Sat, 20 Oct 2018 23:31:46 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137885Answer by pshishod2645https://discuss.codechef.com/questions/137810/bbricks-editorial/137849<p>I solved it by <code>Lagrange Interpolation</code></p>
<p>Let f(n, k) denote the answer then we have the recurrence</p>
<p>$$f(n, k) - f(n - 1, k) = f(n -1, k - 1) + f(n -1, k - 2) $$</p>
<p>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..</p>
<p>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.</p>
<p>So overall time complexity $O(K^2 + TN)$</p>
<p><a href="https://www.codechef.com/viewsolution/20560530">My solution for reference</a></p>pshishod2645Sat, 20 Oct 2018 20:14:50 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137849Answer by chef_keshavhttps://discuss.codechef.com/questions/137810/bbricks-editorial/137846<p>This can also be solved fully using divide and conquer with Dynamic programming.</p>
<p>Direction of this approach:-</p>
<p>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 k-1 brick in right half) + ...other terms.</p>
<p>Recurrent relation will look similar to this.</p>
<p><em>(n, k) = (n/2, 0)(n-n/2, k-0) + (n/2, 1)(n-n/2, k-1) + ..... + (n/2, k-1)(n/2, 1) + (n/2, k)(n/2, 0)</em></p>
<p>NOTE: This is not correct relation. Try to think in this direction.</p>
<p>Time complexity of this solution is O(k^2 * log(n)).</p>chef_keshavSat, 20 Oct 2018 19:43:47 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137846Answer by vijju123https://discuss.codechef.com/questions/137810/bbricks-editorial/137824<p><code>But this dp is still O(N2⋅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 this dp for all 1≤n,k≤1000, and we can for fixed N,K sum up all values dp[i][K],K i≤N.</code></p>
<p>Why? How? Where did this derivation come from?</p>
<p>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.</p>
<p>BTW - Anguepa's answer here is a very neat explanation of how to derive the recurrence - <a href="https://math.stackexchange.com/questions/2945440/number-of-ways-to-select-k-non-adjacent-boxes-in-a-2-times-n-board/2945878">https://math.stackexchange.com/questions/2945440/number-of-ways-to-select-k-non-adjacent-boxes-in-a-2-times-n-board/2945878</a></p>vijju123Sat, 20 Oct 2018 16:31:42 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137824Answer by ankit_btechhttps://discuss.codechef.com/questions/137810/bbricks-editorial/137822<p><a href="http://oeis.org/A035607">Here</a> is the link from OEIS. You can find many interesting papers as well.</p>ankit_btechSat, 20 Oct 2018 16:30:56 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137822Answer by tieroshttps://discuss.codechef.com/questions/137810/bbricks-editorial/137820<p>Here is a nice paper: <a href="https://arxiv.org/pdf/1409.3869.pdf">Selections Without Adjacency on a Rectangular Grid</a>
I tried everything written here before I noticed what was wrong in my solution, a little bug in binomial mod function :P</p>tierosSat, 20 Oct 2018 16:20:58 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137820Answer by skyhavochttps://discuss.codechef.com/questions/137810/bbricks-editorial/137815<p>can someone please give the link for the oeis </p>skyhavocSat, 20 Oct 2018 15:56:34 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137815Answer by aryanc403https://discuss.codechef.com/questions/137810/bbricks-editorial/137814<p><a href="https://www.spoj.com/problems/LVADER/">https://www.spoj.com/problems/LVADER/</a></p>aryanc403Sat, 20 Oct 2018 15:53:17 +0530https://discuss.codechef.com/questions/137810/bbricks-editorial/137814