# How to solve permutation swaps in today cook off?

Could someone share the approach ? problem link

Use the property that permutations form a cycle. So, my approach was to find the inverse permutation C[i] such that B[i] = A_{C[i]}, C[i] can be found as C[P[i]] = i.
Now store all the cycles, all queries of type 1 are simple rotations. To answer query of type 2 and 3 first calculate the correct indices using number of rotations.
You can see my code. If you are unable to understand anything, feel free to ask.

4 Likes

I think you can solve it by dividing the permutation b into cycles and storing a count of number of type-1 queries, then for finding the array element at any index you can just return the A_i at the index j where j=(i+number \ of \ type-1 \ queries)\%cycle \ size

2 Likes

Yeah it can be solved in this way , link to my code

How do we handle swaps then? And wont’t then your approach give TLE?

now it won’t it’s just a constant time operation. Find the indices and swap the array elements…

Have a look on my code , just above your comment

how i can solve chef and subarray problem ? my solution you can find here https://www.codechef.com/viewsolution/46828687

I think you’ve linked the code for second problem

Yeah I edited it

Could you please take an example. That will clear my doubt fast

WLOG, Sharing an example with array A elements >= n for clarity

A: 6 7 8 9 10
P: 5 1 4 3 2

Here, cycles are (2 5 1) ( 3 4). i.e. observe how element at position 2 changes after multiple type 1 operations.

Iter 1: 7 10 9 8 10
Iter 2: 10 6 8 9 7
Iter 3: 6 7 9 8 10

Notice how element at position two changes: 7 ( Initial Idx 2 ) → 10 ( Initial Idx 5 ) → 6 ( Initial Idx 1 ) → 7 ( Initial Idx 2 )

We can use this property of cycles to figure out which element will be present at the target idx after a set of type 1 operations.

1 Like

I’ll explain with sample only. The permutation is P = [2, 3, 1] and A = [1, 2, 3]. The inverse permutation can be calculated using C[P[i]] = i, so we get C = [3, 1, 2]. Now note that this permutation C has cycle (1 -> 3 -> 2 -> 1). This cycle has a length of 3. We can store all the cycles. In my code, I am storing cycles in comp[l].
Now let’s talk about query, we have query of type 1, so we increment a variable ones by 1.
Next we need to swap 2 and 3. But remember that we need to rotate 2 and 3 by ones. Looking at permutation cycle of C, we have 2 -> 1, 3 -> 2. So in original array A, we need to swap A and A. So array becomes [2, 1, 3].
Next query was type 3 with index as 1. So rotating by ones in the permutation we have 1 -> 3. We then output A = 3.
To rotate in O(1), we can use length of cycles.
Is it clear now?

2 Likes

I did by binary lifting kind of thing, just calculated which element will where after 2 ^i shifts, then for each query position of element after j shifts can be found in log n time

1 Like

Yes it’s clear . Thanks to you and @arijitiit for example.

Can you please share your code . I also tried the same way but getting WA! Neat

struct lift

{

``````vector<vector<int>> next;

int delta;

lift(int n, int *b)

{

delta = 0;

next = vector<vector<int>>(18, vector<int>(n));

for (int i = 0; i < n; i++)

{

next[b[i] - 1] = i;

}

for (int i = 1; i < 18; i++)

{

for (int j = 0; j < n; j++)

{

next[i][j] = next[i - 1][next[i - 1][j]];

}

}

}

int get(int ret)

{

for (int j = 0; j < 18; j++)

{

if (delta & (1 << j))

{

ret = next[j][ret];

}

}

return ret;

}
``````

};

void solve()

{

``````int n;

cin >> n;

int a[n];

int b[n];

for (int i = 0; i < n; i++)

{

cin >> a[i];

}

for (int j = 0; j < n; j++)

{

cin >> b[j];

}

lift d(n, b);

int q;

cin >> q;

while (q--)

{

int x;

cin >> x;

if (x == 1)

{

d.delta++;

}

else if (x == 2)

{

int y, z;

cin >> y >> z;

y--;

z--;

y = d.get(y);

z = d.get(z);

swap(a[y], a[z]);

}

else

{

int y;

cin >> y;

y--;

y = d.get(y);

cout << a[y] << "\n";

}

}
``````

}