BBRICKS - Editorial

editorial
, , ,
1

Problem Link :

Division 1

Division 2

Author : Jannik

Tester : Misha Chorniy

Editorialist : Anand Jaisingh

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

4 Likes
2
3

can someone please give the link for the oeis

4

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 :stuck_out_tongue:

1 Like
5

Here is the link from OEIS. You can find many interesting papers as well.

6 
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

7

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

1 Like
8

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

2 Likes
9

Can it be solved using Matrix exponentiation?

10

I also want to know how to do it with Matrix Exponentiation?

11

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)
12

Here is my solution (


[1]).
Using Matrix exponentiation.


  [1]: https://www.codechef.com/viewsolution/20553858
3 Likes
13

It’s simply prefix sum optimization. I think anyone who reads both recurrences properly, will understand that quite easily.

14

I don’t think so, because K is around 1000, and exponentiating 1000 sized matrices is almost impossible here.

15

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 :slight_smile:

2 Likes
16

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.

17

@vuvth , can you please explain your approach?
How did you use Matrix Exponentiation for recurrence in two variables?

18

[Here][1] 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 :slight_smile: …

Time Complexity = O( T . K^2 )
[1]: http://www.codechef.com/viewsolution/20580951

1 Like
19

this is cool, do you mind explaining your solution ?

1 Like
20

I edited that part.

2 Likes