How do you construct an array with one inversions? How about three? How about six?

You can only scramble the order of the small numbers and keep the large ones ordered. Try the sample test case.

In the sample, you can construct 3 2 4 1 5. Where 1, 2, 3 are in reverse order and 4 adds an inversion by being before 1. Try to generalize this.

We start with $$$a_i=i$$$ with $$$0$$$ inversions. First, find the largest $$$m$$$ such that $$$\frac{m(m-1)}{2}\leq k$$$. Reverse the first $$$m$$$ numbers to get $$$\frac{m(m-1)}{2}$$$ inversions. $$$m$$$ can be found by brute force.

And then let $$$k'=k-\frac{m(m-1)}{2}$$$, this is how many inversion you needed left. Swap the number $$$m+1$$$ just $$$k'$$$ spots to the left and we're done.

(You can use a stack or vector to reverse as well, as shown in the code).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int a[1000005];

int main(){
    vector <int> pre;
    int n, id;
    ll tg;
    cin>>n>>tg;
    id=0;
    while(tg-id>0){
        pre.pb(id+1);
        tg-=id;
        id++;
    }
    for(int i=1; i<=n; i++) a[i]=i;
    reverse(a+1, a+id+1);
    int k=tg;
    id++;
    while(k>0){
        swap(a[id], a[id-1]);
        id--;
        k--;
    }
    for(int i=1; i<=n; i++) cout<<a[i]<<" ";
}

Solve the problem for $$$n=9$$$ and $$$k=3$$$.

Put numbers in $$$\mod k$$$ order would be good. For example you have 3 6 9 1 4 7 2 5 8 for $$$n=9, k=3$$$. However, sometimes it won't work.

If $$$k \lt \sqrt{n}$$$ it becomes impossible. For proof, search for the Erdős–Szekeres Theorem.

See hint 3 for impossible cases.

For the possible cases. Put all numbers that are $$$0 \mod k$$$ in increasing order, then all numbers that are $$$1\mod k$$$ in increasing order, then put $$$2 \mod k$$$ ones, and so on.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int main(){
    int t;
    cin>>t;
    while(t--){
        vector <int> v;
        int n,k;
        cin>>n>>k;
        if(k*k<n){
            cout<<"IMPOSSIBLE\n";
            continue;
        }
        for(int i=0; i<k; i++){
            for(int j=1; j<=k; j++){
                v.pb(j*k-i);
            }
        }
        for(int i: v){
            if(i<=n) cout<<i<<" ";
        }
        cout<<'\n';
    }
}

For $$$a=[1,2,3,4], b=[4,3,1,2]$$$. Note that $$$[2,1,4,3]$$$ is a solution.

Build a graph with edges from $$$a_i$$$ to $$$b_i$$$ for every $$$i$$$, how do you construct a solution for the test case in hint 1? When does it not work?

Build a graph from $$$a_i$$$ to $$$b_i$$$ for every $$$i$$$. And then if there isn't any $$$2$$$-cycles in the graph, just make $$$c_i$$$ the index of the vertex where you walk $$$2$$$ steps from $$$a_i$$$.

If there is a $$$2$$$ cycle then $$$c_i=a_i$$$ for those two vertices. Store those pairs into a queue or vector, and then merge two pairs to make a new $$$4$$$-cycle any way you want. One pair might be left, then you need to merge the last pair into an existing cycle as well. $$$n=2$$$ is impossible.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
 
const int MAXN=200005;
int a[MAXN], b[MAXN], pos[MAXN], g[MAXN], ans[MAXN], bad[MAXN];
queue <pii> qu;
 
int main(){
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++){
        cin>>b[i];
        pos[b[i]]=i;
        g[a[i]]=b[i];
    }
    for(int i=1; i<=n; i++){
        ans[i]=g[g[a[i]]];
        if(ans[i]==a[i]){
            if(!bad[i]) qu.push({i, pos[a[i]]});
            bad[pos[a[i]]]=1;
            bad[i]=1;
        }
    }
    pii temp1, temp2;
    while(qu.size()>1){
        temp1=qu.front();
        qu.pop();
        temp2=qu.front();
        qu.pop();
        swap(ans[temp1.first], ans[temp2.first]);
        swap(ans[temp2.second], ans[temp1.second]);
        bad[temp1.first]=bad[temp2.first]=bad[temp1.second]=bad[temp2.second]=0;
    }
    if(!qu.empty()){
        int x1=0, x2=0;
        if(n==2){
            cout<<"IMPOSSIBLE";
            return 0;
        }
        temp1=qu.front();
        qu.pop();
        for(int i=1; i<=n; i++){
            if(x1 && x2) break;
            if(!bad[i]){
                if(x1) x2=i;
                else x1=i;
            }
        }
        swap(ans[temp1.first], ans[x1]);
        swap(ans[temp1.second], ans[x2]);
    }
    for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
}

Solve when $$$n=p-1$$$ where $$$p$$$ is a prime.

A recursive solution is possible. How do you deal with the last few terms first?

Use any sieve method to find all primes below $$$10^6$$$.

If $$$n+1$$$ is a prime then you solve directly by letting the first permutation be identity permutation and the second one be reversed.

Otherwise, put the second one and the first both as identity first. Find an $$$i \lt n$$$ such that $$$n+i$$$ is prime, reverse the subarray from the $$$i$$$th term to the $$$n$$$th term and solve it for $$$n=i-1$$$ (recursively doing so until $$$n+1$$$ is prime where you hit the base case).

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int MAXN=200005;
bool prime[MAXN];
int ans[MAXN];
 
void solve(int n){
    if(prime[n+1]){
        for(int i=1; i<=n; i++) ans[i]=n-i+1;
        return;
    }
    for(int i=2; i<=n; i++){
        if(prime[n+i]){
            reverse(ans+i, ans+n+1);
            solve(i-1);
            break;
        }
    }
}
 
int main(){
    for(int i=2; i<MAXN; i++) prime[i]=1;
    for(int i=2; i*i<MAXN; i++){
        if(prime[i]){
            for(int j=i*i; j<MAXN; j+=i) prime[j]=0;
        }
    }
    ll n;
    cin>>n;
    for(int i=1; i<=n; i++) ans[i]=i;
    solve(n);
    for(int i=1; i<=n; i++) cout<<i<<" ";
    cout<<'\n';
    for(int i=1; i<=n; i++) cout<<ans[i]<<" ";
}

As you might question in the solution: why does there always an $$$1\leq i \lt n$$$ such that $$$n+i$$$ is prime? Bertrand's Postulate tell us there is a prime $$$p$$$ such that $$$n \lt p \lt 2n$$$ for all $$$n \gt 1$$$. I don't know how to prove the theorem though so don't ask me.

We first disregard the limit that each pair of player can play only one game. Develop a greedy solution (with the fact that the sum of $$$x_i$$$ is not too large.

Set the limit back. We know that the player who want to play the most matches matters, so we need to deal with them first. Can you deal with them greedily?

What if a player want to play a lot of games and there are not enough opponents left during your greedy?

From now on, if a player still wants to play $$$k$$$ games I said they have $$$k$$$ "remnant games".

Use a priority queue to store how many remnants game are left for each player. Take out the one with the most remnant games and pair opponents with them (pair the opponents in decreasing order of remnant games). If at any moment the player with the most remnant games can't find enough opponents, then halt and output IMPOSSIBLE

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
 
int tot;
int oddcnt;
priority_queue <pii> pq;
vector <pii> ans;
vector <pii> temp;
 
int main(){
    int n;
    cin>>n;
    int num;
    bool possible=true;
    for(int i=1; i<=n; i++){
        cin>>num;
        if(num>0) pq.push({num, i});
    }
    pii cur, nxt;
    while(!pq.empty()){
        cur=pq.top();
        pq.pop();
        if(cur.first>pq.size()){
            possible=false;
            break;
        }
        else{
            for(int i=0; i<cur.first; i++){
                nxt=pq.top();
                pq.pop();
                ans.pb({cur.second, nxt.second});
                if(nxt.first>1) temp.pb({nxt.first-1, nxt.second});
            }
            while(temp.size()>0){
                pq.push(temp.back());
                temp.pop_back();
            }
        }
    }
    if(possible){
        cout<<ans.size()<<'\n';
        for(pii x: ans){
            cout<<x.first<<" "<<x.second<<'\n';
        }
    }
    else cout<<"IMPOSSIBLE";
}

Start with a wrong board. Try applying swaps to it. Which swaps would you want to perform?

You'd only like the ones that increases the number of distinct row/column sums. But we don't know how to find them at all, so what do we do?

$$$n \lt 4$$$ can be checked to be impossible.

Start with a board where every cell on the $$$i$$$th row is filled in with number $$$i$$$. This board would be incorrect but it's okay. We repeatedly randomly choose two cells to swap. If swapping them increase the number of distinct row/column sums then we swap them, otherwise we don't swap them. $$$50000$$$ random tries passes as my code do get AC.

A bit on implementation, though. Carefully store the row/column sums and the number of distinct sum values. When you test performing a swap make sure to do it in $$$O(1)$$$ by these store values.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
 
const int MAXN=1005;
int g[MAXN][MAXN];
int r[MAXN], c[MAXN], r1, r2, c1, c2;
int cnt=0, ori;
int ex[1000005];
 
void rem(int x){
    ex[x]--;
    if(ex[x]==0) cnt--;
}
 
void add(int x){
    ex[x]++;
    if(ex[x]==1) cnt++;
}
 
int res;
void change(int x1, int y1, int x2, int y2){
    rem(r[x1]); rem(r[x2]); rem(c[y1]); rem(c[y2]);
    r[x1]+=(g[x2][y2]-g[x1][y1]);
    c[y1]+=(g[x2][y2]-g[x1][y1]);
    r[x2]-=(g[x2][y2]-g[x1][y1]);
    c[y2]-=(g[x2][y2]-g[x1][y1]);
    add(r[x1]); add(r[x2]); add(c[y1]); add(c[y2]);
    swap(g[x1][y1], g[x2][y2]);
}
 
int main(){
    int n;
    cin>>n;
    if(n<=3){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            g[i][j]=i;
            r[i]+=g[i][j];
            c[j]+=g[i][j];
        }
    }
    for(int i=1; i<=n; i++){
        add(r[i]);
        add(c[i]);
    }
    int sp=0;
    while(cnt<2*n && sp<50000){
        r1=rand()%n+1;
        c1=rand()%n+1;
        r2=rand()%n+1;
        c2=rand()%n+1;
        ori=cnt;
        change(r1, c1, r2, c2);
        if(cnt<ori) change(r1, c1, r2, c2);
        sp++;
    }
    if(cnt<2*n){
        cout<<"IMPOSSIBLE";
        return 0;
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cout<<g[i][j]<<" ";
        }
        cout<<'\n';
    }
}

Try to find as many cases with no solutions first. The trivial requirements are that $$$3|mn$$$ and $$$\min(m, n) \gt 1$$$.

When one of $$$m, n$$$ is $$$3$$$, and the other one is odd. This is impossible. Other cases that meet all the aforementioned requirements seems to not be disprovable.

You can definitely construct a $$$2\times 3$$$ rectangle. What else can you construct?

You can construct a $$$5\times 9$$$ rectangle!

114414411
124112431
223552233
133451311
114411331

Try to do casework and decompose the board into $$$2\times 3$$$, $$$3\times 2$$$ and $$$5\times 9$$$ (or $$$9\times 5$$$) rectangles.

Please read all the hints first. From now on, I'd assume you had read them. We work on an $$$n\times m$$$ board ($$$n$$$ rows, $$$m$$$ columns).

If $$$m=1$$$ or $$$n=1$$$ or $$$3\nmid mn$$$, then there's no solution.

If one of $$$m, n$$$ is $$$3$$$ and the other one is odd, then there's no solution. That's it for the case with no solutions. From now on we would assume we are not on these cases.

If $$$n=2$$$ then fill it with $$$2\times 3$$$ block.

If $$$n \gt 2$$$ but $$$n$$$ is even then still fill it with $$$2\times 3$$$ blocks, beware of adjacent letters.

If $$$n$$$ is odd but $$$m$$$ is even. Fill the first $$$3 times m$$$ with $$$3\times 2$$$ blocks. Then it reduces to the last case.

If they both are odd, then fill the top left $$$5\times 9$$$ first, and then fill the remaining $$$(n-5)\times 9$$$ on the left, and then the remaining board at last. You can do this recursively, just beware of adjacent letters.

(My solution code might involve a transformation, though)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int g[100][100];
int aa[2][3]={{1,1,2},{1,2,2}};
int bb[3][2]={{1,1},{1,2},{2,2}};
int cc[5][9]={{1,1,4,4,1,4,4,1,1},{1,2,4,1,1,2,4,3,1},{2,2,3,5,5,2,2,3,3},{1,3,3,4,5,1,3,1,1},{1,1,4,4,1,1,3,3,1}};
string s="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void put(int a, int b, int type, int t){
    if(type==1){
        for(int i=0; i<2; i++){
            for(int j=0; j<3; j++){
                g[a+i][b+j]=aa[i][j]+t;
            }
        }
    }
    else if(type==2){
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                g[a+i][b+j]=bb[i][j]+t;
            }
        }
    }
    else{
        for(int i=0; i<5; i++){
            for(int j=0; j<9; j++){
                g[a+i][b+j]=cc[i][j]+t;
            }
        }
    }
}

void fill(int a, int b, int x, int y, int delta){
    //delta is for not repeating letter for adjacent piece
    if(x==2){//2*y board
        for(int i=0; i<y; i+=3){
            put(a, b+i, 1, delta);
        }
        return;
    }
    if(x%2==0){//2k*y board
        int temp1=delta;
        for(int i=0; i<x; i+=2){
            if(i%4==0) fill(a+i, b, 2, y, temp1);
            else fill(a+i, b, 2, y, temp1+2);
        }
        return;
    }
    else if(y%2==0){//x*2k board
        int temp2=delta;
        for(int i=0; i<y; i+=2){
            if(i%4) put(a, b+i, 2, temp2+4);
            else put(a, b+i, 2, temp2+6);
        }
        fill(a+3, b, x-3, y, temp2);
    }
    else{
        //for other board, decompose them into
        //one 5*9, one (x-5)*9, and one remaining chunk.
        int temp3=delta;
        put(a, b, 3, temp3+16);
        fill(a+5, b, x-5, 9, temp3+12);
        fill(a, b+9, x, y-9, temp3);
    }
}

void say(int x, int y, bool trans){
    if(trans){
        for(int i=0; i<y; i++){
            for(int j=0; j<x; j++){
                cout<<s[g[j][i]-1];
            }
            cout<<'\n';
        }
    }
    else{
        for(int i=0; i<x; i++){
            for(int j=0; j<y; j++){
                cout<<s[g[i][j]-1];
            }
            cout<<'\n';
        }
    }
}

int main(){
    int qq;
    cin>>qq;
    int m, n;
    for(int i=1; i<=qq; i++){
        cin>>m>>n;
        if(m%3&&n%3){
            cout<<"NO\n";
        }
        else if(m%2&&n%2&&(m==3||n==3)){
            cout<<"NO\n";
        }
        else if(m==1||n==1){
            cout<<"NO\n";
        }
        else if(n%3==0){
            cout<<"YES\n";
            fill(0,0,m,n,0);
            say(m,n,false);
        }
        else{
            cout<<"YES\n";
            fill(0,0,n,m,0);
            say(n,m,true);
        }
    }
}

There is a research paper you can view that contains a whole solution (but not implementation).

I come up with a slightly different solution. Haven't been able to implement it yet though. But this tutorial is written at 2am-4am local time. I would try to update it when I can. At least I would put my solution here in a few days, I hope.