# TRPLSRT - Editorial

**URL:** <https://discuss.codechef.com/t/trplsrt-editorial/63273>\
**Category:** editorial\
**Tags:** easy-medium, editorial, invariants, maths, permutation, may20, losmi247\
**Created:** [May 11, 2020, 9:30am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273 "2020-05-11T09:30:03Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![losmi247](https://discuss.codechef.com/user_avatar/discuss.codechef.com/losmi247/32/208155_2.png) [@losmi247](https://discuss.codechef.com/u/losmi247)\
**Post date:** [May 11, 2020, 9:30am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/1 "2020-05-11T09:30:03Z")

</div>

[Practice](https://www.codechef.com/problems/TRPLSRT)  
[Div-2 Contest](https://www.codechef.com/MAY20B/problems/TRPLSRT)  
[Div-1 Contest](https://www.codechef.com/MAY20A/problems/TRPLSRT)

_Author:_ [Miloš Purić](https://www.codechef.com/users/losmi247)  
_Tester:_ [Danya Smelskiy](https://www.codechef.com/users/smelskiy)  
_Editorialist:_ [Miloš Purić](https://www.codechef.com/users/losmi247)

# 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:

 ![image1](https://s3.amazonaws.com/discourseproduction/original/2X/2/2703fdd738ddc8f8a9524e288b4c4cd7e9476757.png)

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:

```auto
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:

```auto
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](http://sites.millersville.edu/bikenaga/abstract-algebra-1/permutations/permutations.pdf) as an introduction to permutation groups with some more interesting results. Wikipedia’s articles on [permutation groups](https://en.wikipedia.org/wiki/Permutation_group) and [symmetric groups](https://en.wikipedia.org/wiki/Symmetric_group), 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](https://arxiv.org/pdf/1007.4236.pdf), 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;
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![csk111165](https://discuss.codechef.com/user_avatar/discuss.codechef.com/csk111165/32/53994_2.png) [@csk111165](https://discuss.codechef.com/u/csk111165)\
**Post date:** [May 11, 2020, 9:52am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/2 "2020-05-11T09:52:29Z")

</div>

@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. 😊

---

<div class="post-metadata">

**Author:** ![admin](https://discuss.codechef.com/user_avatar/discuss.codechef.com/admin/32/212587_2.png) [@admin](https://discuss.codechef.com/u/admin)\
**Post date:** [May 11, 2020, 9:55am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/3 "2020-05-11T09:55:50Z")

</div>

Please join [[Official] May Long 2020 - Post-contest discussion - Live stream session](https://discuss.codechef.com/t/official-may-long-2020-post-contest-discussion-live-stream-session/64377) 🙂 And if you can’t make it, it’ll be uploaded to youtube after the stream is over.

---

<div class="post-metadata">

**Author:** ![sub\_coder1](https://discuss.codechef.com/user_avatar/discuss.codechef.com/sub_coder1/32/15425_2.png) [@sub\_coder1](https://discuss.codechef.com/u/sub_coder1)\
**Post date:** [May 11, 2020, 10:23am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/4 "2020-05-11T10:23:38Z")

</div>

I tried but the last 2 cases always showed WA. Can anyone tell me what went wrong?  
submission - [CodeChef: Practical coding for everyone](https://www.codechef.com/viewsolution/32830895)

---

<div class="post-metadata">

**Author:** ![manrajx](https://discuss.codechef.com/user_avatar/discuss.codechef.com/manrajx/32/26283_2.png) [@manrajx](https://discuss.codechef.com/u/manrajx)\
**Post date:** [May 11, 2020, 10:25am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/5 "2020-05-11T10:25:43Z")

</div>

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](https://www.codechef.com/viewsolution/32962801)

---

<div class="post-metadata">

**Author:** ![csk111165](https://discuss.codechef.com/user_avatar/discuss.codechef.com/csk111165/32/53994_2.png) [@csk111165](https://discuss.codechef.com/u/csk111165)\
**Post date:** [May 11, 2020, 10:34am UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/6 "2020-05-11T10:34:15Z")

</div>

@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

---

<div class="post-metadata">

**Author:** ![mohit827](https://discuss.codechef.com/user_avatar/discuss.codechef.com/mohit827/32/3653_2.png) [@mohit827](https://discuss.codechef.com/u/mohit827)\
**Post date:** [May 11, 2020, 12:00pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/8 "2020-05-11T12:00:12Z")

</div>

@csk111165 Completely agreed to you!

---

<div class="post-metadata">

**Author:** ![shubham\_169](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@shubham\_169](https://discuss.codechef.com/u/shubham_169)\
**Post date:** [May 11, 2020, 1:10pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/9 "2020-05-11T13:10:59Z")

</div>

Hi guys, I have done this question using Graph. If anyone wants to see the implementation then please have a look at [this.](https://www.codechef.com/viewsolution/32941960)

---

<div class="post-metadata">

**Author:** ![anurag\_bhatt](https://discuss.codechef.com/user_avatar/discuss.codechef.com/anurag_bhatt/32/50934_2.png) [@anurag\_bhatt](https://discuss.codechef.com/u/anurag_bhatt)\
**Post date:** [May 11, 2020, 1:36pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/10 "2020-05-11T13:36:59Z")

</div>

can you please explain your approach. 🙂

---

<div class="post-metadata">

**Author:** ![gyan\_p\_t](https://discuss.codechef.com/user_avatar/discuss.codechef.com/gyan_p_t/32/3653_2.png) [@gyan\_p\_t](https://discuss.codechef.com/u/gyan_p_t)\
**Post date:** [May 11, 2020, 1:39pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/11 "2020-05-11T13:39:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![prateek\_111](https://discuss.codechef.com/user_avatar/discuss.codechef.com/prateek_111/32/3653_2.png) [@prateek\_111](https://discuss.codechef.com/u/prateek_111)\
**Post date:** [May 11, 2020, 2:47pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/12 "2020-05-11T14:47:03Z")

</div>

@admin please upload it on youtube.

---

<div class="post-metadata">

**Author:** ![shubham\_169](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@shubham\_169](https://discuss.codechef.com/u/shubham_169)\
**Post date:** [May 11, 2020, 2:51pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/13 "2020-05-11T14:51:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![samay\_kam\_hai](https://discuss.codechef.com/user_avatar/discuss.codechef.com/samay_kam_hai/32/49851_2.png) [@samay\_kam\_hai](https://discuss.codechef.com/u/samay_kam_hai)\
**Post date:** [May 11, 2020, 4:02pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/14 "2020-05-11T16:02:23Z")

</div>

completely agreed with you

---

<div class="post-metadata">

**Author:** ![manishkheta321](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@manishkheta321](https://discuss.codechef.com/u/manishkheta321)\
**Post date:** [May 11, 2020, 4:14pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/15 "2020-05-11T16:14:48Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![souravishan](https://discuss.codechef.com/user_avatar/discuss.codechef.com/souravishan/32/9084_2.png) [@souravishan](https://discuss.codechef.com/u/souravishan)\
**Post date:** [May 11, 2020, 5:25pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/16 "2020-05-11T17:25:22Z")

</div>

> [@losmi247](#):
>
> The following inversions will remain after the swap: (k,i)(k,i)(k,i) where k\<ik\<ik\<i, (i,k)(i,k)(i,k) where j\<kj\<kj\<k, (k,j)(k,j)(k,j) where k\<ik\<ik\<i and (j,k)(j,k)(j,k) where j\<kj\<kj\<k.

@losmi247 could you explain this with an example pls

---

<div class="post-metadata">

**Author:** ![its\_boring](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@its\_boring](https://discuss.codechef.com/u/its_boring)\
**Post date:** [May 11, 2020, 5:29pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/17 "2020-05-11T17:29:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![udayan14](https://discuss.codechef.com/user_avatar/discuss.codechef.com/udayan14/32/238262_2.png) [@udayan14](https://discuss.codechef.com/u/udayan14)\
**Post date:** [May 11, 2020, 5:35pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/18 "2020-05-11T17:35:35Z")

</div>

Guys you can refer to my solution [here](https://www.codechef.com/viewsolution/32754294). Its pretty simple to understand.

---

<div class="post-metadata">

**Author:** ![udayan14](https://discuss.codechef.com/user_avatar/discuss.codechef.com/udayan14/32/238262_2.png) [@udayan14](https://discuss.codechef.com/u/udayan14)\
**Post date:** [May 11, 2020, 5:39pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/19 "2020-05-11T17:39:05Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![manishsemwal](https://discuss.codechef.com/user_avatar/discuss.codechef.com/manishsemwal/32/324460_2.png) [@manishsemwal](https://discuss.codechef.com/u/manishsemwal)\
**Post date:** [May 11, 2020, 5:39pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/20 "2020-05-11T17:39:41Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![chiragxarora](https://discuss.codechef.com/user_avatar/discuss.codechef.com/chiragxarora/32/3653_2.png) [@chiragxarora](https://discuss.codechef.com/u/chiragxarora)\
**Post date:** [May 11, 2020, 5:53pm UTC](https://discuss.codechef.com/t/trplsrt-editorial/63273/21 "2020-05-11T17:53:14Z")

</div>

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](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!!!

[Next page](https://discuss.codechef.com/t/trplsrt-editorial/63273.md?page=2)