f2lk6wf90d's blog

By f2lk6wf90d, history, 4 years ago, 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. Comments (30)
 » Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
 » Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
 » Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
 » Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
 » Code#include using namespace std; // moves are reversible and have the same weight in both // directions void dijkstra(int n) { map, int> dist; set>> pq; vector v0(n); iota(v0.begin(), v0.end(), 1); dist[v0] = 0; pq.insert({0, v0}); while (!pq.empty()) { auto p = *pq.begin(); pq.erase(pq.begin()); int base = p.first; // generate all moves for (int i=0; i> n; dijkstra(n); } 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?
•  » » 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#include #include #include #include #include #define SZ 5 using namespace std; map, int> m; map > minv; int adj; int dist; int dist2; int fnext; int par; void getpermutations(int x) { vector v; int cnt = 0; for(int i = 0; i < x; i++) v.push_back(i); do { m[v] = cnt; minv[cnt] = v; cnt++; } while(next_permutation(v.begin(), v.end())); } void fmove(vector& v, int x, int y) { int i = v[x]; v.erase(v.begin() + x); v.insert(v.begin() + y, i); } void getadj(int x) { vector v = minv[x]; int n = SZ; vector v2 = v; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) if(i == j) continue; else {fmove(v2, i, j); int u = m[v2]; adj[x][u] = i + j + 2; v2 = v;} } vector path(int u, int v) { vector p; if(fnext[u][v] == -1) return p; p.push_back(u); while(u != v) p.push_back(u = fnext[u][v]); return p; } void print_vector(int x) { vector v = minv[x]; for(int c: v) printf("%d ", c); putchar('\n'); } int getpar(int x) { int p = -1; for(int i = 0; i < 120; i++) if(x != i) if(dist[x][i] + dist[i] == dist[x]) { if(p == -1) p = i; else if(dist2[x][p] > dist2[x][i]) p = i; } return p; } void print_vector1(int x) { vector v = minv[x]; printf("\""); printf("{"); for(int i = 0; i < 5; i++) printf("%d%s", v[i], i != 4 ? "," : "}\""); } int getint(void) { int x; scanf("%d", &x); return x; } bool check(int x) { vector v = minv[x]; if(v == 4) return true; for(int i = 0; i < 4; i++) if(v[i] == 4) fmove(v, i, 4); int y = m[v]; return dist[x][y] + dist[y] == dist[x]; } int main(void) { getpermutations(SZ); vector v; for(int i = 0; i < 120; i++) getadj(i); for(int i = 0; i < 120; i++) for(int j = 0; j < 120; j++) dist[i][j] = dist2[i][j] = 1<<20; for(int i = 0; i < 120; i++) for(int j = 0; j < 120; j++) fnext[i][j] = -1; for(int i = 0; i < 120; i++) for(int j = 0; j < 120; j++) if(adj[i][j]) {dist2[i][j] = 1; dist[i][j] = adj[i][j], fnext[i][j] = j;} for(int i = 0; i < 120; i++) dist[i][i] = dist2[i][i] = 0; for(int k = 0; k < 120; k++) for(int i = 0; i < 120; i++) for(int j = 0; j < 120; j++) if(dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; fnext[i][j] = fnext[i][k]; dist2[i][j] = dist2[i][k] + dist2[k][j]; } /* for(int i = 0; i < 5; i++) v.push_back(getint()); int x = m[v]; vector p = path(x, 0); for(int c: p) print_vector(c); printf("%d\n", dist[x]); */ for(int i = 1; i < 120; i++) par[i] = getpar(i); for(int i = 1; i < 120; i++) { print_vector1(par[i]); printf("--"); print_vector1(i); putchar('\n'); } return 0; }
•  » » » The graph is symmetric so you don't really need to do all-pairs shortest paths
•  » » » » 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.
•  » » 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.
•  » » Here's a shortest path tree with weights on the edges: http://svgshare.com/i/4hW.svg
•  » » 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?
 » Auto comment: topic has been updated by f2lk6wf90d (previous revision, new revision, compare).
 » It feels like there are two cases. Either we move the largest element into its final position directly. 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. :)
•  » » Could you give an example for [2,4,1,5,3]?
•  » » » 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 = . 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 =  and HR = . 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 = . 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...)
•  » » 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.
•  » » » 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?
•  » » » » The first test case is equivalent to [2,1,5,3,4], since we're sorting in descending order instead.
•  » » » » » 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...
•  » » » » » » OK so when I need to calculate the number of elements less than some element y, instead of using a TreeSet and headSet(y), I used a custom segment tree in an int[] array, and all of a sudden the code ran in < 2 sec. -_-
•  » » » » » » » For N = 1000? That's very interesting! Could you share your implementation?
•  » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   Sure here it is: https://pastebin.com/eZFY0KHvNot that I think it's too much help, since it's full of hacks to speed up the execution. The outline above should be more understandable.
•  » » » » » » » » » Thank you!
•  » » 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.
 » 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". We make all ltr moves before all rtl moves. We never make an intermediate move, ie: each element will be moved at most once through either ltr or rtl. 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) When making ltr moves, suppose we have to make the following moves : { (i1,j1), (i2,j2) } wherea) 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 →   You are referring to problem "Sorting" in BOI 2007 (solution, judge)
•  » » 4 years ago, # ^ | ← Rev. 2 →   You gave a wrong link
•  » » » Fixed. Thanks for noticing this
•  » » Thanks!!
•  » » I had no idea this was a duplicate problem. This was a problem from the Greek team selection contest in 2013. Looking up reformulations of the statement didn't return anything relevant. Thank you!