We all know, any permutation is made up of disjoint set of cyclic swaps. Read more about it here
i.e to make the permutation sorted, we need to do k-1 swaps for each k sized cycle.
Total swaps => n — number of cycles.
A variation of this standard problem was asked in the recent Div.3 2033E - Sakurako, Kosuke, and the Permutation,
We have to make the permutation such that either p[i] = i OR p[p[i]] = i ,
interestingly, solution to this comes as k/2-1 for each k sized cycle.
Now it makes me wonder what if we introduce one more condition to it =>
either p[i] = i OR p[p[i]] = i OR p[p[p[i]] = i
What would the answer be ? my intuition tells me it should be something in the order of k/6 for a cycle k.
Can you guys help me with this ?
Also what would be the general answer if we have m conditions like this,
either p[i] = i OR .... .... .... OR p[p[p[p[p[...i]....] = i .
Any help would be appreciated, Thanks!
i think it should be (n-m+1)/m for general case of m conditions.
i doubt
Given a k-cycle, you can split it into a i-cycle (i<k) and (k-i)-cycle in one swap. just swap k and i
So the answer would be ceil(k/m)-1 or (k+m-1)//m -1 = (k-1)//m
If you are instead given a subset of {1,2,...n}, it will become a dp problem, equivalent to the simple change-making problem