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).

#include <bits/stdc++.h>
using namespace std;

// moves are reversible and have the same weight in both
// directions

void dijkstra(int n) {
	map<vector<int>, int> dist;
	set<pair<int, vector<int>>> pq;

	vector<int> 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; i++) {
			for (int j=0; j<n; j++) if (i != j) {

				auto tmp = p.second;
				int weight = i+j+2;

				int x = tmp[i];
				tmp.erase(tmp.begin() + i);
				tmp.insert(tmp.begin() + j, x);

				if (dist.count(tmp) == 0 || base + weight < dist[tmp]) {
					pq.erase({dist[tmp], tmp});
					dist[tmp] = base + weight;
					pq.insert({dist[tmp], tmp});
				}
			}
		}
	}

	do {
		for (int x : v0) {
			cout << x << ' ';
		}
		cout << ":" << dist[v0] << '\n';
	} while (next_permutation(v0.begin(), v0.end()));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cerr.tie(nullptr);

	int n;
	cin >> 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?

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

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. :)

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.

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