R.A.N.K.A.'s blog

By R.A.N.K.A., history, 20 months ago,

Problem statement — Permutation is called stable if P[i]=i for every i

We are given Permutation we want to tell in how many moves we can make this permutation stable or print -1 if not possible to make permutation stable.

in one move we can do operation : — P[i] = P[P[i]]

Sample TestCase
7
[1 3 2 5 6 7 4]
Output  - > 2

[1 3 2 5 6 7 4] -> [1 2 3 6 7 4 5] -> [1 2 3 4 5 6 7]

Sample TestCase
7
[2 3 1 5 6 7 4]
Output  - > -1



• +6

 » 20 months ago, # |   +8 look at cycle decomposition of P
 » 20 months ago, # | ← Rev. 3 →   +7 In sample test case 1there were two cyclesfirst -> [3 2] -> solved in one operationSecond -> [5 6 7 4] -> solved in two operationsIn sample test case 2there were two cyclesfirst -> [2 3 1] -> Cannot be solved [-1]Second -> [5 6 7 4] -> solved in two operationsI tried to generate permutation like above and found that if there is cycle whose length is power of 2 then answer is possible and answer is length/2 and for other cases we can't convert to stable permutation.I don't have any proof, it was just an observation.Please help or can anyone prove why this is happeningCorrect me if I am wrong.Thank you.
•  » » 20 months ago, # ^ |   +8 Whenever you apply the said operation, it breaks each cycle by two if it's even and it doesn't do anything if it's odd, just the order in the cycle changes. To reach the identity permutation, all cycles have to have 1 element. For this to hold each cycle has to have a power of 2.
•  » » 20 months ago, # ^ |   +17 It is correct. In group terms, every operation transforms P -> P^2, so any number of operations gives you P^(2^k) for some k. This can become the identity iff the order of P is a power of 2, iff every cycle is of size power of 2. Then the answer is log2(biggest cycle size).
•  » » » 20 months ago, # ^ |   0 Seeing it in group theory terms (algebraically? "P^2") makes it easier to visualise for me. Thank you!~
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you please provide pseudocode for above explaination???
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +3 sudo(super user do) code? do you mean pseudocode?
•  » » 8 months ago, # ^ | ← Rev. 4 →   +1 What is this operation? Is it “move number p[p[i]] to position i”? (Which will change all j for j >= i to j+1).Because it looks like assignment, but example shows that it is not. Is there some meaning in dash before assignment?PS. Damn, its a necropost…
•  » » 8 months ago, # ^ |   0 For n=4 P=[4 3 2 1]. cycle length is 4, but ans=1 (not 4/2=2) So answer won't be length/2(If I'm not wrong).
•  » » » 7 months ago, # ^ |   +3 here cycle length is 2 not 4. Cycle 1: 4-1, Cycle 2: 2-3
 » 8 months ago, # |   0 This forms a directed graph in the permutation. If in the directed graph, it is impossible for p[i] = i through some series of steps (or i doesn't exist in the path) then the answer is -1. Additionally, whenever you make P[i] = i, you delete the path between the node leading to P[i]. Therefore, in order for a valid arrangement to be possible, you must have a path where all the nodes are in disjoint cycles.