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

×

The old forum can be viewed here. Seek help.

CBARS - Editorial

PROBLEM LINK

Practice
Contest

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 2a 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 2a by 2a 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 2a by 2a to the power (n-1).

SETTERS SOLUTION

Can be found here.

TESTERS SOLUTION

Can be found here.

This question is marked "community wiki".

asked 12 Nov '12, 18:30

gamabunta's gravatar image

gamabunta ♦♦
1.8k123182169
accept rate: 14%

edited 13 Nov '12, 02:26


OMG, that was matrix exponentiation? I couldn't see that :-(

This one made me crazy :-D

alt text

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

link

answered 12 Nov '12, 18:39

betlista's gravatar image

betlista ♦♦
12.4k45102191
accept rate: 9%

edited 12 Nov '12, 18:47

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

1 0

is a valid rectangle.

link

answered 13 Nov '12, 02:19

bobas's gravatar image

bobas
465
accept rate: 0%

edited 13 Nov '12, 02:21

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

(13 Nov '12, 02:25) gamabunta ♦♦

@gamabunta xor with 0s is not good too

1 1
0 0

is valid rectangle

(13 Nov '12, 02:30) betlista ♦♦
1

I had that written in my local copy of the editorial :P

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

I think that is correct.

(13 Nov '12, 02:31) gamabunta ♦♦

it seems ok now ;-)

(13 Nov '12, 02:35) betlista ♦♦

thats cool :D ;)

(01 Dec '12, 00:05) mmanish73

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.

link

answered 13 Nov '12, 19:47

bobas's gravatar image

bobas
465
accept rate: 0%

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)

;-)

link

answered 13 Nov '12, 19:56

betlista's gravatar image

betlista ♦♦
12.4k45102191
accept rate: 9%

edited 13 Nov '12, 19:56

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

link

answered 30 Nov '12, 01:08

ashishnegi001's gravatar image

ashishnegi001
142137
accept rate: 0%

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

(30 Nov '12, 01:16) betlista ♦♦

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 ?

link

answered 01 Dec '12, 08:45

ashishnegi001's gravatar image

ashishnegi001
142137
accept rate: 0%

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?

link

answered 04 Dec '12, 07:24

mayank_natani's gravatar image

mayank_natani
112
accept rate: 0%

toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

Tags:

×812
×72
×16
×10

Asked: 12 Nov '12, 18:30

Seen: 1,751 times

Last updated: 04 Dec '12, 07:24