MATBEAUT - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest Division 3
Contest Division 2
Contest Division 1

Setter: Smarth Mehta
Tester: Aryan Choudhary
Editorialist: Hriday G

DIFFICULTY

Medium

PREREQUISITES

None

PROBLEM

You are given an N \times M matrix where each column is a permutation of integers 1 to N. In one operation you can pick two rows x_1 and x_2 (x_1 \neq x_2) and two columns y_1 and y_2 (y_1 \neq y_2), and swap A[x_1][y_1] and A[x_2][y_1] and simultaneously also swap A[x_1][y_2] and A[x_2][y_2].
You need to perform some operations to make it so that the i-th row in every column contains the integer i.

EXPLANATION

Claim: The parity of the total number of column inversions can never change.

Proof

Consider what happens when you swap two elements in a column a = A[i][z], b = A[j][z] (1 \leq i \lt j \leq N, 1 \leq z \leq M). Let x be any arbitrary element A[k][z] such that i \lt k \lt j.

  • If x \lt a and x \lt b, then initially (i, k) is an inversion, while (k, j) is not. After swapping a and b, (i, k) stays an inversion and (k, j) also remains the same.
  • If x \gt a and x \gt b, then initially (k, j) is an inversion, while (i, k) is not. After swapping a and b, (k, j) stays an inversion and (i, k) also remains the same.
  • If a \lt x \lt b, then initially neither (i, k) nor (k, j) are inversions. After swapping a and b, both (i, k) and (k, j) become inversions.
  • Lastly, if b \lt x \lt a, then initially both (i, k) and (k, j) are inversions. After swapping a and b, neither (i, k) nor (k, j) are inversions.

In all four cases, the parity of the number of inversions having position k does not change. This applies to any and all elements at positions i \lt k \lt j. However, on swapping a and b, (i, j) will go from being an inversion to not being one, or vice versa. Hence after one swap, the parity of the total number of inversions will change, all things considered.

Now since two columns are being swapped simultaneously in every operation, the parity will change twice, i.e. revert to what it was. Thus before and after every operation, the parity of the total number of inversions remains the same.

We want to sort each column, which means that we need to make the total number of inversions zero. If initially this value is odd, it is impossible and the answer is -1. If not, we show that it is in fact always possible.

Since this is a constructive problem, there may be multiple correct solutions. Here we describe one such solution.

We can start by sorting the first M-1 columns completely using some operations. To do this, we can perform the required swaps on each column j (1 \leq j \lt M) and repeat them on the last column. This will take at most (N-1)(M-1) operations and we will end up with a matrix that looks like

\begin{matrix} 1 & 1 & \ldots & 1 & a_1 \\ 2 & 2 & \ldots & 2 & a_2 \\ 3 & 3 & \ldots & 3 & a_3 \\ \vdots & \vdots & & \vdots & \vdots \\ n-1 & n-1 & \ldots & n-1 & a_{n-1} \\ n & n & \ldots & n & a_n \end{matrix}

Now all that’s left is to sort the last column. We can pick any 3 elements in the last column and cyclically rotate their values without disturbing the remaining M-1 columns, using 4 operations.

How?

Consider any 3 rows and 3 columns of the matrix.
\begin{matrix} a_1 & \ldots & a_2 & \ldots & a_3 \\ \vdots & & \vdots & & \vdots \\ b_1 & \ldots & b_2 & \ldots & b_3 \\ \vdots & & \vdots & & \vdots \\ c_1 & \ldots & c_2 & \ldots & c_3 \end{matrix} \, \, \, \, \, \, \text{as} \, \, \, \, \, \, \, \begin{matrix} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \end{matrix}

Performing operation (x_1, y_1, x_2, y_2) = (1, 1, 2, 3),
\begin{matrix} b_1 & a_2 & b_3 \\ a_1 & b_2 & a_3 \\ c_1 & c_2 & c_3 \end{matrix}

Performing operation (2, 2, 3, 3),
\begin{matrix} b_1 & a_2 & b_3 \\ a_1 & c_2 & c_3 \\ c_1 & b_2 & a_3 \end{matrix}

Performing operation (1, 1, 2, 3),
\begin{matrix} a_1 & a_2 & c_3 \\ b_1 & c_2 & b_3 \\ c_1 & b_2 & a_3 \end{matrix}

Performing operation (2, 2, 3, 3),
\begin{matrix} a_1 & a_2 & c_3 \\ b_1 & b_2 & a_3 \\ c_1 & c_2 & b_3 \end{matrix}

We can do this N-2 times to ensure that A[i][M] = i for all 1 \leq i \leq N-2. We cannot swap the remaining two cells A[N-1][M] and A[N][M] since we need at least 3 distinct rows to perform the set of 4 operations. If they are already sorted, then we are done. Otherwise, there will be exactly one inversion left in the matrix, which is a contradiction. So it turns out they will also be sorted (if the parity of inversions is even).

The total number of operations required will thus be (N-1)(M-1) + 4(N-2), which is sufficient to pass under the given constraints.

Setter's Solution 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> //required
//#include <ext/pb_ds/tree_policy.hpp> //required

//using namespace __gnu_pbds; //required 
using namespace std;
//template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 

// ordered_set <int> s;
// s.find_by_order(k); returns the (k+1)th smallest element
// s.order_of_key(k); returns the number of elements in s strictly less than k

#define MOD              (1000000000+7) // change as required
#define pb               push_back
#define mp(x,y)          make_pair(x,y)
#define all(x)           x.begin(), x.end()
#define input(vec,N)     for(int i = 0; i < (N); i++) cin >> vec[i];
#define debug(...) logger(#__VA_ARGS__, __VA_ARGS__)
#define leftmost_bit(x)  (63-__builtin_clzll(x))
#define rightmost_bit(x) __builtin_ctzll(x) // count trailing zeros
#define set_bits(x)      __builtin_popcountll(x) 
#define pow2(i)          (1LL << (i))
#define is_on(x, i)      ((x) & pow2(i)) // state of the ith bit in x
#define set_on(x, i)     ((x) | pow2(i)) // returns integer x with ith bit on
#define set_off(x, i)    ((x) & ~pow2(i)) // returns integer x with ith bit off
  
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long int ll;

// highly risky #defines
#define int ll // disable when you want to make code a bit faster
#define endl '\n' // disable when dealing with interactive problems

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

template<typename ...Args>
void logger(string vars, Args&&... values) {
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

vector<vi> vec;
vector<vi> ans;
int N, M;

void print(vector<vi> &ans){
    cout << ans.size() << endl;
    for(vi &v: ans) 
        cout << v[0] << " " << v[1] << " " << v[2] << " " << v[3] << endl;
    return;
}

bool ok(){
    for(int i = 0; i < N; i++){
        for(int j = 0; j < M; j++){
            if(vec[i][j] != i) return false;
        }
    }
    return true;
}

void apply_op(int x1, int y1, int x2, int y2){
    ans.pb({x1+1, y1+1, x2+1, y2+1});
    swap(vec[x1][y1], vec[x2][y1]);
    swap(vec[x1][y2], vec[x2][y2]);
}

void solve(){
    // code starts from here

    cin >> N >> M;
    
    vec.clear();
    vec.assign(N, vi(M));
    ans.clear();

    for(auto &v: vec){
        input(v, M);
        for(int &i: v) i--;
    }
    
    for(int j = 0; j < M-1; j++){
        vi pos(N);
        for(int i = 0; i < N; i++) pos[vec[i][j]] = i;

        for(int i = 0; i < N; i++){
            if(vec[i][j] == i) continue;

            int index = pos[i];
            pos[vec[i][j]] = index;
            pos[vec[index][j]] = i;
            apply_op(i, j, index, M-1);
        }
    }

    vi pos(N);
    for(int i = 0; i < N; i++) pos[vec[i][M-1]] = i;

    if(N <= 2 || M <= 2){
        if(ok()){
            print(ans);
        } else{
            cout << -1 << endl;
        }
        return;
    }

    for(int i = 0; i < N-2; i++){
        if(vec[i][M-1] == i) continue;
        int index = pos[i];
        int buffer = N-1;

        if(index == buffer) buffer--;

        pos[i] = i;
        pos[vec[i][M-1]] = buffer;
        pos[vec[buffer][M-1]] = index;
        
        apply_op(i, M-3, buffer, M-1);
        apply_op(index, M-2, buffer, M-1);
        apply_op(i, M-3, buffer, M-2);
        apply_op(i, M-2, buffer, M-1);
        apply_op(index, M-2, buffer, M-1);
    }

    // for(int i = 0; i < N; i++){
    //  for(int j = 0; j < M; j++){
    //      cerr << vec[i][j]+1 << " ";
    //  }
    //  cerr << endl;
    // }
    // cerr << endl;

    if(ok()) print(ans);
    else cout << -1 << endl;
}


clock_t startTime;
double getCurrentTime() {
    return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    startTime = clock();
    // mt19937_64 rnd(time(NULL));
    
    int T = 1;
    cin >> T;

    while(T--){
        solve();
    }
    
    cerr << getCurrentTime() << endl;
    return 0;
}
Tester's Solution 
/* in the name of Anton */

/*
  Compete against Yourself.
  Author - Aryan (@aryanc403)
  Atcoder library - https://atcoder.github.io/ac-library/production/document_en/
*/

#ifdef ARYANC403
    #include <header.h>
#else
    #pragma GCC optimize ("Ofast")
    #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
    //#pragma GCC optimize ("-ffloat-store")
    #include<bits/stdc++.h>
    #define dbg(args...) 42;
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
    cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true) {
        char g=getchar();
        if(g=='-') {
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g&&g<='9') {
            x*=10;
            x+=g-'0';
            if(cnt==0) {
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd) {
            if(is_neg) {
                x=-x;
            }
            assert(l<=x&&x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l, int r, char endd) {
    string ret="";
    int cnt=0;
    while(true) {
        char g=getchar();
        assert(g!=-1);
        if(g==endd) {
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt&&cnt<=r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
    return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
    return readString(l,r,' ');
}

void readEOF(){
    assert(getchar()==EOF);
}

vi readVectorInt(int n,lli l,lli r){
    vi a(n);
    for(int i=0;i<n-1;++i)
        a[i]=readIntSp(l,r);
    a[n-1]=readIntLn(l,r);
    return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

bool checkIden(const vi &a){
    const int n=sz(a);
    for(int i=0;i<n;++i){
        if(a[i]!=i)
            return false;
    }
    return true;
}

vector<vi> readMatrix(int n,int m){
    vector<vi> a(m,vi(n));
    for(int i=0;i<n;++i){
        const auto b=readVectorInt(m,1,n);
        for(int j=0;j<m;++j)
            a[j][i]=b[j]-1;
    }
    for(auto v:a){
        sort(all(v));
        assert(checkIden(v));
    }
    return a;
}

void solve(){
    const int n=readIntSp(1,100),m=readIntLn(1,100);
    auto a=readMatrix(n,m);
    dbg(a);
    vector<vi> answers;
    auto operation=[&](lli x1,lli y1,lli x2,lli y2){
        // dbg(x1,y1,x2,y2);
        swap(a[x1][y1],a[x1][y2]);
        swap(a[x2][y1],a[x2][y2]);
        x1++;x2++;y1++;y2++;
        answers.pb({y1,x1,y2,x2});
    };

    auto prt=[&](bool fl){
        if(!fl){
            cout<<-1<<endl;
            return;
        }
        cout<<sz(answers)<<endl;
        for(const auto &v:answers)
            cout<<v[0]<<" "<<v[1]<<" "<<v[2]<<" "<<v[3]<<endl;
    };

    if(n==1){
        prt(true);
        return;
    }

    for(int i=0;i+1<m;++i){
        const auto &b=a[i];
        for(int j=0;j<n;++j){
            while(b[j]!=j){
                operation(i,j,m-1,b[j]);
            }
        }
        dbg(b);
    }
    dbg(n,m);
    const auto &b=a[m-1];
    if(m<=2||n<=2)
    {
        prt(checkIden(b));
        return;
    }

    vi perm(n);
    for(lli j=0;j<n;++j)
        perm[b[j]]=j;
    auto shift=[&](const lli x,const lli y,const lli z){
        dbg("shift",x,y,z,b[x],b[y],b[z]);

        swap(perm[b[y]],perm[b[z]]);
        operation(1,y,m-1,z);

        operation(0,x,1,y);

        swap(perm[b[x]],perm[b[z]]);
        operation(1,x,m-1,z);

        operation(0,x,1,y);
        dbg("shifted",b[x],b[y],b[z]);
    };

    dbg("init",b);
    for(lli j=0;j+2<n;++j){
        while(b[j]!=j){
            if(perm[j]==n-1)
                shift(perm[j],n-2,j);
            else
                shift(perm[j],n-1,j);
        }
        dbg(j,b,sz(answers));
    }
    dbg(b);
    prt(checkIden(b));
}

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
lli T=readIntLn(1,100);
while(T--)
{
    solve();
}   aryanc403();
    readEOF();
    return 0;
}

Feel free to share your approach. Suggestions are welcomed.

2 Likes
2

Idea was cool but this was an absolute pain to code tbh