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.
I didn’t understood the last two for loops for prefix sums. Why r we doing this way. Why can’t we do this way?
And what the need of this pre[x2+1][y2+1]++?
1 Like
@saurabhshadow @sarthak_eddy @cherry0697
I took range sum and checked the parity finally.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,q;
cin>>n>>m;
int ar[n][m],ar2[n][m];
vector v;
string x;
for(int i=0;i<n;i++)
{
cin>>x;
v.push_back(x);
for(int j=0;j<m;j++)
ar[i][j]=v[i][j]-‘0’;
}
memset(ar2,0,sizeof(ar2));
cin>>q;
while(q–)
{
int a,b,c,d;
cin>>a>>b>>c>>d;
a–,b–,c–,d–;
for(int i=a;i<=c;i++)
ar2[i][b]+=1;
for(int i=a;i<=c;i++)
if(d+1<m)
ar2[i][d+1]-=1;
else if(i+1<n)
ar2[i+1][0]-=1;
}
long c=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
c+=ar2[i][j];
ar2[i][j]=c;
if(ar2[i][j]%2==0)
cout<<ar[i][j];
else
cout<<(!ar[i][j]);
}
cout<<“\n”;
}
return 0;
}
Here is the link for the same solution Link
Its giving TLE
I am assuming the time complexity of this solution to be O((n+m)*q) , Please correct me if i am wrong ? Generally does this complexity pass?
It will not pass , complexity should be O(N*M + Q)
My solution : “CodeChef: Practical coding for everyone”
1 Like
Can u explain something to me?