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
↵
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
