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

×

Division 1

Division 2

# 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.

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]$, 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$

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

This question is marked "community wiki".

asked 20 Oct '18, 15:21 6★anand20
121312
accept rate: 0% 19.8k350498541

 0 answered 20 Oct '18, 15:53 2.7k●1●6●18 accept rate: 10%
 0 can someone please give the link for the oeis answered 20 Oct '18, 15:56 4★skyhavoc 161●6 accept rate: 0% https://oeis.org/A035597 https://oeis.org/A035598 Basically it is the series Number of points of L1 norm m in cubic lattice Z^n. (21 Oct '18, 20:44)
 1 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 4★tieros 73●4 accept rate: 11%
 0 Here is the link from OEIS. You can find many interesting papers as well. answered 20 Oct '18, 16:30 71●7 accept rate: 0%
 0 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. 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/number-of-ways-to-select-k-non-adjacent-boxes-in-a-2-times-n-board/2945878 answered 20 Oct '18, 16:31 15.5k●1●20●66 accept rate: 18% It's simply prefix sum optimization. I think anyone who reads both recurrences properly, will understand that quite easily. (21 Oct '18, 17:31) anand206★ 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) anand206★
 1 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 k-1 brick in right half) + ...other terms. Recurrent relation will look similar to this. (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) 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 62●3 accept rate: 0%
 2 I solved it by Lagrange Interpolation 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)$ My solution for reference answered 20 Oct '18, 20:14 825●1●13 accept rate: 13%
 0 Can it be solved using Matrix exponentiation? answered 20 Oct '18, 23:31 23●1●1●5 accept rate: 0% I don't think so, because $K$ is around $1000$, and exponentiating $1000$ sized matrices is almost impossible here. (21 Oct '18, 17:54) anand206★ Yes it can be solved using Matrix exponentiation. Links: https://discuss.codechef.com/questions/137810/bbricks-editorial?page=1#137989 https://codeforces.com/blog/entry/62610 (01 Nov '18, 13:47) Yes it can be solved using Matrix exponentiation. Links: https://discuss.codechef.com/questions/137810/bbricks-editorial?page=1#137989 https://codeforces.com/blog/entry/62610 (01 Nov '18, 13:47)
 0 I also want to know how to do it with Matrix Exponentiation? answered 21 Oct '18, 16:04 1 accept rate: 0%
 0 Can anyone please explain this part... 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)  answered 21 Oct '18, 16:25 71●6 accept rate: 0%
 3 Here is my solution (code). Using Matrix exponentiation. answered 21 Oct '18, 16:56 3★vuvth 32●3 accept rate: 0% 1 this is cool, do you mind explaining your solution ? (22 Oct '18, 16:49) anand206★ 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)]  | x 0|  Cost for multiplication two matrix is O(8 * K ^ 2). Sorry for my english. Happy coding <3. (03 Nov '18, 15:26) vuvth3★
 0 @vuvth , can you please explain your approach? How did you use Matrix Exponentiation for recurrence in two variables? answered 22 Oct '18, 16:27 71●7 accept rate: 0%
 1 Here is my short and simple solution. Number of ways = (Number of ways of forming i non-empty groups of k columns) * (Number of ways of placing this i groups around n-k 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( (k-1)C(i-1) * 2^i * (n-k+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 149●5 accept rate: 33%
 0 @vuvth plz share your approach. Do mail me at sumeshkpandit@gmail.com answered 26 Oct '18, 01:49 0 accept rate: 0%
 0 My Python code 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$. 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. answered 26 Oct '18, 20:20 5★joffan 948●8 accept rate: 13%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

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:

×15,852
×2,212
×900
×211

question asked: 20 Oct '18, 15:21

question was seen: 3,698 times

last updated: 13 Mar, 14:40