# P7SWAPS - Editorial

Setter: Ashish Kumar
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

Easy

# PREREQUISITES

Permutation cycles or Binary Lifting.

# PROBLEM

Given two permutations A and P of length N each, process the following operations.

• Permute the array A according to the order defined in permutation P. This replaces array A with B where B_i = A_{P_i}
• Swap A_x and A_y for given x and y
• Print A_x for some given x

# QUICK EXPLANATION

• Instead of updating A at each first operation, we shall build a utility to determine the position of the element in the original A such that, after the first operation is applied K times, that element is at position x. This utility shall allow us to quickly answer the third query as well.
• In order to handle swaps, we shall find the positions of elements currently at position x and y in the original array A and perform swap there.
• This utility can be build by storing permutation cycles of P^{-1} (Inverse permutation of P), or by using binary lifting on inverse permutation P

# EXPLANATION

The naive way to solve this problem would be to simulate the whole process. Operation 1 takes O(N) time, and operation 2 and 3 takes O(1) time each. This shall time out.

It is easy to see, that any solution actually simulating operation 1 shall time out. So the solution must not involve simulating operation 1 at least.

### Problem without Swaps

Ignore swaps for now.

Defining A as the original array given in input, and B denotes the most updated array after performing K operations of type 1 for some K.

Let’s define a function f_k(u), which return position p such that A_u = B_p. i.e. gives the position of element A_u in array B. It finds which position shall element at position u reach after first operation is applied K times.

Since this function is both one-one and onto function, we can define it’s inverse function g_k(u), which returns position p such that A_p = B_u. i.e., it returns the position of element in array A, which, after K operations of type 1, is at position u.

It is easy to see that f_k(g_k(u)) = u and g_k(f_k(u)) = u holds.

Hence, if there were no swap operations, we can solve the problem by maintaining a counter variable K denoting the number of times operation 1 is performed. On every operation of type 3, for position x, we want to find position p such that f_k(p) = x, which is same as finding position g_k(x).

Later section shall demostrate computing the values of f_k(u) and g_k(u).

### Problem with swaps

Now, in order to incorporate swaps in our previous swaps, we need to do something.

Let’s assume k operations of type 1 have been performed on array A to obtain array B, and now we have swap operation for positions x and y.

We want to swap B_x and B_y, but we don’t have the B array computed. We need to make a swap in the array A, which would be equivalent to swapping B_x and B_y. We can see Swapping B_x and B_y is equivalent to swapping A_{g_k(x)} and A_{g_k(y)}, since B_x = A_{g_k(x)} holds by our definition of function f and g.

Hence, whenever we get a swap operation on positions x and y, we compute p = g_k(x) and q = g_k(y) and swap them in original array A which can be done in O(1).

If we can compute g_k(u) efficiently, we have solved the problem.

### Computing g_k(u) efficiently

Function f is used just for explanation, we don’t need to actually compute f_k(u) to solve this problem. g_k(u) is the position p of element in original array A which after k operations of type 1, reaches position u.

Let’s use P^{-1} to represent permutation, such that applying operation 1 first in order of P and then applying operation 1 in order of permutation P^{-1}, we get the original permutation.

Explanding our definition of f to f_k(P, u) denote the position of A_u in final array, after k operations of type 1 are applied using permutation P.

It is easy to notice that f_k(P, u) = g_k(P^{-1}, u) and g_k(P, u) = f_k(P^{-1}, u).

Hence, we find permutation P^{-1} (By setting Q_{P_i} = i), and find f_k(P^{-1},u).

Setter and Tester’s approach
Both setter and tester made a list of permutation cycles, a list containing a list of positions, where each inner list contains a set of positions that moves to each other’s position after an operation. No position moves from one inner list to another inner list.

For permutation [2,4,3,1,6,5], there are three permutation cycles (2,4,1)(3)(6,5). Each operation actually represents a right cyclic shift in each of these sublists, and to obtain element at position p after k operations, we find the sublist containing position p, and its position in that sublist, say q. Then, its new position shall be the position stored at location (q+K) \bmod S where S is the size of the sublist.

Tester, instead of computing P^{-1} and then doing this, replaced q with (q-K) \bmod S which is equivalent to performing a left cyclic shift.

Editorialist’s approach
Since Q \leq 10^5, K cannot exceed 10^5 as well. I used P^{-1} (denoted by invP in my implementation). Let’s apply binary lifting here. We can see that f_k(u) = f_{k-x}(f_x(u)) holds. For each u, precompute f_{2^b}(u) for b upto log(Q). When we need to compute f_k(u) for some k, we can write it as sum of powers of 2 and apply those.

For k = 13, we can write 13 = 8+4+1, so f_{13}(u) = f_8(f_4(f_1(u))). All these values are precomputed.

# TIME COMPLEXITY

For the setter and tester’s approach, the time complexity is O(N+Q) per test case.
For the editorialist’s approach, time complexity is O((N+Q)*log(Q)) per test case.

# SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define ll long long int
#define FastIO ios_base::sync_with_stdio(false),cin.tie(0)
#define f(n) for(int i=0;i<n;i++)
#define pb push_back
#define pi pair<ll,ll>
#define endl "\n"
#define WRITE(f) freopen(f, "w", stdout)

void dfs(int s,vector<int>&v,vector<int>&P,int visited[])
{
visited[s]=1;
v.pb(s);

int x=P[s];

if(!visited[x])
{
dfs(x,v,P,visited);
}
}

int sum_n=0,sum_q=0;

void solve()
{
int n;cin>>n;
sum_n+=n;
assert(sum_n>=1 and sum_n<=100000);

vector<int>A(n+1),P(n+1);

int cnt[n+1]{0};

f(n){
cin>>A[i+1];

assert(A[i+1]>=1 and A[i+1]<=n);
assert(cnt[A[i+1]]==0);
cnt[A[i+1]]++;
}

memset(cnt,0,sizeof cnt);

f(n){
cin>>P[i+1];

assert(P[i+1]>=1 and P[i+1]<=n);
assert(cnt[P[i+1]]==0);
cnt[P[i+1]]++;
}

// get cycles for array P

vector<int>v[n+1];
int visited[n+1]{0};

for(int i=1;i<=n;i++)
{
if(!visited[i]){
dfs(i,v[i],P,visited);
}
}

// store for each index, which cycle it belongs to
// as well as position in the cycle

vector<pi>arr(n+1);

for(int i=1;i<=n;i++)
{
for(int j=0;j<v[i].size();j++)
{
int x=v[i][j];
arr[x]={i,j};
}
}

int q;cin>>q;

sum_q+=q;
assert(sum_q>=1 and sum_q<=100000);

int k=0;

//store initial position of numbers in array A

int pos[n+1];

for(int i=1;i<=n;i++)
{
int x=A[i];
pos[x]=i;
}

while(q--)
{
int t;cin>>t;
assert(1<=t and t<=3);

if(t==1)
{
k++;
}
else if(t==2)
{
int x,y;
cin>>x>>y;
assert(1<=x and x<=n);
assert(1<=y and y<=n);
assert(x!=y);

// we need to get element at position x before k rotations
// same for y.

// for x
int cycle=arr[x].F,position=arr[x].S,sz=v[cycle].size();
position=(position-k)%sz;
position=(position+sz)%sz;
int new_x=v[cycle][position];
int a=A[new_x];

// for y
cycle=arr[y].F,position=arr[y].S,sz=v[cycle].size();
position=(position-k)%sz;
position=(position+sz)%sz;
int new_y=v[cycle][position];
int b=A[new_y];

// we swap values in original array as well as pos array
swap(pos[a],pos[b]);
swap(A[new_x],A[new_y]);
}
else
{
int x;cin>>x;

assert(1<=x and x<=n);

// we check for this position , which cycle it belongs to and,
// which index will be here after k rotations.

int id=x;
int cycle=arr[id].F,position=arr[id].S,sz=v[cycle].size();
int newpos=((position-k)%sz+sz)%sz;
cout<<A[v[cycle][newpos]]<<endl;
}
}
}

int main()
{
FastIO;

int t=1;
cin>>t;

assert(1<=t and t<=1000);

for(int i=1;i<=t;i++)
{
solve();
}
return 0;
}

Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <numeric>

#ifdef HOME
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

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) {
assert(cnt > 0);
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) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../P7SWAPS_8.in", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T;
int sumN = 0;
int sumQ = 0;
forn(tc, T)
{
vector<bool> au(N);
sumN += N;
vector<int> A(N), P(N);
int ctr = 0;
for (auto& ai : A)
{
if (++ctr == N)
else
assert(ai > 0 && ai <= N);
assert(!au[ai]);
au[ai] = true;
}
ctr = 0;
vector<bool> pu(N);
for (auto& pi : P)
{
if (++ctr == N)
else
--pi;
assert(pi >= 0 && pi < N);
assert(!pu[pi]);
pu[pi] = true;
}

vector<bool> used(N);
vector<vector<int> > arr;
vector<pair<int, int> > posArr(N);

forn(i, N)
{
if(used[i])
continue;
vector<int> narr;

int act = i;
while (!used[act])
{
used[act] = true;
posArr[act] = {arr.size(), narr.size()};
narr.push_back(act);
act = P[act];
}
arr.push_back(narr);
}

sumQ += Q;
int permCounter = 0;

auto calcPos = [&](int pos)
{
int posA = posArr[pos].first;
int posAPos = posArr[pos].second;

int pcn = permCounter % arr[posA].size();

posAPos -= pcn;

if (posAPos < 0)
posAPos += arr[posA].size();

return arr[posA][posAPos];
};

forn(q, Q)
{
char c = getchar();
assert(c >= '1' && c <= '3');
int qt = c - '0';
switch (qt)
{
case 1:
++permCounter;
break;
case 2:
{
assert(pos1 != pos2);
--pos1, --pos2;

int origPos1 = calcPos(pos1);
int origPos2 = calcPos(pos2);

swap(A[origPos1], A[origPos2]);
break;
}
case 3:
{
--pos;
int origPos = calcPos(pos);

printf("%d\n", A[origPos]);
break;
}
default:
assert(false);
break;
}
}
}
assert(sumN <= 100'000);
assert(sumQ <= 100'000);
assert(getchar() == -1);
return 0;
}

Editorialist's Solution
import java.util.*;
import java.io.*;
class P7SWAPS{
//SOLUTION BEGIN
int B = 20;
void pre() throws Exception{}
void solve(int TC) throws Exception{
int N = ni();
int[] A = new int[N], P = new int[N];
for(int i = 0; i< N; i++)A[i] = ni();
for(int i = 0; i< N; i++)P[i] = ni()-1;

int[] invP = new int[N];
for(int i = 0; i< N; i++)invP[P[i]] = i;
int[][] nxt = new int[B][N];
for(int i = 0; i< N; i++)nxt[i] = invP[i];
for(int b = 1; b< B; b++)
for(int i = 0; i< N; i++)
nxt[b][i] = nxt[b-1][nxt[b-1][i]];

int Q = ni();
int count = 0;
for(int q = 0; q< Q; q++){
int ty = ni();
if(ty == 1)count++;
else if(ty == 2){
int u = ni()-1, v = ni()-1;
int posU = pos(nxt, u, count), posV = pos(nxt, v, count);
int tmp = A[posU];
A[posU] = A[posV];
A[posV] = tmp;
}else pn(A[pos(nxt, ni()-1, count)]);
}

}
int pos(int[][] nxt, int u, int steps){
for(int b = B-1; b >= 0; b--)
if(((steps>>b)&1) == 1)
u = nxt[b][u];
return u;
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
static boolean multipleTC = true;
void run() throws Exception{
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new P7SWAPS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}

StringTokenizer st;
}

}

String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
}catch (IOException  e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}

String nextLine() throws Exception{
String str = "";
try{
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}


Feel free to share your approach. Suggestions are welcomed as always. 6 Likes

Very cool problem!, kudos to the author. My linear time solution.

10 Likes

Can you please give links to more problems on Permutation cycle and similar concept.

1 Like

1 Like

Can somebody please help me debug my solution. Its based on the same idea as the Setter’s solution.

permutations
This PDF helped me understand the basics of permutation groups and how cycles work

4 Likes

can anyone give more insight or where binary up lifting can be applied?

I just implemented the same idea which I said here, which part aren’t you able to comprehend?.

Damn, These type of Questions actually reminds you yet again how lovely codechef questions are! Loved this one!

3 Likes

I am a beginner.
I tried to solve this problem in C language with out any knowledge in permutations.
please check my code it is giving correct output too but got TLE.
Is it possible to write an answer for this in this way.
If yes, help me to modify this code. Pls…
#include <stdio.h>
#define N 100000
int main()
{
int t, n, a[N], b[N], p[N], i, j, nt, x, y, z, temp, l;
scanf("%d",&t);
for (j = 1; j <=t; j++)
{
scanf("%d", &n);
for (i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (i = 1; i <= n; i++)
scanf("%d", &p[i]);
scanf("%d", &nt);
for (i = 1; i <= n; i++)
{
scanf("%d", &z);
if (z == 1)
{
for (j = 1; j <= n; j++)
b[p[j]] = a[j];
for (j = 1; j <= n; j++)
a[j] = b[j];
}
if (z == 2)
{
scanf("%d", &x);
scanf("%d", &y);
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
if (z == 3)
{
scanf("%d", &l);
printf("%d",a[l]);
}
}
}
return 0;
}

For anyone finding it hard to understand the editorial, refer to the following video to understand permutation cycles first. It helps a lot.