[Solved] Swap Shift January Long 2023 CodeChef

Swap Shift: Blobo2 is in his practical exam. The teacher gave him a permutation A of N integers.

The teacher has allowed Blobo2 to make a certain type of operation on the permutation. In one operation, he can:

• Apply left shift on the permutation. In other words, he can take the first element of the permutation and move it to the back of the permutation.

The teacher has asked Blobo2 to find the lexicographically smallest permutation possible after applying any (possibly zero) number of given operations.

Since Blobo2 wants to impress his teacher, he decided to perform at most two swaps in addition to the allowed operation.

Find the lexicographically smallest possible permutation Blobo2 can generate after applying at most two swaps and any number of given operations.

Note:

• A permutation of size N consists of all integers from 1 to N exactly once.
• During a swap, Blobo2 can choose any two indices i and j (1≤i,j≤N) and swap Ai​ with ��Aj​.
• A permutation X is said to be lexicographically smaller than a permutation Y if Xi​<Yi​, where i is the first index where both the permutations differ.

Input Format

• The first line of input will contain a single integer T, denoting the number of test cases.
• The second line will contain the integer N, denoting the size of the permutation.
• The third line contains N distinct integers, the elements of the permutation A.

Output Format

Output the lexicographically smallest possible permutation Blobo2 can generate after applying at most two swaps and any number of given operations.

Constraints

• 1≤T≤5⋅10^5
• 1≤N≤10^5
• 1≤Ai​≤N
• A is a permutation
• The sum of N over all test cases won’t exceed 5⋅10^5.

Sample 1:

Input

2
5
5 2 1 4 3
5
3 5 2 1 4

Output

1 2 3 4 5 
1 2 3 4 5

Explanation:

Test case 11: Blobo2 can perform 2 swaps:

• For the first swap, Blobo2 can swap the first and second elements: [5​,2​,1,4,3] →[2,5,1,4,3]
• For the second swap, he can swap the first and fourth elements: [2​,5,1,4​,3] → [4,5,1,2,3]

Finally, Blobo2 will left shift the array two times which will lead to the lexicographically smallest permutation: [1,2,3,4,5].

Test case 22: Blobo2 can perform 22 swaps:

• For the first swap, Blobo2 can swap the third and fifth elements: [3,5,2​,1,4​] →[3,5,4,1,2]
• For the second swap, he can swap the second and third elements: [3,5​,4​,1,2] →[3,4,5,1,2]

Finally, Blobo2 will left shift the array two times which will lead to the lexicographically smallest permutation: [1,2,3,4,5].

Solution

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef {
    static int[] A = new int[100010];
    static int[] tmp = new int[100010];
    static int[] pos = new int[100010];
    static int[] ans = new int[100010];
    static int n;
    static void add(int cnt){
        for(int i = 1; i <= n; i ++) pos[tmp[i]] = i;
        for(int i = 1; i <= n; i ++){
            if(cnt == 0) break;
            if(tmp[i] == i) continue;
            int id = pos[i];
            pos[tmp[i]] = id;
            tmp[id] = tmp[i];
            tmp[i] = i;
            cnt --;
        }
    }
    static int ok(){
        for(int i = 1; i <= n; i ++) {
            if(tmp[i] > ans[i]) return 0;
            else if(tmp[i] < ans[i]) return 1;
        }
        return 0;
    }
    static void change(){
        if(ok() == 0) return;
        for(int i = 1; i <= n; i ++) ans[i] = tmp[i];
    }
    public static void main(String[] args) throws IOException {
        Scanner cin = new Scanner(System.in);
        int t = cin.nextInt();
        while(t -- > 0){
            n = cin.nextInt();
            for(int i = 1; i <= n; i ++) A[i] = cin.nextInt();
            if(n <= 4){
                for(int i = 1; i <= n; i ++) System.out.print(i + " ");
                System.out.println();
                continue;
            }
            // sauravhathi
            for(int i = 1; i <= n; i ++) ans[i] = A[i];
            int id = 0;
            for(int i = 1; i <= n; i ++) if(A[i] == 1) id = i;
            for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 2 + 5 * n) % n + 1];
            add(2);
            change();
            for(int i = 1; i <= n; i ++) if(A[i] == 2) id = i;
            for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 3 + 5 * n) % n + 1];
            add(2);
            change();
            for(int i = 1; i <= n; i ++) if(A[i] == 3) id = i;
            for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 4 + 5 * n) % n + 1];
            add(2);
            change();
            for(int i = 1; i <= n; i ++) if(A[i] == 4) id = i;
            for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 5 + 5 * n) % n + 1];
            add(2);
            change();
            id = 0;
            for(int i = 1; i < n; i ++){
                if(A[i] == 2 && A[i + 1] == 1) id = i;
            }
            if(A[n] == 2 && A[1] == 1) id = n;
            if(id != 0){
                for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 2 + 5 * n) % n + 1];
                add(2);
                change();
            }
            id = 0;
            for(int i = 1; i < n; i ++){
                if(A[i] == 3 && A[i + 1] == 2) id = i;
            }
            if(A[n] == 3 && A[1] == 2) id = n;
            if(id != 0){
                for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 3 + 5 * n) % n + 1];
                add(2);
                change();
            }
            id = 0;
            for(int i = 1; i < n - 1; i ++){
                if(A[i] == 3 && A[i + 2] == 1) id = i;
            }
            if(A[n - 1] == 3 && A[1] == 1) id = n - 1;
            if(A[n] == 3 && A[2] == 1) id = n;
            if(id != 0){
                for(int i = 1; i <= n; i ++) tmp[i] = A[(i + id - 2 + 5 * n) % n + 1];
                add(2);
                change();
            }
            for(int i = 1; i <= n; i ++) System.out.print(ans[i] + " ");
            System.out.println();
        }
    }
}

def rotate(p):
    i = p.index(0)
    return p[i : ] + p[: i]
    
def swap(p, i1, i2):
    i1 %= len(p)
    i2 %= len(p)
    rv = p.copy()
    rv[i1], rv[i2] = rv[i2], rv[i1]
    return rv
    
def swaps(p):
    j = 1
    while j != len(p) and p[j] == j:
        j += 1
    if j == len(p):
        return [p]
    i1 = p.index(1)
    tries = [(j, p.index(j)), (0, i1 - 1), (0, i1), (0, -1), (0, -2), (i1, i1 - 1)]
    if len(p) > 2:
        tries.append((i1, p.index(2) - 1))
    return [rotate(swap(p, j, k)) for j, k in tries]
    
for _ in range(int(input())):
    input()
    v = [int(x) - 1 for x in input().split()]
    for x in min(r for q in swaps(rotate(v)) for r in swaps(q)):
        print(x + 1, end = ' ')
    print()

#include<bits/stdc++.h>
namespace {
using namespace std;
// https://github.com/atcoder/ac-library/
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while(tt--) {
    int n;
    cin >> n;
    VI a(n);
    rep(i, n) cin >> a[i], a[i]--;
    VI ans(n, n);
    VI b(n), pos(n);
    auto swp = [&](int i, int j) {
      int vi = b[i], vj = b[j];
      swap(b[i], b[j]);
      swap(pos[vi], pos[vj]);
    };
    rep(s, n) {
      if (a[s] < 3 || a[(s + 1) % n] < 3 || a[(s + 2) % n] < 3) {
        rep(i, n) b[i] = a[(s + i) % n];
        rep(i, n) pos[b[i]] = i;
        int rest = 2;
        rep(i, n) if (b[i] != i) {
          swp(pos[i], i);
          if (--rest == 0) break;
        }
        chmin(ans, b);
      }
    }
    rep(i, n) cout << ans[i] + 1 << " \n"[i + 1 == n];
  }
}

Happy Learning – If you require any further information, feel free to contact me.