By madver, history, 6 months ago, ,

Hello everybody. Today, i hope you can help me to solve this problem. I have many ways to solve it if the array has distinct integers. But if the array has repeated elements, i think it is very hard. Can anyone give me some advice ?

•
• +8
•

 » 6 months ago, # |   0 Haven't put much thought on this, but my guess would be n - k, where n is the size of the array and k is the value of longest not decreasing subsequence.
•  » » 6 months ago, # ^ |   +5 for test 2 3 4 ... n 1you would return 1 instead of n — 1
•  » » » 6 months ago, # ^ |   0 Sure! Got it wrong. I think the problem it solves is when you are able to change the position of a element instead of swapping two. Any counter examples for this problem?
 » 6 months ago, # |   +8 If you have several equal elements you will never make a swap between them, so you can replace each element with the tuple (ai, i). Notice that now all elements are distinct (and solving this problem is equivalent to solve the previous) and you can do whatever algo you know to solve this.
•  » » 6 months ago, # ^ |   0 Would it work for the sequence 1 3 2 2?
•  » » » 6 months ago, # ^ |   0 Of course. You need to sort the array: [(1, 1);(3, 2);(2, 3);(2, 4)]The sorted version will be: [(1, 1);(2, 3);(2, 4);(3, 2)]Notice when comparing tuple we first compare first element, and in case they differ we compare the second element.In this case you only need two swaps. Actually, after you replace each element by a tuple, you can replace each element by a different integer in the range [1, n], assigning each element its final position in the array, and now you need to solve the problem in a permutation. (Notice you need to sort the array first, to find it's final position).In this case  (1,1) -> 1 (2,3) -> 2 (2,4) -> 3 (3,2) -> 4 so the array you need to sort is:(1, 4, 2, 3)
•  » » » » 6 months ago, # ^ |   +29 But you may use one swap only: between the 3 and the last 2.
•  » » » » » 6 months ago, # ^ |   +8 My bad, I was thinking in the problem:Performing swaps between adjacents elements
•  » » 6 months ago, # ^ |   +8 Will this work if we allow to swap not only adjacent elements?
 » 4 months ago, # |   0 Friend of mine was asked the same question in Zalando interview round. Could not solve this too. Swapping any two elements is allowed. Anyone with a solution?
•  » » 4 months ago, # ^ |   +6 I think you or your friend lied. Because there is currently a problem like this in USACO bronze