Problem with permutations
Difference between en1 and en2, changed 46 character(s)
The input consists of natural number N and M (N <= 2*10^5 and M < N). \n
Then you are given a permutation of numbers [1, N]
 \n
You should sort the given array, but only the following operation is allowed:
 \n
Chose a number with index from [0, M-1] and  choose a number from [M, N-1], then swap then.
 \n
What is the minimum number of operations to sort the array?
 \n
Example:
 \n
5 3
 \n
1 2 3 5 4

---------
 \n
1 2 5 3 4 (swap 3 and 5)
 \n
1 2 4 3 5 (swap 4 and 5)
 \n
[1 2 3 4 5] (swap 3 and 4, now the array is sorted, total steps = 3)

 \n↵
\n

Any idea on how to solve this problem?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English VMaksimoski008 2023-06-26 19:38:50 6
en4 English VMaksimoski008 2023-06-26 18:37:02 65
en3 English VMaksimoski008 2023-06-26 18:34:54 68
en2 English VMaksimoski008 2023-06-26 18:32:34 46
en1 English VMaksimoski008 2023-06-26 18:31:20 580 Initial revision (published)