So I learnt something new ,hence this blog
the blog is written wrt this question https://mirror.codeforces.com/contest/1980/problem/E
Logic: after taking the input I realised there will be atleast a 1 present in both matrices so If i sorted both matrices wrt the position of 1 in them then they will end up in the same position, and if they do then a can be always converted to b
In short (position of 1 in) [4X4]
matrix a matrix b
@ @
* * 1 * @
@ * 1 * *
@ @
Step 1 :
sort col wrt row (compare 1 with @'s and swap rows accordingly)
matrix a matrix b
* * 1 * * 1 * *
@ @
@ @
@ @
Step 2 :
sort row wrt col (compare 1 with *'s and swap cols accordingly)
matrix a matrix b
1 * * * 1 * * *
@ @
@ @
@ @
now they will end up same (if could be transformed into one another by any number of ops)
ok now the hard thing was how to implement step 1 so i first found the column index of 1 in both matrixes stored them and passed this column index to my custom comparator class then I swapped the vectors wrt this column values
here is the code
class cmpr {
int param;
public:
cmpr(int p) : param(p) {}
bool operator()(vi x,vi y) {
// logic uses param
return x[param]>y[param];
}
};
void nikhil(int testcase){
int n,m,j_ind;
cin>>n>>m;
vector<vector<int>> a(n,vector<int>(m)),b(n,vector<int>(m));
bool flag=true;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>a[i][j];
if(a[i][j]==1)
{
j_ind=j;
}
}
}
sort(a.begin(),a.end(),cmpr(j_ind));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>b[i][j];
if(b[i][j]==1)
{
j_ind=j;
}
}
}
sort(b.begin(),b.end(),cmpr(j_ind));
Never thought I would be needing to pass argument to comparator function
Auto comment: topic has been updated by code.with.nick (previous revision, new revision, compare).
Nice solution brother
thanks brother