Sorry it’s a typo. It is (2,2).
3 Likes
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
can someone tell me what is wrong with my code(it is giving a tle)
https://www.codechef.com/viewsolution/36985305
1 Like
Can anyone help me in this solution it is saying TLE.
Thanks vry vry much @sarthak for providing the Python Code.
And also this problem is really good.
Would you give me a reason as to why we need to do mat[x2+1][y2+1]+=1? I figured out that we have to do it but do not realize the need
1 Like
Can you please tell me what’s wrong with my code?
https://www.codechef.com/viewsolution/37012895
Thank you!
Suppose the input matrix is
00
00
And the query is 1 1 1 1
So your difference array will look like
1 -1
-1 1
After performing all the queries you need to add the do add matrix row-vise and column-vise, the difference array would look like:
1 0
0 0
And this clearly shows that we have need to flip only 1st cell.
But let us suppose that we didn’t perform [x2+1][y2+1+=1, then the difference array will look like:
1 -1
-1 0
Now perform the addition, it will be:
1 0
0 -1
I hope you got it!
@arijitsamal_1 For processing your code takes O(N * M) time per query while the expected time for each query should be O(1). See Editorial for it
The selected four points tend to make a boundary.
check this 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
const long long int m=pow(10,9)+7;int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll n,m ;
cin>>n>>m;
string s[n];
for(int i=0 ;i<n ;i++)
cin>>s[i];
int dp[n+1][m+1]={0};
int t;
cin>>t;
while(t–)
{
int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
x1–; x2–; y1–; y2–;
dp[x1][y1] += 1;
dp[x1][y2+1] -= 1;
dp[x2+1][y1] -= 1;
dp[x2+1][y2+1] += 1;
}
int f=0 ;
for(int i=0 ; i<=n ;i++)
{
for(int j=0 ; j<=m ;j++)
{
f += dp[i][j];
if(i<n){
dp[i+1][j] += dp[i][j];
if(j<m)
{
int x = s[i][j]-‘0’;
if(f%2==0)
cout<<x;
else
cout<<(x+1)%2;
}
}
}
if(i<n)
cout<<"\n";
}
return 0;
}
It is not DP 
possed the solution in a hurry 
if(x2+1<n && y2+1<m)
pre[x2+1][y2+1]++
can anyone please explain this logic to me?
Did it pass? I thought even 2D BIT won’t pass.