madver's blog

By madver, history, 12 months ago, In English,

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 ?

 
 
 
 
  • Vote: I like it  
  • +8
  • Vote: I do not like it  

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    for test

    2 3 4 ... n 1

    you would return 1 instead of n — 1

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Would it work for the sequence 1 3 2 2?

    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +29 Vote: I do not like it

        But you may use one swap only: between the 3 and the last 2.

        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          My bad, I was thinking in the problem:

          Performing swaps between adjacents elements

  • »
    »
    12 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Will this work if we allow to swap not only adjacent elements?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think you or your friend lied. Because there is currently a problem like this in USACO bronze