PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Ashish Kumar
Tester: Istvan Nagy
Editorialist: Taranpreet Singh
DIFFICULTY
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 READ(f) freopen(f, "r", stdin)
#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) {
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, ' ');
}
int main(int argc, char** argv)
{
#ifdef HOME
if(IsDebuggerPresent())
{
freopen("../P7SWAPS_8.in", "rb", stdin);
freopen("../out.txt", "wb", stdout);
}
#endif
int T;
T = readIntLn(1, 1000);
int sumN = 0;
int sumQ = 0;
forn(tc, T)
{
int N = readIntLn(1, 100'000);
vector<bool> au(N);
sumN += N;
vector<int> A(N), P(N);
int ctr = 0;
for (auto& ai : A)
{
if (++ctr == N)
ai = readIntLn(1, N);
else
ai = readIntSp(1, N);
assert(ai > 0 && ai <= N);
assert(!au[ai]);
au[ai] = true;
}
ctr = 0;
vector<bool> pu(N);
for (auto& pi : P)
{
if (++ctr == N)
pi = readIntLn(1, N);
else
pi = readIntSp(1, N);
--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);
}
int Q = readIntLn(1, 100000);
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:
readStringLn(0, 0);
++permCounter;
break;
case 2:
{
readStringSp(0, 0);
int pos1 = readIntSp(1, N);
int pos2 = readIntLn(1, N);
assert(pos1 != pos2);
--pos1, --pos2;
int origPos1 = calcPos(pos1);
int origPos2 = calcPos(pos2);
swap(A[origPos1], A[origPos2]);
break;
}
case 3:
{
readStringSp(0, 0);
int pos = readIntLn(1, N);
--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[0][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;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
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());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 
