TRPLSRT - Editorial

Practice
Div-2 Contest
Div-1 Contest

Author: Miloš Purić
Tester: Danya Smelskiy
Editorialist: Miloš Purić

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Math, Knowledge about permutation groups, Invariants

PROBLEM:

Given a permutation p of length n, find a way to sort it using at most \left \lfloor{\frac{n}{2}}\right \rfloor cyclical shifts of length 3.

QUICK EXPLANATION:

We have to find a sequence of swaps to sort the permutation. If the permutation is odd, it is not possible to sort it. Let’s process the swaps from the sequence two by two. If the current two swaps are from the same cycle, we can replace them with a single shift, otherwise we can perform two shifts. If we sort the cycles so that the ones of odd length come first, we will never use more than \left \lfloor{\frac{n}{2}}\right \rfloor operations.

EXPLANATION:

We’ll refer to our operation on indices i, j, k as shift(i,j,k) and to a regular swap on indices i, j as swap(i,j). Let’s try to decompose a shift into regular swaps of two indices.

\textbf{Observation 1}: A shift(i,j,k) is equivalent to performing two swaps swap(i,j), swap(i,k) in that order (we swap the elements on those indices, rather than the indices themselves).

It can be shown that the parity of the permutation (i.e. the parity of the number of inversions) changes after a single swap has been made.

Proof 1

Let’s swap the numbers on two different indices i and j within a permutation of length n. We’ll prove that the parity of the number of inversions in this permutation changes.

The following inversions will remain after the swap: (k,i) where k<i, (i,k) where j<k, (k,j) where k<i and (j,k) where j<k.

Therefore, if we denote x as the count of numbers greater than p_i in the range (i,j) , y as the count of numbers less than p_j in the range (i,j) and a as the number of inversions before the swap had been made, the number of inversions b after the swap will be:

b=a-((j-i+1)-x)-((j-i+1)-y)+x+y\pm1=a-2(j-i+1-x-y)\pm1

We add \pm1 because the pair (i,j) will either become an inversion or be one no longer. From this we infer b \not\equiv a \pmod 2, so the parity of the permutation has indeed changed.


Since a shift is equivalent to two regular swaps, we conclude that after performing a single shift the parity of the permutation does not change. Hence, if the parity of the given permutation is odd, we can never sort it using the given operation. From now on we consider only even permutations.

Let’s find all the cycles of the given permutation. For a cycle of length l (a cycle that contains l indices) we need l-1 swaps to sort it, so we characterize every cycle as a list of cycle size-1 swaps. Note that within a single cycle the first index in every swap is the same, so each cycle is represented by a list of this form:

(x,y_1),(x,y_2),…,(x,y_{cyclesize-1})

Using \textit{Observation 1} we can replace two swaps (x,y),(x,z) with a single shift(x,y,z). If a cycle is of odd size, we need an even number of swaps to sort it, so we replace two consecutive swaps (x,y_{2i-1}),(x,y_{2i}) with a single shift(x,y_{2i-1},y_{2i}) for each 1 \leq i \leq \frac{cyclesize-1}{2} . But, if a certain cycle is of even length, then a problem arises. We have to deal with a list of an odd number of swaps, and one will be left after we process the first cyclesize-2 swaps. The following observation comes in handy when dealing with that swap.

\textbf{Observation 2}: Two regular swaps swap(i,j),swap(k,l) are equivalent to shift(i,j,l), shift(k,l,i) in the given order if i,j,k,l are pairwise distinct indices.

Here is a sketch for better understanding:

We can apply this to the swap we are left with and the first swap of the next cycle, as all the indices in them are different (they belong to different cycles). In consequence, if we are left with only one swap in a cycle, we can do it together with the first swap of the next cycle using 2 operations, and handle the next cycle without the first swap. The ‘next’ cycle will undoubtedly exist owing to the total number of swaps being even (we consider only even permutations).

However, this solution is not sufficient. There are permutations for which this solution exceeds the limit for number of operations significantly. There is an interesting proof on the upper bound of the operations it uses.

Proof 2

It can be shown that this solution uses at most \left \lfloor{\frac{2n}{3}}\right \rfloor operations.

Let f_{x,c} be the maximum number of operations this solution can use if the permutation has c cycles (we count those of length 1 too) and x=n-c (the length of the sequence of swaps, where n is the length of the permutation). Note that we consider only even x ’s because the permutation has to be even.

We can write f_{x,c} in terms of previous f ’s by considering the length of the last cycle. If the last cycle was of even length then we go to f_{x-2y,c-1} by using y operations.

If the last cycle was of odd length then we go to f_{x-2y-2,c-1} by using y+2 operations, because we have to do to the last swap of the second to last cycle with the first swap of the last cycle. In this case, we can also go to f_{x-2y-2,c-2} if we wish for the second to last cycle to have length 1. However, f_{a,b} \geq f_{a,b-1} is obviously true for all a and b \geq 1 so we can omit this.

Thus, the following recurrent relation holds true:

f_{x,c}=\max(\max\limits_{1 \leq y \leq \frac{x}{2}} (f_{x-2y,c-1}+y), \max\limits_{1 \leq 2y+1 < x} (f_{x-2y-2,c-1}+y+2)), with f_{0,c}=0

This expression can be rewritten in the following way (we omit the base values f_{0,c} for clarity):

f_{x,c}=\max\limits_{1 \leq y \leq \frac{x}{2}} (\max(f_{x-2y,c-1}+y,f_{x-2y,c-1}+y+1))

The second term is obviously always bigger so:

f_{x,c}=\max\limits_{1 \leq y \leq \frac{x}{2}} (f_{x-2y,c-1}+y+1)

We will now prove that f_{x,c} \leq \frac{2(x+c)}{3} for every x \geq 1 and c \geq 1 by induction on the number of cycles c.

\textbf{Base case:} f_{x,1}=\frac{x}{2} \leq \frac{2(x+1)}{3}

\textbf{Inductive step:} From the above reasoning, derived from the definition:

f_{x,c}=\max\limits_{1 \leq y \leq \frac{x}{2}} (f_{x-2y,c-1}+y+1)

By the inductive hypothesis f_{a,c-1} \leq \frac{2(a+c-1)}{3} for all a \geq 1. Thus:

f_{x,c} \leq \max\limits_{1 \leq y \leq \frac{x}{2}} (\frac{2(x-2y+c-1)}{3}+y+1)=
=\max\limits_{1 \leq y \leq \frac{x}{2}} (\frac{2x+2c-y+1}{3})=\frac{2x+2c-1+1}{3}=\frac{2(x+c)}{3}

This shows that the statement is correct for all f's with c cycles, so the step is over.

Hence, f_{x,c} \leq \frac{2(x+c)}{3} is true for all x \geq 1 and c \geq 1.

Since n=x+c, then O \leq \frac{2n}{3} (i.e. O \leq \left \lfloor{\frac{2n}{3}}\right \rfloor) for every permutation of length n. Equality can be reached by tracing back the values of f.


To optimize it we need to consider the fact that the order of processing the cycles does not matter. We will sort all cycles so that we first process all the cycles for which we need an even number of swaps (cycles of odd size) and then all the cycles for which we need an odd number of swaps (cycles of even size). We can prove that by processing cycles in this manner we never use more than \left \lfloor{\frac{n}{2}}\right \rfloor operations.


Proof 3

Let c_e,c_o be the number of even cycles and odd cycles respectively, e_i,o_i be the size of the i-th even and i-th odd cycle respectively, l_e,l_o be the total length of all even and odd cycles (i.e. the sum of sizes of all even and odd cycles) respectively.

For processing all the cycles of odd length (each of them requires an even number of swaps) we need a operations where:

a=\frac{\sum_{i=1}^{c_o} (o_i-1)}{2}=\frac{l_o-c_o}{2}

The number of cycles of even length must be even (since each of them requires an odd number of swaps). For every two adjacent cycles of even length we will do the last swap of the first cycle with the first swap of the second cycle using 2 operations. Taking that into account, for processing all the cycles of even length we need b operations where:

b=\frac{(\sum_{i=1}^{c_e} e_i-1)-c_e}{2}+c_e=\frac{l_e-2c_e}{2}+c_e=\frac{l_e}{2}

Summing these two up, we get that the total number of operations O is:

O=a+b=\frac{l_o-c_o+l_e}{2}=\frac{n-c_o}{2}

From this we see that O \leq \frac{n}{2} and so O \leq \left \lfloor{\frac{n}{2}}\right \rfloor. The equality can be achieved when all cycles are of even length (i.e. c_o=0).


IMPLEMENTATION NOTES:

Representing the permutation as a product of transpositions quickly (i.e. extracting all the swaps that need to be made) may be the first somewhat troubling part in case you have never done it before. It is usually being implemented in the following way:

ListOfTranspositions #an empty list of pairs - transpositions
for i = 1 . . . n:
    while(a[i] != i) 
       #the element currently standing on position i should go to position a[i]
       ListOfTranspositions.append({i,a[i]}) #add the transposition from i to a[i]
       swap(a[i],a[a[i]]) #swap the corresponding values on those indices

From the fact that the parity of the permutation changes after a single swap has been made (see Proof 1), it follows that the parity of the permutation is the same as the parity of the number of transpositions in it’s representation. Consequently, we can just check if the length of the ListOfTranspositions is odd and output -1 if that is the case.

In order to be able to sort the cycles according the parity of their length, we need to create a separate list for each cycle and store each transposition in the list of the cycle it belongs to. We can achieve that by modifying the code above:

ListOfListsOfTranspositions #an empty list of lists
for i = 1 . . . n:
    ListOfTranspositions #an empty list of pairs - transpositions
    while(a[i] != i) 
       #the element currently standing on position i should go to position a[i]
       ListOfTranspositions.append({i,a[i]}) #add the transposition from i to a[i]
       swap(a[i],a[a[i]]) #swap the corresponding values on those indices
    ListOfListsOfTranspositions.append(ListOfTranspositions)
sort(ListOfListsOfTranspositions) #sort the cycles according to their parity

Now it only remains to construct the solution by traversing the transpositions and grouping them two by two as described, in the order they are given in the ListOfListsOfTranspositions.

The time complexity of this solution is O(n \log n) and the memory complexity is O(n). The time complexity would have been O(n) if we had used counting sort for sorting the cycles.

REMARKS:

If you are not familiar with the basic terms in permutation groups, I suggest you take a look at
this article as an introduction to permutation groups with some more interesting results. Wikipedia’s articles on permutation groups and symmetric groups, which are closely related in the field of group theory, are also quite nicely written.

Problems in permutation groups and their solutions have applications in fields like bioinformatics, for example, sorting of genomic sequences. Some more applications have been pointed out in this article, which I encourage you to take a look at.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> p;
typedef pair <p,int> t;
const int N = 2e5+23;

int a[N],b[N];
vector <vector<p>> cycles; /// all the cycles are stored here (actually the swaps that are needed to sort them)
vector <p> swaps;
vector <t> sol;

void op(int i,int j,int k){
    sol.push_back(t(p(i,j),k));
}

void solve(){
    cycles.clear();
    swaps.clear();
    sol.clear();
    int n,k,parity = 0;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
    }
    vector <vector<p>> oddcycles; /// we'll put all cycles of odd length here
    for(int i = 1; i <= n; i++){ /// now we single out the cycles
        vector <p> v;
        while(a[i] != i){ /// a[i] is the position where the element currently on position i should go
            v.push_back(p(i,a[i])); /// add this swap
            parity++;
            swap(a[i],a[a[i]]);
        }
        if(v.size()){
            if(v.size()%2 == 0){ /// if this cycle is of even size put it into cycles
                cycles.push_back(v);
            }
            else{ /// if it is of odd size put it here
                oddcycles.push_back(v);
            }
        }
    }
    for(int i = 0; i < oddcycles.size(); i++){ /// then add all the odd length cycles to the back so that all the cycles are sorted according to their parity
        cycles.push_back(oddcycles[i]);
    }
    if(parity%2 == 1){ /// if the permutation is odd it is impossible to sort it using given operations
        cout << "-1\n";
        return;
    }
    if(n == 3){ /// base cases, probably not needed
        if(b[1] == 1){
            cout << "0\n";
        }
        else if(b[1] == 2){
            cout << "1\n";
            cout << "1 2 3\n";
        }
        else{
            cout << "1\n";
            cout << "1 3 2\n";
        }
        return;
    }
    for(auto f : cycles){ /// from now on we just need the whole list of swaps, that is the vector 'swaps'
        for(auto g : f){
            if(g.first > g.second){
                swap(g.first,g.second);
            }
            swaps.push_back(g);
        }
    }
    for(int x = 0; x < swaps.size(); x += 2){ /// we process the swaps two by two
        p f = swaps[x],g = swaps[x+1];
        int i1 = f.first,j1 = f.second,i2 = g.first,j2 = g.second;
        if(i1 > j1){
            swap(i1,j1);
        }
        if(i2 > j2){
            swap(i2,j2);
        }
        /// if any two indices are equal then these two swaps belong to the same cycle and we can do them using one operation
        if(i1 == i2){
            op(i1,j1,j2);
            continue;
        }
        if(j1 == j2){
            op(j1,i1,i2);
            continue;
        }
        if(i1 == j2){
            op(i1,j1,i2);
            continue;
        }
        if(i2 == j1){
            op(j1,i1,j2);
            continue;
        }
        /// otherwise we have four different indices i1,j1,i2,j2 and we can do them together using two operations
        op(i1,j1,j2);
        op(i2,j2,i1);
    }
    cout << sol.size() << "\n";
    for(auto f : sol){
        cout << f.first.first << " " << f.first.second << " " << f.second << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    /*freopen("tst.txt","r",stdin);
    freopen("output.txt","w",stdout);*/
    int te;
    cin >> te;
    while(te--){
        solve();
    }
}
Tester's Solution
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

const int N = 200'005;


int n, k;
int p[N];
bool used[N];

void solve(int test_id) {
    vector<pair<int, int>> two_node_cycles;
    vector<tuple<int, int, int>> answer;

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; ++i) {
        used[i] = false;
    }
    for (int i = 1; i <= n; ++i) if (!used[i]) {
        vector<int> cycle;
        int j = i;
        while (!used[j]) {
            used[j] = true;
            cycle.push_back(j);
            j = p[j];
        }
        while (cycle.size() > 2) {
            // x -> y -> z -> x
            int z = cycle.back();
            cycle.pop_back();
            int y = cycle.back();
            cycle.pop_back();
            int x = cycle.back();
            if (cycle.size() == 1)
                cycle.pop_back();
            answer.push_back(tie(x, y, z));
            --k;
        }
        if (cycle.size() == 2) {
            two_node_cycles.push_back(make_pair(cycle[0], cycle[1]));
        }
    }
    while (two_node_cycles.size() > 1) {
        // a -> b -> a,
        // c -> d -> c
        pair<int, int> fir = two_node_cycles.back();
        two_node_cycles.pop_back();
        pair<int, int> sec = two_node_cycles.back();
        two_node_cycles.pop_back();
        // b -> c -> d
        // a -> b -> c
        answer.push_back(tie(fir.second, sec.first, sec.second));
        answer.push_back(tie(fir.first, fir.second, sec.first));
        k -= 2;
    }
    if (!two_node_cycles.empty()) {
        k = -1;
    }
    if (k < 0) {
        cout << "-1\n";
    } else {
        cout << answer.size() << '\n';
        for (int i = 0; i < answer.size(); ++i) {
            cout << get<0>(answer[i]) << " "
                 << get<1>(answer[i]) << " "
                 << get<2>(answer[i]) << '\n';
        }
    }
    return;
}

int main(int argc, const char * argv[]) {
    #ifdef __APPLE__
        freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int tests;
    cin >> tests;
    for (int i = 0; i < tests; ++i) {
        solve(i);
    }   
    return 0;
}
19 Likes

@admin It would add more value to the Editorial as well as beginner if a Short Video description(Hope that won't take much time) can be provided for each Problems as it helps in more understanding of the problem and concepts.
Thanks. :blush:

64 Likes

Please join [Official] May Long 2020 - Post-contest discussion - Live stream session :slight_smile: And if you can’t make it, it’ll be uploaded to youtube after the stream is over.

5 Likes

I tried but the last 2 cases always showed WA. Can anyone tell me what went wrong?
submission - CodeChef: Practical coding for everyone

1 Like

i just did those operation first in which we can get two elements into its correct place and then traversed again for leftover to do operation to get an element into its correct position but this editorial is great!
https://www.codechef.com/viewsolution/32962801

2 Likes

@admin Sure I will But It sometimes becomes quite long discussion there as that will be platform for all the DOUBT CLEARANCE ,But what I was suggesting to provide a Short Video Description(maybe around 5-10 min) explaining the core idea of problem In Post discussion what I observed is , in

ZOOM discussion makes it quite lengthy

and so many doubts handling go along the Explanation.

A proper well explained short Video will add more information to the Editorial and new Coders.

Thanks

10 Likes

@csk111165 Completely agreed to you!

3 Likes

Hi guys, I have done this question using Graph. If anyone wants to see the implementation then please have a look at this.

2 Likes

can you please explain your approach. :slight_smile:

1 Like

I was able to solve only first two problems…Can anyone suggest which problems to practice to get better?

2 Likes

@admin please upload it on youtube.

Hi Anurag, Here is my algorithm using graph. There are 3-types of operations as follows:

1. Operations, in which all the 3 elements comes to their right positions in single operation.
2. Then those operations in which 2 elements can be placed at their right position in single operations.
3. At the end, last type of operations are those in which 1 element can be placed in right position in single operation.

Using the concept of these operations i have written the code.

completely agreed with you

https://www.codechef.com/viewsolution/32623512
here is my solution …
i was just trying to put i at its correct place, nothing much :slight_smile:
It passed …

@losmi247 could you explain this with an example pls

1 Like

i dont understand this
> If the permutation is odd, it is not possible to sort it.
Can anyone pls explain.

1 Like

Guys you can refer to my solution here. Its pretty simple to understand.

2 Likes

Its got to do with the fact that even + even is always even. The operation we are allowed to do acts as an even number. If the original permutation is odd, then we can never reach the identity permutation(think of this like 0, which is even).

Before your actual code starts i.e. on the unmodified input array, just once do a cyclic shift on all the triplets that you can obtain directly viz. i, j=a[i] and k=a[a[i]]. Don’t forget to count it.

Can somebody please have a look at my code and tell me where I went wrong??
Please it would help a lot!!
https://www.codechef.com/viewsolution/32923428

and I have a doubt, assume this sequence 7 3 5 4 2 1 6
this is odd but we can still sort this!!!