f2lk6wf90d's blog

By f2lk6wf90d, history, 4 years ago, In English

Hello everyone, I found this problem a while ago and I'm still stuck on it (there's no OJ to submit it as far as I know):
You are given a permutation of the integers from 1 to N. In this case, moving an element from i to j is defined as removing the element from position i, and inserting it at position j. For example, in this array: [4,5,2,1,3], moving the element from 2 to 5 gives us the array [4,2,1,3,5]. The cost of moving an element from i to j is defined as i + j (1-indexed).
What is the minimum total cost needed to sort the permutation?
Example:
[1,3,4,5,2][1,2,3,4,5] with total cost 5 + 2 = 7.
1 ≤ N ≤ 1000, however solutions with any reasonable complexity are welcome.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Code

Here's a brute-force helper if anyone wants to play around and try to spot a pattern. Interestingly, the worst case scenario is not always n, n - 1, ..., 2, 1.

The next step would perhaps be writing some greedy algorithm and comparing the outputs?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've already tried this :(
    Here's some code (uses Floyd-Warshall instead) that generates a shortest-path tree that is readable by graphviz for n = 5:

    Spoiler
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The graph is symmetric so you don't really need to do all-pairs shortest paths

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, I know it's a huge overkill. I originally wanted to see if there was a pattern when transforming any permutation to any other permutation.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Worst cases (all with the largest cost listed):

    n =  1; d =  0; p = {1}
    n =  2; d =  3; p = {2,1}
    n =  3; d =  7; p = {3,2,1}
    n =  4; d = 12; p = {4,3,2,1}
    n =  5; d = 18; p = {1,5,4,3,2}, {2,1,5,4,3}, {5,4,3,2,1}
    n =  6; d = 27; p = {2,1,6,5,4,3}
    n =  7; d = 37; p = {2,1,7,6,5,4,3}, {3,2,1,7,6,5,4}
    n =  8; d = 49; p = {3,2,1,8,7,6,5,4}
    n =  9; d = 62; p = {3,2,1,9,8,7,6,5,4}, {4,3,2,1,9,8,7,6,5}
    n = 10; d = 77; p = {4,3,2,1,10,9,8,7,6,5}
    

    Searching OEIS for the sequence of costs was not fruitful.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here's a shortest path tree with weights on the edges: http://svgshare.com/i/4hW.svg

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have a feeling that the answer with minimum cost is also any answer that uses the minimum number of moves, could you confirm this?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It feels like there are two cases.

  1. Either we move the largest element into its final position directly.
  2. Or we don't move the largest element at all, an example of that is [2, 3, 4, 5, 1].

In the first case, let's have a look at the optimal solution and all the moves it makes before moving the largest element x (into its final position). Consider the parts to the left and right of x respectively, call them HL and HR. We either have moves within HL, within HR, or between HL and HR. If we move x to its final position directly (i.e. to the end of the list), the moves within HL are unaffected, the moves within HR become cheaper (!) as the index for each element decrease by 1, and the moves between HL and HR also become cheaper.

So if we are going to move the largest element, we might just as well do it directly. After we do this, we end up with the same problem but of size N - 1, solve recursively.

In the second case, and this is where I'm unsure and feel I'm almost guessing (or going on intuition). Consider again the two halves HL and HR. Notice that there won't be any moves from HL to HR, as that would mean that we would later need to move x, which would put us in case 1. Perform the moves to get HL sorted, this reduces to the same problem but of some size M < N (solve recursively). For each element y in HR, going left to right, move it into its final position in HL.

So all in all, we just try both cases and pick the better one. The complexity should be quadratic.

But I'm probably mistaken, so please do give me a counter-example showing where the above approach goes wrong (if it is wrong). We might all learn something from it, and be one step closer to the real solution. :)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you give an example for [2,4,1,5,3]?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So yeah for [2,4,1,5,3] the optimal solution falls into the second case.

      • So x = 5, HL = [2, 4, 1] and HR = [3].
      • Solve HL recursively. Solving (i.e. sorting) [2,4,1] is equivalent to solving [2,3,1], whose optimal solution also happens to be of case 2.

      • So x = 3, HL = [2] and HR = [1].
      • Solve HL recursively. We hit our base case and return cost 0.
      • Move each element of HR into its final position in HL. So we move 1 to the front, which costs 1 + 3 = 4.
      • We also try to solve [2,3,1] using case 1, but that doesn't give a result better than 4. (Using case 1 will yield a cost of 8.)

      • We now have x = 5, HL = [1, 2, 4] and HR = [3].
      • Move each element of HR into its final position in HL. So we move 3 to the third position, which costs 3 + 5 = 8.
      • We are now done and have accumulated a total cost of 4 + 8 = 12. We also try to solve it using case 1, which immediately gives a cost of 9 + the cost of solving [2,4,1,3], which isn't better than 12, so 12 is the optimal answer.

      (I wish I could do proper sub-bullets to illustrate the recursive steps better, but yeah...)

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This sounds good. If you'd like to post an implementation of your idea too, testcases are here. Note: You have to compress the integers in the input first (they are all distinct), and sort in descending order instead, so you have to set every element of the permutation i to N - i + 1.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So the first test case is, if I'n not mistaken, equivalent to [4,5,1,3,2]. The output says that the answer is 11, whereas my code, your graph, and my brain says it's 17.

      Or am I reading the input incorrectly?

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The first test case is equivalent to [2,1,5,3,4], since we're sorting in descending order instead.

        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          OK then all the results match up.

          So my Java solution runs in 16 sec on the last test case. I could probably cut it down to below 10 sec with some custom data structures (instead of ones requiring auto-boxing and so on), or even better rewrite it in C++. ^^

          So yeah, on to figuring out how to make the algorithm faster...

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            OK so when I need to calculate the number of elements less than some element y, instead of using a TreeSet<Integer> and headSet(y), I used a custom segment tree in an int[] array, and all of a sudden the code ran in < 2 sec. -_-

            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              For N = 1000? That's very interesting! Could you share your implementation?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So one place where the reasoning goes wrong, is when it comes to the time complexity.

    I thought that we'd only have O(N) dp-states, and that therefore the complexity was O(N2). However this is not true. First of all I didn't account for the normalization, which unless you use counting sort or the like, will account for a factor. The factor also shows up when we need to calculate the position in HL where we will move an element of HR.

    But more importantly, for the above algorithm, as stated, there are not O(N) dp-states but O(N2) dp-states. More precisely, the number of states is equivalent to the number of distinct prefixes of our input (after normalization) you can get by removing the q largest elements, for some q. In practice this number has a pretty good constant, because if the i:th largest element has position Qi, then its removal will only affect prefixes of length at least Qi. And the normalization also makes it so that the dp-state changes only if the removed element causes a change in the "relative order".

    So even if the total complexity becomes , an efficient implementation has a good chance of making a time limit around a few seconds.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a few points. Not sure how useful, but here it goes :
Suppose we make a move (i,j) where i < j, then we call this move "ltr", otherwise we call it "rtl".

  1. We make all ltr moves before all rtl moves.
  2. We never make an intermediate move, ie: each element will be moved at most once through either ltr or rtl.
  3. Number of moves to be made, M = n — size_of(LIS(n)). There are many LIS sequences. We can try to choose an LIS where number of lrt = p, number of rtl = q, M = p + q. (not sure how)
  4. When making ltr moves, suppose we have to make the following moves : { (i1,j1), (i2,j2) } where
    a) i1 < i2, j2 < j1, i1 < j1, i1 < j2. Then, we must make (i1,j1) before (i2,j2).
    b) i1 < i2, j1 < j2, i2 < j1. Then, order of making these moves doesn't matter.
    Similarly, we can find rules for rtl moves.
»
4 years ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

You are referring to problem "Sorting" in BOI 2007 (solution, judge)