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

By R.A.N.K.A., history, 3 years ago, In English

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

Please help and thanks in advance.

  • Vote: I like it
  • +6
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

look at cycle decomposition of P

»
3 years ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

In sample test case 1

there were two cycles

first -> [3 2] -> solved in one operation

Second -> [5 6 7 4] -> solved in two operations

In sample test case 2

there were two cycles

first -> [2 3 1] -> Cannot be solved [-1]

Second -> [5 6 7 4] -> solved in two operations

I 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 happening

Correct me if I am wrong.

Thank you.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seeing it in group theory terms (algebraically? "P^2") makes it easier to visualise for me. Thank you!~

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Bruh can u please tell the reference for this visualisation. I mean It is kind hard for me to prove the above .I don't want formal proof but intuition is also fine.I will be very thankful to you.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please provide pseudocode for above explaination???

  • »
    »
    3 years ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    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…

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      here cycle length is 2 not 4. Cycle 1: 4-1, Cycle 2: 2-3