# CENS20A - Editorial

**URL:** <https://discuss.codechef.com/t/cens20a-editorial/75404>\
**Category:** editorial\
**Tags:** editorial, cens2020, saurabhshadow\
**Created:** [August 19, 2020, 6:01pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404 "2020-08-19T18:01:26Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![saurabhshadow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhshadow/32/347886_2.png) [@saurabhshadow](https://discuss.codechef.com/u/saurabhshadow)\
**Post date:** [August 19, 2020, 6:01pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/1 "2020-08-19T18:01:26Z")

</div>

# PROBLEM LINK:

[Practice](https://www.codechef.com/problems/CENS20A)  
[Contest](https://www.codechef.com/CENS2020/problems/CENS20A)

**Author:** [Aman Dwivedi](https://www.codechef.com/users/cherry0697)  
**Tester:** [Jatin Nagpal](https://www.codechef.com/users/nagpaljatin141)  
**Editorialist:** [Sarthak Shukla](https://www.codechef.com/users/sarthak_eddy)

# 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](https://www.geeksforgeeks.org/constant-time-range-add-operation-array/). 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**
>
> ```auto
> #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**
>
> ```auto
> 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('')
> 
> ```

---

<div class="post-metadata">

**Author:** ![akram01](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@akram01](https://discuss.codechef.com/u/akram01)\
**Post date:** [August 19, 2020, 6:09pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/2 "2020-08-19T18:09:41Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![anon86196368](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon86196368](https://discuss.codechef.com/u/anon86196368)\
**Post date:** [August 19, 2020, 6:10pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/3 "2020-08-19T18:10:48Z")

</div>

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

🤦‍♂️

---

<div class="post-metadata">

**Author:** ![ssrivastava990](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ssrivastava990/32/216836_2.png) [@ssrivastava990](https://discuss.codechef.com/u/ssrivastava990)\
**Post date:** [August 19, 2020, 6:13pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/4 "2020-08-19T18:13:59Z")

</div>

> [@anon86196368](#):
>
> 2D segment tree

😳

---

<div class="post-metadata">

**Author:** ![ameybhavsar](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ameybhavsar/32/26566_2.png) [@ameybhavsar](https://discuss.codechef.com/u/ameybhavsar)\
**Post date:** [August 19, 2020, 6:15pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/5 "2020-08-19T18:15:42Z")

</div>

Kindly anyone provide a counter test-case for my WA Code.  
[Submission Link](https://www.codechef.com/viewsolution/37002678)

---

<div class="post-metadata">

**Author:** ![csk03012](https://discuss.codechef.com/user_avatar/discuss.codechef.com/csk03012/32/3653_2.png) [@csk03012](https://discuss.codechef.com/u/csk03012)\
**Post date:** [August 19, 2020, 6:22pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/6 "2020-08-19T18:22:15Z")

</div>

my solution giving TLE why?  
[https://www.codechef.com/viewsolution/36984523](https://www.codechef.com/viewsolution/36984523)

---

<div class="post-metadata">

**Author:** ![codegeass\_314](https://discuss.codechef.com/user_avatar/discuss.codechef.com/codegeass_314/32/33912_2.png) [@codegeass\_314](https://discuss.codechef.com/u/codegeass_314)\
**Post date:** [August 19, 2020, 6:32pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/7 "2020-08-19T18:32:57Z")

</div>

this is a seriously good editorial. Kudos!

---

<div class="post-metadata">

**Author:** ![thatprakhar](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@thatprakhar](https://discuss.codechef.com/u/thatprakhar)\
**Post date:** [August 19, 2020, 6:36pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/8 "2020-08-19T18:36:15Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sar01](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sar01/32/208155_2.png) [@sar01](https://discuss.codechef.com/u/sar01)\
**Post date:** [August 19, 2020, 6:38pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/9 "2020-08-19T18:38:05Z")

</div>

[https://www.codechef.com/viewsolution/37003622](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

---

<div class="post-metadata">

**Author:** ![sarthak\_eddy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sarthak_eddy/32/5094_2.png) [@sarthak\_eddy](https://discuss.codechef.com/u/sarthak_eddy)\
**Post date:** [August 19, 2020, 6:41pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/11 "2020-08-19T18:41:56Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sksama](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@sksama](https://discuss.codechef.com/u/sksama)\
**Post date:** [August 19, 2020, 6:44pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/12 "2020-08-19T18:44:37Z")

</div>

nice editorial

---

<div class="post-metadata">

**Author:** ![nahsor](https://discuss.codechef.com/user_avatar/discuss.codechef.com/nahsor/32/55527_2.png) [@nahsor](https://discuss.codechef.com/u/nahsor)\
**Post date:** [August 19, 2020, 6:47pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/13 "2020-08-19T18:47:41Z")

</div>

Nice Editorial @sarthak_eddy

---

<div class="post-metadata">

**Author:** ![sarthak\_eddy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sarthak_eddy/32/5094_2.png) [@sarthak\_eddy](https://discuss.codechef.com/u/sarthak_eddy)\
**Post date:** [August 19, 2020, 6:50pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/14 "2020-08-19T18:50:42Z")

</div>

Thanks 🙂.

---

<div class="post-metadata">

**Author:** ![fomomomo](https://discuss.codechef.com/user_avatar/discuss.codechef.com/fomomomo/32/130580_2.png) [@fomomomo](https://discuss.codechef.com/u/fomomomo)\
**Post date:** [August 19, 2020, 7:15pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/15 "2020-08-19T19:15:17Z")

</div>

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

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

---

<div class="post-metadata">

**Author:** ![lex\_luthor](https://discuss.codechef.com/user_avatar/discuss.codechef.com/lex_luthor/32/24644_2.png) [@lex\_luthor](https://discuss.codechef.com/u/lex_luthor)\
**Post date:** [August 19, 2020, 7:30pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/16 "2020-08-19T19:30:17Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![predicate007](https://discuss.codechef.com/user_avatar/discuss.codechef.com/predicate007/32/24644_2.png) [@predicate007](https://discuss.codechef.com/u/predicate007)\
**Post date:** [August 19, 2020, 7:33pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/17 "2020-08-19T19:33:14Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sarthak\_eddy](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sarthak_eddy/32/5094_2.png) [@sarthak\_eddy](https://discuss.codechef.com/u/sarthak_eddy)\
**Post date:** [August 19, 2020, 7:34pm UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/18 "2020-08-19T19:34:52Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![ramu\_537](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@ramu\_537](https://discuss.codechef.com/u/ramu_537)\
**Post date:** [August 20, 2020, 3:07am UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/19 "2020-08-20T03:07:40Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![sandipan\_2224](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sandipan_2224/32/67805_2.png) [@sandipan\_2224](https://discuss.codechef.com/u/sandipan_2224)\
**Post date:** [August 20, 2020, 3:26am UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/20 "2020-08-20T03:26:45Z")

</div>

_Editorials are awesome!!_

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

---

<div class="post-metadata">

**Author:** ![cherry0697](https://discuss.codechef.com/user_avatar/discuss.codechef.com/cherry0697/32/348418_2.png) [@cherry0697](https://discuss.codechef.com/u/cherry0697)\
**Post date:** [August 20, 2020, 3:46am UTC](https://discuss.codechef.com/t/cens20a-editorial/75404/21 "2020-08-20T03:46:49Z")

</div>

@sarthak_eddy kudos to him for writing such awesome editorials.

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

[Next page](https://discuss.codechef.com/t/cens20a-editorial/75404.md?page=2)