CENS20A - Editorial

editorial
, ,
45

Can someone please help me why im getting WA. i followed editorial logic for range updates.
https://www.codechef.com/viewsolution/37017027

@saurabhshadow @sarthak_eddy @cherry0697

46

Can u please explain the 2D range update and the example in the editorial a little more . I didnt understand the 2D range update and its proof

47

Can anyone tell mistake in my solution ?
https://www.codechef.com/viewsolution/37017222

48

Given the maximum constraints your code would be running until next week.

50

It dit. See here.

51

Awesome… I had got that performing each query is costy but not knowing somewhat like this Logic for constant time addition exist. Thnx for such Great Editorial…Learnt New Thing :raised_hands:

2 Likes
53

Take pen paper and dry run my code , u will understand :slight_smile:

1 Like
54

I think it makes sense, it shouldn’t matter.

55

wow really good sum thank you for the editoral :slight_smile:

56

Dear Sarthak,

Can you explain me why presum[x2+1][y2+1] is added by 1 and not presum[x2][y2]. Please explain to me.

Thanks in advance!!

57

I don’t understand what is wrong in my debugging. when I dry run the code, I get
01
11
as the answer
This is how I think after reading the editorial
00
00

0-1
-11

0-1
-11

0-1
-11
the sum of previous position in col,row with current pos
0-1
-1-1
where am I wrong?

58

to avoid index out of range error because if x2+1 or y2+1 exceeds the allocated indexes then it would give runtime error.

59

Good contest followed by very good editorials… :smiley:

60

#include
using namespace std;

int main() {
int n=0,m=0,i,j;
cin>>n>>m;
int a[n][m];
string s;
for(i=1;i<=n;i++)
{
cin>>s;
for(j=0;j<m;j++)
{
a[i][j]=s[j];
}
}
long int q=0;
cin>>q;
while(q–)
{
int x1=0,y1=0,x2=0,y2=0;
cin>>x1>>y1>>x2>>y2;
for(i=x1;i<=x2;i++)
{
for(j=y1;j<=y2;j++)
{
if(a[i][j]==0)
a[i][j]=1;
else
a[i][j]=0;
}
}
}
for(i=1;i<=n;i++)
{
for(j=0;j<m;j++)
{
cout<<a[i][j];
}
cout<<"\n";
}
// your code goes here
return 0;
}
what is wrong in this plzz tell??

61

Can anyone provide me any test case for which I am getting WA?

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

62

#define ll long long
#define dd long double
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define si(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(s) scanf("%s",s)
#define pi(x) printf("%d\n",x)
#define pl(x) printf("%lld\n",x)
#define ps(s) printf("%s\n",s)

dd pi = acos(-1) ;
ll z = 1000000007 ;
using namespace std ;
const int N = 2e5 + 7;

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”,“r”,stdin);
freopen(“output.txt”,“w”,stdout);
#endif
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);

int n;
int m;
si(n);
si(m);
int matrix[n+1][m+1];
memset(matrix,0,sizeof(matrix));
for(int i=0;i<n;i++)
{
char a[m];
scanf("%s",a);
for(int j=0;j<m;j++)
matrix[i][j]=a[j]-‘0’;
}

ll q;
cin>>q;
while(q–)
{
int x1;
int y1;
int x2;
int y2;
si(x1);
si(y1);
si(x2);
si(y2);
x1–;
y1–;
x2–;
y2–;
matrix[x1][y1]+=1;
matrix[x1][y2+1]-=1;
matrix[x2+1][y1]-=1;
matrix[x2+1][y2+1]+=1;
}

for(int i=0;i<=m;i++)
for(int j=1;j<=n;j++)
matrix[j][i]+=matrix[j-1][i];

for(int i=0;i<n;i++)
{
for(int j=1;j<=m;j++)
{
matrix[i][j]+=matrix[i][j-1];
printf("%d",matrix[i][j-1]%2);
}
printf("\n");
}

}

why this code giving wrong ans ?? anyone help me…

63

Use pen and paper to visualise the importance of these points.
(x_2, y_2) is not used but (x_2+1, y_2+1) is used because we have to balance (x_1, y_2+1) and (x_2+1, y_1).
Hope it helps.

1 Like
64

That’s what google search told me.

65

I think this concept comes from prefix sum algorithm. You can check it’s implementation to understand!

66

Can Anyone explain the range update in proof part of the editiorial

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, 1) 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.