PROBLEM LINK:
Author: Hasan Jaddouh
Tester: Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Bitwise Operations
PROBLEM:
Given a matrix Mat[i][j] of 0s and 1s with dimensions N\times 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[i][j] is the sum of all the elements Mat[i][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[i][j] = cumSum[i][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[i][j] = input[i-1][j-1] - '0';
cumXor[i][j] ^= cumXor[i-1][j];
cumXor[i][j] ^= cumXor[i][j-1];
cumXor[i][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})
