I think the time constraint was too much , my O(N * M+Q * min(N,M)) even got passed in 1.2 seconds almost. BTW Thanks for a very well written tutorial
3 Likes
A relatively neat/readable solution for anyone interested.
AC_CODE
#include<bits/stdc++.h>
using namespace std ;
void solve(){
int n,m ;cin >> n >> m ;set<int>s ;
vector<vector<int>>a(n,vector<int>(m)) ;
vector<unordered_map<int,int>>mp(n+m) ;
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin >> a[i][j],mp[n-i+j][a[i][j]]++ ;
for(int i=0;i<n+m;i++)
if(mp[i].size()>1)
s.insert(i) ;
int q ;cin >> q ;
while(q--){
int x,y,v ;
cin >> x >> y >> v ;
--x;--y ;
mp[n-x+y][a[x][y]]-- ;
if(mp[n-x+y][a[x][y]]==0)
mp[n-x+y].erase(a[x][y]) ;
mp[n-x+y][v]++ ;
if(mp[n-x+y].size()==1)
s.erase(n-x+y) ;
if(mp[n-x+y].size()>1)
s.insert(n-x+y) ;
a[x][y]=v ;
cout << (s.size()?"No":"Yes") << '\n' ;
}
}
signed main(){
int T;
cin >> T ;
while(T--)
solve() ;
}
8 Likes
@taran_1407 @zappelectro can u provide the implementation for this approach?
How do we map every element of the matrix to the corresponding set and position ?
Can someone explain , how in the given example test case(provided in the question) 2nd query is NO but 3rd is YES.
2 Likes
See editorialist solution, it uses the constant memory approach.
1 Like
thnx 
actually i tried to solve it using segment tree , lol now i found that its a simple one.
2 Likes
Setter’s solution is the most elegant solution. It completely symbolizes that we should not grab a fking chainsaw, if the same work could be done by butter cutting knife…
8 Likes
HI,
I Am not getting why I am getting SIGSEGV error with my code to please if possible provide any test case ( ANY SUBTASK),
https://www.codechef.com/viewsolution/40864098
Thanks , 
THANKS, I got where it is getting wrong I AM attaching the correct solution for it by removing the error.
https://www.codechef.com/viewsolution/40879407
in line 122 of CodeChef: Practical coding for everyone change a[m-1+x-y] to a[x-y] .
Why does this code give TLE on test 3?
submission - CodeChef: Practical coding for everyone
LOGIC - Keeping a set for the diagonals and a set for the bad diagonals, if at any query point bad size is 0, answer is yes else no.
Shouldn’t this code pass the time constraints as the main overhead is building my diagonal in the query which would be done in -
O(min(n,m)*log(min(n,m))*Q)
The find operation and insert in the bad set would again take O(log(min(n,m))*Q
Shouldn’t this pass?
What i am getting with ur code if all queries have x=500 & y=500 ur solution will be qnn that is sufficient for 2 second but maybe system not taking it , but for sure question not wanted to go with n*n in each query.
why my code fails for All test case?. Please help me!!. 
https://www.codechef.com/viewsolution/40920729
But I am not right, it is n.log(n) in each query.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m,i,j;
cin>>n>>m;
int a[n+1][m+1];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
int q,x,y,v,flag,d;
cin>>q;
while(q–)
{
cin>>x>>y>>v;
a[x][y]=v;
j=1;
d=j;
while(j<m && d<m)
{
j=d;i=1;
flag=0;
while(i<=n && j<=m && i+1<=n && j+1<=m)
{
if(a[i][j]!=a[i+1][j+1])
{
//cout<<a[i][j]<<" "<<a[i+1][j+1]<<endl;
flag=1;
break;
}
i++,j++;
}
if(flag==1)
{
break;
}
d=d+1;
}
if(flag==1)
{
cout<<“No”<<endl;
}
else
{
cout<<“Yes”<<endl;
}
a[x][y]=v;
}
}
return 0;
}
guys can any one tell me what is wrong in this for clearing subtask of horascope matrix.
Yes, Anyone can explain this. 1st, 2nd example are fine, but unable to understand the 3rd example.
1 Like
the value of matrix gets updated after every query, in the second test case the value of A(1,1) got updated to 5 ,thus the third test case was correct where A(2,2) was 5 ,since A(1)(1) was already 5