CAKECUT - Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Bitwise Operations

PROBLEM:

Given a matrix Mat*[j] of 0s and 1s with dimensions N imes M, we have to report the number of submatrices that contain an even number of 1s.

EXPLANATION:

Let us first think about the naïvest algorithm which can report the number of submatrices with even number of 1s. We can transform the given matrix into a matrix of cumulative sum. Let’s call this new matrix cumSum. So, cumSum*[j] is the sum of all the elements Mat*[j] such that i < x and j < y. Once we have completely populated the cumSum matrix, we can calculated the number of 1s in any submaxtrix by using inclusion exclusion principle. In terms of math, we have that the number of 1s in the submatrix given by the diagonally opposite points (x_1, y_1) and (x_2, y_2) can be calculated as:

cumSum[x_2][y_2] - cumSum[x_1-1][y_2] - cumSum[x_2][y_1-1] + cumSum[x_1-1][y_1-1]

This way of calculating the number of 1s per submatrix and then counting the even results takes \mathcal{O}(N^2\cdot M^2). To optimise this, we need to make some observations. Note that, right now, we are calculating the number of 1s explicitly per submatrix. But we only need to know whether a submatrix has even or odd number of ones. So we transform each entry of our cumSum matrix to:

cumSum*[j] = cumSum*[j] mod 2

Before we move into further explanation, let us look at how xor works with the notion of “cumulative”. We noted that when we were summing, we could use the above formula to get the sum of any submatrix. We can use a similar notion for xor as well. This means that the xor of all the numbers in the submatrix given by (x_1, y_1) and (x_2, y_2):

cumSum[x_2][y_2] ^ cumSum[x_1-1][y_2] ^ cumSum[x_2][y_1-1] ^ cumSum[x_1-1][y_1-1]

where ^ stands for bitwise xor operation. Another property about xors is that xor of even number of 1s is 0 and odd number of 1s is 1.

So, once we have the cumSum array after doing the mod 2 operation on each element, and the aforementioned observations, we have all the relevant details to form a formal algorithm.

Here is a pseudocode for the procedure up till now:

for i = 1 to N
{
	for j = 1 to M
	{
		cumXor*[j] = input[i-1][j-1] - '0';
		
		cumXor*[j] ^= cumXor[i-1][j];
		cumXor*[j] ^= cumXor*[j-1];
		cumXor*[j] ^= cumXor[i-1][j-1];
	}
}

We can treat each row of our cumSum array as a number formed of M bits. So we can xor together the rows of the cumSum array element-wise. Let us say by xoring the i^{th} and the j^{th} row, we get the bits[] as the resultant array. We know that 1s in the bits array indicate odd number of 1s and 0s indicate even number of 1s within submatrices that have endpoints in these rows. We also know that both odd subtracted from odd and even subtracted from even give even. Thus, we count the total number of possible submatrices which have even number of 1s and have endpoints in these 2 rows by taking:

count1s = c1*(c1-1)/2  
count0s = c0*(c0-1)/2  

where c1 = number of 1s in bits[] array and c0 = number of 0s in bits[] array. We do this for every pair of rows and add the count1s and count0s variables to our final answer counter.

This gives us a \mathcal{O}(N^2M) algorithm. We can optimise the xoring of two rows by treating grouping bits to form 32 bits integers. This is already done in libraries like the Bitset library of C. By grouping, we can get the complexity down to \mathcal{O}(\frac{N^2M}{32}).

Please see editorialist’s/setter’s program for implementation details.

COMPLEXITY:

\mathcal{O}(\frac{N^2M}{32})

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

3 Likes

This isn’t easy-medium…

1 Like

I could guess the O(N2M2) thing. The subsequent improvement was god-like. Thanks

Can anyone explain why count1s+count0s for every pair of rows is the answer?
It seems like we are adding the number of ways of selecting 2 1’s or 2 0’s.But how does it give the number of sub matrices with even sum?
I would be thankful if someone could provide a little example.

What do we get from xor-ing 2 rows?

1 Like

Can anyone explain in more detail how was the answer obtained by xoring the rows of matrix ?

LAst part went over my head anyone please help I am stuck on this for straight three hours now

1 Like

Finally got the last part .

First understand how it works on normal sum matrix.

Suppose matrix be : 1 1 1 (a00 , a01 , a02) .

Then sum matrix will be : 1 2 3

To calculate number of sub matrices we will go from index 0 to index 2 . Let count = 0

i = 0 , sumMat[0] = 1 , it is not even number hence do not count it.

i = 1 , sumMat[1] = 2 , it is even hence increment count . (count = 1) (Now understand what this sumMat[1] actually is ? It is sum of original mat[0] and mat[1] . So sum of submatrix [1 1] is even. )

for i = 1 start from looking 0th index (to count all sub matrix till now .)

j = 0 , i = 1 subtract sumMat[0] from sumMat[1] , it will give us original matrix mat[1] . It is odd hence don’t increase count.

similarly for i = 2 , subtracting sumMat[0] will give us original sub matrix [1 1] (i.e. a01 , a02) .

So we are knew now that subtracting odd from odd gives us Even matrix and increase count . And subtracting even from even obviously gives even .

NOW ACTUAL FUN IS WITH XOR-MATRIX .

Our xor-matrix will be [1 0 1] for sum Matrix [1 2 3] , and corresponding xor-sum-matrix will be [ 1 1 0 ]

0 indicates even sum and 1 indicated odd sum .

We know that all 0s individually will increment counter , and all pairs of 1s will increment counter .

So to get all 0s including pair of zeros , use nCr where n = zero + 1 , r = 2

For getting all pair of once use nCr , with n = one , r = 2

For getting more clear how it works dry run this algorithm for different matrix [0 1 1 1] , then sumMat[0 1 2 3] and xor-mat [0 1 0 1] . count = (z+1)(z)/2 + (one)(one-1)/2 = 3 + 1 = 4 .

your calculation of xor is wrong. @radeonguy. it should be
110

011

radeonguy

(sum[r] - sum[l - 1) % 2 = 0 , sum[l - 1] % 2 = sum[r] % 2 . so we want number of pairs with equal prefix sum % 2.

3 Likes

ok, I get it now.Thanks for the help!

1 Like

what is r and l in @rajat1603 's answer ?
Still trying to figure out that part of algorithm.

This looks good but can you do the above operations on a 2x3 matrix ?
thanks !
:smiley:
e.g.

matrix =

101

111

xor matrix will be :



110

010

now what next ? Please correct me if I am wrong in any part.