PROBLEM LINKDIFFICULTYEASY PREREQUISITESMatrix Exponentiation PROBLEMIn 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 EXPLANATIONSince 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. EXPLANATIONLet 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 bitwiseand By) does not contain any consecutive 1s AND (Bx bitwiseor 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 (n1). SETTERS SOLUTIONCan be found here. TESTERS SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Nov '12, 18:30 gamabunta ♦♦ 
OMG, that was matrix exponentiation? I couldn't see that :( This one made me crazy :D I was trying DP, but (2^MAXA)^4 * log(MAXB) was too slow... answered 12 Nov '12, 18:39 betlista ♦♦ 
I do not understand this part : "Y can follow X if and only if (Bx bitwiseand 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. answered 13 Nov '12, 02:19 bobas Thank you for pointing out the error. It has been corrected :)
(13 Nov '12, 02:25)
gamabunta ♦♦
(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. answered 13 Nov '12, 19:47 bobas 
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) ;) answered 13 Nov '12, 19:56 betlista ♦♦ 
What does the (i,j)th i.e. a cell of canFollow Matrix mean? answered 30 Nov '12, 01:08 ashishnegi001 There is 1 if pattern on left side can follow after the pattern on top so in:
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 ? answered 01 Dec '12, 08:45 ashishnegi001 
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 (n1) times will result in matrix having the sum as the answer? answered 04 Dec '12, 07:24 mayank_natani 