Cool problem continuation on cyclic swaps in a permutation

Правка en1, от StellarSpecter, 2024-10-26 05:30:56

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!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский StellarSpecter 2024-10-26 05:30:56 1061 Initial revision (published)