TRPLSRT - Editorial

editorial
, , , , , ,
5

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
6

@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
8

@csk111165 Completely agreed to you!

3 Likes
9

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
10

can you please explain your approach. :slight_smile:

1 Like
11

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

2 Likes
12

@admin please upload it on youtube.

13

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.

14

completely agreed with you

15

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 …

16

@losmi247 could you explain this with an example pls

1 Like
17

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

1 Like
18

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

2 Likes
19

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

20

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.

21

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

22

An odd permutation is one that can be reached by an odd number of two-element swaps.
This is not an odd permutation since it can be reached in four swaps.

1 2 3 4 5 6 7
6 2 3 4 5 1 7
7 2 3 4 5 1 6
7 3 2 4 5 1 6
7 3 5 4 2 1 6
3 Likes
23

oh I see, can you please review my code once??
I’ve tried a lot but I can’t find where my code is failing

24

I can’t figure out your exact approach. Can you just brief me?

25

Odd permutation means it has odd number of inversions.

refer to the above question

1 Like