COW3E-Editorial

PROBLEM LINK: https://www.codechef.com/COW42020/problems/COW3E

Practice

Contest

Author: Kushagra Kinger

Tester: Kushagra Kinger

Editorialist: Kushagra Kinger

DIFFICULTY:

MEDIUM

PREREQUISITES:

Difference Array , Prefix Sum Array.

PROBLEM:

Given a 2d matrix of size nxm , perform range updates and range sum queries where two cells (r1,c1) and (r2,c2) define a range which contains all cells [i,j] such that r1<=i<=r2 and c1<=j<=c2.

QUICK EXPLANATION:

We will use the concept of one dimensional difference array extended to 2d arrays for range updates and 2d prefix sums for answering queries.

EXPLANATION:

Since queries are asked after all the modifications, thus we perform all the modifications first and then answer the queries. Assume that we have performed all the modifications. Now we have to answer range queries in the 2d-matrix which can be done by making a 2d prefix array of the given matrix.I am not explaining the construction of 2d prefix array and then how it’s used to answer range sum queries here as this concept is available on many places on the internet.

Now , we need to worry about how to perform the modifications efficiently, after that 2d prefix array will answer the queries.

For performing range updates , we will use the concept of 2d differene array.

In 1-d difference array, first we proccess the array as follows:

dif[] is the difference array of a[].

Initially dif is similar to a i.e. dif[i]=a[i] (0<=i<size of array).

Then:

for i= 1 to n-1 //zero indexing

dif[i]=dif[i]-a[i-1];

Now if we have to perform modifications of the form k,l,r which means add k in all elements from l to r then we simply add k to dif[l] and -k to dif[r+1](if l and r are valid i.e. 0<=l<n and 0<=r+1<n). If we are asked to perform m such modifications, we keep on doing this operation on the difference array. Finally when all the modifications are performed we make a prefix sum array of this array and the array obtained is the array which we would have got after performing all modifications on the original array.

In this question we will extend this concept to 2d arrays.

Refer the code for step by step process. Basic concept is that, as in 1d array we add k to the starting index and subtract from the index which touches the boundary of the block to be updated. In 2d array , we have to consider 4 indices.If we have to update from (r1,c1) to (r2,c2) then (r1,c1) is the starting index and (r1,c2+1),(r2+1,c1) and (r1+1,c1+1) are the boundary touching indices.

2d Segment trees is an alternative for solving such a problem but it would be overkill to use it here and the construction time of O(nmlog(n)log(m)) may not pass the time limits of this problem. Thus the concept of 2d difference array must be used to perform modifications in O(1) and then 2d prefix array to perform queries in O(1) time, which yields the total time complexity of O(u+q+n*m).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

ll a[1001][1001];
ll b[1001][1001];

int main()
{io
ll ans,k;
int n,m,r1,c1,r2,c2,u,q;
cin>>n>>m>>u>>q;


//b will be used as 2d-difference array
for(int i=0;i<n;i++)
{
	for(int j=0;j<m;j++)
	{
    	cin>>a[i][j];
    	b[i][j]=a[i][j];
    }
}


// Making of difference array
for(int i=1;i<n;i++)
b[i][0]-=a[i-1][0];

for(int i=1;i<m;i++)
b[0][i]-=a[0][i-1];

for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
b[i][j]=b[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
}


// Making modifications
while(u--)
{cin>>k>>r1>>c1>>r2>>c2;
// Three boundary touching indices must be checked for validity before 
updation
    if(c2+1<m)
    b[r1][c2+1]-=k;

    if(r2+1<n)
    b[r2+1][c1]-=k;

    if(r2+1<n&&c2+1<m)
    b[r2+1][c2+1]+=k;

    b[r1][c1]+=k;
}


//Obtaining Modified Array by performing 2d-prefix array computation on the 
2d-difference array
for(int i=1;i<n;i++)
b[i][0]+=b[i-1][0];

for(int i=1;i<m;i++)
b[0][i]+=b[0][i-1];

for(int i=1;i<n;i++)
{
	for(int j=1;j<m;j++)
	b[i][j]=b[i][j]+b[i-1][j]+b[i][j-1]-b[i-1][j-1];	
}


//Making 2d prefix array for answering queries
for(int i=1;i<m;i++)
b[0][i]+=b[0][i-1];

for(int i=1;i<n;i++)
b[i][0]+=b[i-1][0];

for(int i=1;i<n;i++)
{
	for(int j=1;j<m;j++)
	b[i][j]+=(b[i-1][j]+b[i][j-1]-b[i-1][j-1]);
}

//Answering Queries
while(q--)
{	int r1,c1,r2,c2;
	cin>>r1>>c1>>r2>>c2;
     ans=b[r2][c2];
    if(r1-1>=0)
	ans-=b[r1-1][c2];

    if(c1-1>=0)
    ans-=b[r2][c1-1];

	if(r1-1>=0&&c1-1>=0)
	ans+=b[r1-1][c1-1];

	cout<<ans<<"\n";
}
 return 0;}
3 Likes
(r1,c2+1),(r2+1,c1) and (r1+1,c1+1) are the boundary touching indices.

Here shouldn’t it be (r2 + 1, c2 + 1) rather than (r1 + 1, c1 + 1).
I think it’s a typing mistake.

4 Likes

Oh yes it’s a typing mistake, it’s (r2+1,c2+1) there instead of (r1+1,c1+1).
Thanks for pointing this out

3 Likes

can anyone tell me in the setter’s code why we are making prefix sum two time’s
one for this->Obtaining Modified Array by performing 2d-prefix array computation on the 2d-difference array
and another for this->Making 2d prefix array for answering queries

I am getting a WA on my code. Can someone please help me in finding where I am wrong?

Code:

#include <bits/stdc++.h>
  using namespace std;

int main() {
	int n,m,u,q;
	cin>>n>>m>>u>>q;
	int grid[n][m], grid2[n][m];
	for(int i=0;i<n;i++){
	    for(int j=0;j<m;j++){
	        cin >> grid[i][j];
	        grid2[i][j]=grid[i][j];
	    }
	}
	
	//Making difference array
	for(int i=1;i<n;i++){
	    grid2[i][0]-=grid[i-1][0];
    }
    
    for(int i=1;i<m;i++){
        grid2[0][i]-=grid[0][i-1];
    }
    
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<m;j++){
            grid2[i][j]=grid2[i][j]-grid[i-1][j]-grid[i][j-1]+grid[i-1][j-1];
        }
    }
	
	while(u--){
	    int k,r1,c1,r2,c2;
	    cin>>k>>r1>>c1>>r2>>c2;
	    grid2[r1][c1]+=k;
	    if(r2+1 < n && c2+1 < m){
	        grid2[r2+1][c2+1]+=k;
	    }
	    if(r2+1 < n){
	        grid2[r2+1][c1]-=k;
	    }
	    if(c2+1 < m){
	        grid2[r1][c2+1]-=k;
	    }
	}
	
	
	for(int i=1;i<n;i++){
	    grid2[i][0] += grid2[i-1][0];
	}
	for(int i=1;i<m;i++){
	    grid2[0][i] += grid2[0][i-1];
	}
	for(int i=1;i<n;i++){
	    for(int j=1;j<m;j++){
	        grid2[i][j] = grid2[i][j] + grid2[i-1][j] + grid2[i][j-1] - grid2[i-1][j-1];
	    }
	}
	
	
	for(int i=1;i<n;i++){
	    grid2[i][0] += grid2[i-1][0];
	}
	for(int i=1;i<m;i++){
	    grid2[0][i] += grid2[0][i-1];
	}
	for(int i=1;i<n;i++){
	    for(int j=1;j<m;j++){
	        grid2[i][j] = grid2[i][j] + grid2[i-1][j] + grid2[i][j-1] - grid2[i-1][j-1];
	    }
	}
	while(q--){
	    int r1,c1,r2,c2;
	    int ans;
    	cin>>r1>>c1>>r2>>c2;
        ans=grid2[r2][c2];
        if(r1-1>=0)
    	ans-=grid2[r1-1][c2];
        if(c1-1>=0)
        ans-=grid2[r2][c1-1];
    	if(r1-1>=0&&c1-1>=0)
    	ans+=grid2[r1-1][c1-1];
    
    	cout<<ans<<"\n";
	}
	return 0;
}

@kkdrummer @

why you are adding k in r2+1,c2+1.

r2+1,c2+1 is starting index or boundary touching index.

We can also do this problem without taking the difference array, but we will use the 2nd array (array b of same size).
Step 1- Initialize array b={0} (2d).

Step 2- Perform the modification on by ADDING ‘k’ to (r1,c1) and (r2+1,c2+1) checking if (r2+1,c2+1) is within limits and by SUBSTRACTING ‘k’ from (r1,c2+1) and (r2+1,c1)

Step 3- Frist summing up top-down then left-right on array b

Step 4- ADD array a to array b as a[i][j]+=b[i][j];

Step 5- Summing up Frist top-down then left-right on modified array a

Step 6- ans=a[r2][c2] - (a[r1-1][c2] + a[r2][c1-1] - a[r1-1][c1-1]) // Check for boundary conditions here too.

4 Likes

@aditya_das Thank you so much!! :raised_hands::raised_hands:

can anyone just help me out in figuring how the heck do we obtain that modified array in the sample testcase ??
also shoudln’t the answer for second query be sum of all cells from (1,1) to (2,2) which is (2 + (-1)+ 3 + (-3) + 1) which is 2 rather than 1 !!!

can anyone just help me out in figuring how the heck do we obtain that modified array in the sample testcase ??
also shoudln’t the answer for second query be sum of all cells from (1,1) to (2,2) which is (2 + (-1)+ 3 + (-3) + 1) which is 2 rather than 1 !!!

I am also not getting it. If you figured it out can you share it?

I am getting WA on submission , though the sample test cases passes in test run, can someone help me find the error?

Code :

#include<iostream>
#include <bits/stdc++.h>
#include<cmath>
using namespace std;

void printMatrix(vector<vector<long long>> &v){
    for(auto x:v){
        for(auto value:x)
            cout<<value<<" ";
        cout<<endl;
    }
}

int main(){
   long long n,m,u,q;
    cin>>n>>m>>u>>q;  
    vector<vector<long long>> matrix(n,vector<long long>(m));
    vector<vector<long long>> bumpMatrix(n,vector<long long>(m));
    vector<vector<long long>> prefixMatrix(n,vector<long long>(m));

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>matrix[i][j];
        }
    }

    while(u--){
       long long k,r1,c1,r2,c2;
        cin>>k>>r1>>c1>>r2>>c2;
        bumpMatrix[r1][c1]+=k;
        if(c2+1<m)
            bumpMatrix[r1][c2+1]-=k;
        if(r2+1<n)
            bumpMatrix[r2+1][c1]-=k;
        if(r2+1<n && c2+1<m)
            bumpMatrix[r2+1][c2+1]+=k;
    }
    //=====bumpMatrix Evaluation=====
    //row prefix evaluation
    for(int i=0;i<n;i++){
       long long sum=0;
        for(int j=0;j<m;j++){
            sum=sum+bumpMatrix[i][j];
            bumpMatrix[i][j]=sum;
        }
    }
    //column prefix evaluation
    for(int j=0;j<m;j++){
        long long sum=0;
        for(int i=0;i<n;i++){
            sum=sum+bumpMatrix[i][j];
            bumpMatrix[i][j]=sum;
        }
    }  
    
    //==================================

    //updating bumMatrix to real Value
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            bumpMatrix[i][j]+=matrix[i][j];
    }
   
    //================================

    //calculating 2d prefix sum in prefixmatrix
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            long long a=0,b=0,c=0,d=0;
            if(i-1>=0)
                a=prefixMatrix[i-1][j];
            if(j-1>=0)
                b=prefixMatrix[i][j-1];
            if(i-1>=0 && j-1>=0)
                c=prefixMatrix[i-1][j-1];
             prefixMatrix[i][j]=bumpMatrix[i][j] +  a+ b -  c ;
        }
    }
     //printMatrix(prefixMatrix);    
    //=========================================

    //Taking Queries
    while(q--){
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
       long long ans;
        long long a=0,b=0,c=0;
        if(r1-1>=0)
            a=prefixMatrix[r1-1][c1];
        if(c1-1>=0)
            b=prefixMatrix[r2][c1-1];
        if(r1-1 && c1-1>=0)
            c=prefixMatrix[r1-1][c1-1];
        ans=prefixMatrix[r2][c2] - a - b + c;
        cout<<ans<<"\n";
    }
    //==============

    return 0;
}

Why are we using r2+1 and c2+1 as boundary conditions