Блог пользователя Nams

Автор Nams, история, 9 лет назад, По-английски

Hello All,

I came across this interesting question in which there is an array consisting of n numbers with each number lying between 1 to m. Now it is asked to find the minimum number of swaps necessary to reformat the array such that the array elements with same value come together.

Note: Here Here swap means exchanging position of two adjacent numbers.

Example: If N=4 && M=2 && A[4]=1 2 1 2 => Ans=1

If N=6 && M=4 && A[6]=2 1 4 3 1 2 => Ans=6

Constraints: 1<=N<=10^5 && 1<=M<=16

I have been able to find that this question can be solved using DP+bitmasking but I am facing difficulty in forming the DP structure. So if anybody can help,it will be really grateful.

Thanks

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

does it have any online judge?? where have you seen it?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone suggest any other algorithm if not Dp+Bitmask that may be used to solve this problem?