CENS20A - Editorial

PROBLEM LINK:

Practice
Contest

Author: Aman Dwivedi
Tester: Jatin Nagpal
Editorialist: Sarthak Shukla

DIFFICULTY:

SIMPLE - EASY

PREREQUISITES:

Difference array

PROBLEM:

Given a binary matrix of N rows and M columns. For Q queries, given x_1, y_1, x_2, y_2. Flip all bits lying inside the rectangle formed by (x_1,y_1) as top left corner and (x_2,y_2) as bottom right corner. At last, print the final binary matrix after processing queries.

QUICK EXPLANATION:

  • Create a 2 D sum array initialized to zero.
  • Perform 2 D range update on a given submatrix in each query and calculate difference array after processing queries.
  • If sum at particular index is odd then bit at that index is flipped else it’s the same.

EXPLANATION:

We have to flip all the bits lying inside the rectangle given in each query.
It’s quite obvious that we can’t loop through the given rectangle in each query to flip the bits.
So, instead of flipping the bits in each query, we can keep track of the number of times bit at any index is flipped.

Now, how can we do this?

Answer

We can perform range updates for each query and find the final 2 D matrix after performing updates. We can use another 2 D array preSum of size N*M, initialized to zero, for this operation where each element denotes the number of times bit at that position is flipped.

Now the question is reduced to..

This problem is now reduced to a problem where we are given a grid A of size N*M, and we are asked to increment all the elements lying inside the sub-matrix, formed by (x_1,y_1) as the top left corner and (x_2,y_2) as a bottom right corner, by 1. And, finally, print the final matrix after updates.

The rectangle given in each query is (x_1,y_1), (x_1,y_2), (x_2,y_1) and (x_2,y_2).

Now comes the part to perform updates in each query.
We can use O(1) range update technique of 1 D array as here. Since our rectangle is a group of 1 D arrays, we can perform this operation for every row/column.

But wait, the number of queries is very high, it will result in TLE.

Now, what?
Can we extend this O(1) range update for 1 D array to 2 D array as well? If you don’t know this, think about it before moving onto the implementation.

2 D range update

We can increment preSum[x_1][y_1] and preSum[x_2+1][y_2+1] by 1. And, decrement preSum[x_1][y_2+1] and preSum[x_2+1][y_1] by 1. Make sure to check if these indices are in range or not.

The proof for this update is simple and similar to that of 1 D array. Try figuring it out.

Proof

It is recommended that you first get comfortable working with 1D difference arrays.

Lets try maintaining a 1D difference array for each row. Initially it would look like this.

\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}


Now suppose we update the range (2, 2) to (4, 3). The matrix changes to

\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & -1 \\ 0 & 1 & 0 & -1 \end{bmatrix}


Notice that this is the same as a range update on column. So we take a new matrix and do updates based on column. Which would look like this

\begin{bmatrix} 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}


We would have to perform updates at most 4 different points in this matrix. After performing all the queries, we iterate column wise over this matrix to find all the 1D difference arrays of the rows. And then iterate row wise to find all the actual values of the elements.

Now, the only remaining thing is to find the final matrix. This calculation is also similar to that in 1 D technique. In 1 D technique, we calculate the difference array of the array to get the final array. Here, find the difference array for both rows and columns.

Now, how is the difference array related to our flipping of bits?

Answer

Each element of our difference array denotes the number of times bit is flipped at that position. If the sum at any index is even, then it means a bit at that position is flipped even number of times and will remain the same as previously. But, if sum at any index is odd then the bit at that index is flipped.

TIME COMPLEXITY:

Time: O(N*M + Q)
Space: O(N*M)

SOLUTIONS:

C++ Code
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
 
int main() {
	fast
	ll n,m;
	cin>>n>>m;
	ll a[n][m],i,j,pre[n][m];
	string s[n];
	for(i=0;i<n;i++)
		cin>>s[i];

	for(i=0;i<n;i++) {
		for(j=0;j<m;j++) {
			a[i][j] = s[i][j]-'0';
			pre[i][j]=0;
		}
	}

	ll q;
	cin>>q;
	ll x1,y1,x2,y2;
	while(q--) {
		cin>>x1>>y1>>x2>>y2;
		x1--;
		y1--;
		y2--;
		x2--;
		pre[x1][y1]++;
		if(x2+1<n && y2+1<m)
			pre[x2+1][y2+1]++;
		if(x2+1<n)
			pre[x2+1][y1]--;
		if(y2+1<m)
			pre[x1][y2+1]--;
	}

	for(i=0;i<m;i++) {
		for(j=1;j<n;j++) {
			pre[j][i] += pre[j-1][i];
		}
	}
	
	for(i=0;i<n;i++) {
		for(j=1;j<m;j++) {
			pre[i][j] += pre[i][j-1];
		}
	}
	
	
	for(i=0;i<n;i++) {
		for(j=0;j<m;j++) {
			if(pre[i][j]%2) {
				if(a[i][j] == 1)
					cout<<0;
				else
					cout<<1;
			}
			else
				cout<<a[i][j];
		}
		cout<<"\n";
	}
} 
Python Code
import sys
 
n, m = map(int, sys.stdin.readline().strip().split())
 
arr = []
for i in range(n):
	s = input() + "0"
	temp = []
	for x in s:
		temp += [int(x)]
	arr += [temp]
 
arr += [[0]*(m+1)]
 
add = [[0 for i in range(m+1)] for j in range(n+1)]
pref1 = [[0 for i in range(m+1)] for j in range(n+1)]
pref2 = [[0 for i in range(m+1)] for j in range(n+1)]
 
q = int(sys.stdin.readline().strip())
for _ in range(q):
	x1, y1, x2, y2 = map(int, sys.stdin.readline().strip().split())
	x1 -= 1
	y1 -= 1
	x2 -= 1
	y2 -= 1
	pref2[x1][y1] += 1
	pref2[x2+1][y1] -= 1
	pref2[x1][y2+1] += -1
	pref2[x2+1][y2+1] -= -1
 
for i in range(m):
	for j in range(n):
		if j == 0:
			pref1[j][i] = pref2[j][i]
		else:
			pref1[j][i] = pref1[j-1][i] + pref2[j][i]
 
for i in range(n):
	for j in range(m):
		if j == 0:
			add[i][j] += pref1[i][j]
		else:
			add[i][j] = add[i][j-1] + pref1[i][j]
 
for i in range(n):
	for j in range(m):
		arr[i][j] += add[i][j]
		arr[i][j] %= 2
 
for i in range(n):
	for j in range(m):
		print(arr[i][j], end='')
	print('')
49 Likes

Do change the contest link, its not the correct one I guess. (no probs looks fixed now)

There was such a simple solution and I decided to code up a 2D segment tree…

:man_facepalming:

10 Likes

:flushed:

4 Likes

Kindly anyone provide a counter test-case for my WA Code.
Submission Link

my solution giving TLE why?
https://www.codechef.com/viewsolution/36984523

this is a seriously good editorial. Kudos!

12 Likes

Your code gives wrong output for the input:
3 3
000
000
000
1
1 2 2 2

Your code outputs :
000
110
000
instead of
010
010
000

1 Like

https://www.codechef.com/viewsolution/37003622
I feel my code is much less time consuming than the code provided, please tell me why it is showing TLE

Your code’s time complexity is O(N M Q) which will surely give TLE.

1 Like

nice editorial

1 Like

Nice Editorial @sarthak_eddy

Thanks :slightly_smiling_face:.

1 Like

Can anyone pls tell me why I got TLE? Nice Editorial btw.

https://www.codechef.com/viewsolution/37002169

Heyy bro, in the proof of 2D range update, is it (2,1) or (2,2) ?

Are you for real?
Bruteforcing each query and “feeling much less time consuming”.

5 Likes

Sorry it’s a typo. It is (2,2).

3 Likes

:neutral_face: really disappointed apart from incrementing x2+1,y2+1 index everything was crct…But really a great contest learnt a lot

4 Likes

Editorials are awesome!!

Learnt a lot from this contest. Hoping for more in the future

3 Likes

@sarthak_eddy kudos to him for writing such awesome editorials.

Thanks you enjoyed the contest, hopefully we will come with another contest soon

6 Likes