CBARS - Editorial

gamabunta · November 12, 2012, 6:30pm

PROBLEM LINK

DIFFICULTY

EASY

PREREQUISITES

Matrix Exponentiation

PROBLEM

In how many ways can a fill a matrix of size a by b, such that, there are no rectanlges of height and width more than 1, that contain only 0s or only 1s.

QUICK EXPLANATION

Since a can only be at most 6, you can consider filling the matrix one column at a time.

A column can be filled in at most 2^a ways. You can build an matrix that represents whether a column of type A can be followed by a column of type B. This matrix must be exponentiated n times to get the final answer.

EXPLANATION

Let us call a rectagle that violates the constraint - that is, it is made up entirely of 0s (or entirely of 1s) and has a width and height, both more than 1 - an invalid rectangle.

It is easy to see that if an invalid rectangle must exist, then there also exists an invalid rectangle of dimensions 2x2.

Corollarly: if we ensure while filling a column that we are not building an invalid rectangle of dimension 2x2, then there can never exist an invalid rectangle in the finished matrix.

We are going to fill the matrix column by column.

Consider the following situation.

....................(x0)(y0)
....................(x1)(y1)
....................(x2)(y2)
....................(x3)(y3)
....................(x4)(y4)
....................(x5)(y5)

Let us assume that the matrix has been filled up to column X such that it contains no invalid rectangles. We add another column, call it column Y. We know that the matrix contains no invalid rectangles of size 2x2 until column X. We must ensure that addition of column Y does not add an invalid rectangle of dimension 2x2.

But since any 2x2 rectangles that addition of column Y can introduce can only at most overlap column X, we can ignore the state of the rest of the matrix!

Now, let Bx = (x5, x4, x3, x2, x1, x0) be the bitset that represents the values in column X. Similarly, let By = (y5, y4, y3 y2, y1, y0) represents the values that we intend to fill in column Y.

Y can follow X if and only if (Bx bitwise-and By) does not contain any consecutive 1s AND (Bx bitwise-or By) does not contain any consecutive 0s.

We can no build a matrix canFollow of dimension 2^a by 2^a which represents whether some configuration of a column can be followed by another configuration in the next column.

Exponentiation of canFollow leads us to enumerating the number of ways of filling the columns such that the matrix does not contain any invalid rectangles. As an example, the 4x4 matrix for a = 2 is

     00 01 10 11
00 |  0  1  1  1 |
01 |  1  1  1  1 |
10 |  1  1  1  1 |
11 |  1  1  1  0 |

Adding all the values in the above matrix gives us the answer for a = 2, b = 2.

To get the answer for a = 2, b = 3 - we multiply it with itself once.

| 3 3 3 2 |
| 3 4 4 3 |
| 3 4 4 3 |
| 2 3 3 3 |

The answer would thus be 50.

The answer for and a and n can similarly be found by raising the matrix of dimension 2^a by 2^a to the power (n-1).

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

betlista · November 12, 2012, 6:39pm

OMG, that was matrix exponentiation? I couldn’t see that

This one made me crazy

alt text

I was trying DP, but (2^MAXA)^4 * log(MAXB) was too slow…

bobas · November 13, 2012, 2:19am

I do not understand this part :

“Y can follow X if and only if (Bx bitwise-and By) does not contain any consecutive digits that are the same.”

So if X = (1,1), Y = (0,0) then X & Y = (0,0), which means Y can’t follow X, even though

1 0

is a valid rectangle.

gamabunta · November 13, 2012, 2:25am

Thank you for pointing out the error. It has been corrected

betlista · November 13, 2012, 2:30am

@gamabunta xor with 0s is not good too

1 1
0 0

is valid rectangle

gamabunta · November 13, 2012, 2:31am

I had that written in my local copy of the editorial

I have changed it to “and with 1s” AND “or with 0s”.

I think that is correct.

betlista · November 13, 2012, 2:35am

it seems ok now

bobas · November 13, 2012, 7:47pm

It’s a great problem, I feel I learned quite a lot by solving it, using the editorial. I recommend others to solve it also, especially those that do not have any experience with matrix exponentiation.

As I understand it, the reason matrix exponentiation worked here is because the solution for a larger state is a linear combination of solutions for smaller states.

betlista · November 13, 2012, 7:56pm

Because we have n=2^a matrices here, someone can use Strassen algorithm to reduce time from O(n^3) to O(n^2.8)

ashishnegi001 · November 30, 2012, 1:08am

What does the (i,j)th i.e. a cell of canFollow Matrix mean?

betlista · November 30, 2012, 1:16am

There is 1 if pattern on left side can follow after the pattern on top so in:

     00 01 10 11
00 |  0  1  1  1 |
01 |  1  1  1  1 |
10 |  1  1  1  1 |
11 |  1  1  1  0 |

there cannot be 00 after 00 (otherwise it creates bar with 2x2 subrectangle with only zeros), similarly for 11 and 11

mmanish73 · December 1, 2012, 12:05am

thats cool

ashishnegi001 · December 1, 2012, 8:45am

Can somebody explain or give a link to the theory that supports that Matrix Exponentiation of canFollow gives us the matrix whoes sum of elements gives the total number of combinations ?

mayank_natani · December 4, 2012, 7:24am

Although this is a very good editorial, I was wondering if someone can provide a good link to learn the Matrix Exponentiation technique. Please make it more clear why multiplying the matrix with itself (n-1) times will result in matrix having the sum as the answer?