zodzeos's blog

By zodzeos, 5 years ago, In English,

Given, two integers, M and R and an array of size M*R, containing R positions with value 0 and the remaining positions with values in the interval [1,M*R-R] without repetitions, you need to answer the minimum number of swaps in the array to transform it in an array where the positions of the array that are multiples of M should be filled by 0 values and the non zero values are sorted.

For example, given the input:
4 2
0 1 2 3 0 4 5 6

the minimum number of swaps is 6:
1 2
2 3
3 4
5 6
6 7
7 8

The limits for the problem are:
(1 ≤ M, R ≤ 100,000, 1 ≤ M * R ≤ 100,000)

Could anyone help me to solve this problem?

Read more »

 
 
 
 
  • Vote: I like it
  • -7
  • Vote: I do not like it