## Monday, October 27, 2014

### SPOJ - LSORT

Problem Statement:
SPOJ - LSORT

Summary:
Sort a permutation of [1..N] by the following rule:
1. Start with P the permutation of [1..N], and Q an empty set [].
2. For each step i, we can choose any element in P and append it to beginning or end of Q. We incur cost i*x, where x is the position of the element in P at that time.
3. In the end Q must be in sorted ascending order.

Find the minimal cost possible to perform this operation.

Solution:
A nice problem! Before doing the usual DP on the string, we need to precompute the positions of elements in P after removing several elements to Q, and there is a nice pattern that makes this computation possible and very efficient. Let's say Q has endings i and j. Notice that elements from i to j are already in sorted order. We can either take i-1 or j+1 from P, and for each we can calculate its current position by observing that it is equal to the number of elements in i to j that are place behind i-1 or j+1 in the original array P. After computing the positions of all elements given i or j, we can do a simple DP: minimal cost to build Q[i..j] is the minimum between cost to build Q[i..j-1] + cost of placing j, or cost to build Q[i+1..j] + cost of placing i.

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

/*
A[i] are elements.
P[i] is the position of i in A[i].
X[i][k] = the value x (position of element i from the left) after we
used items [i+1 .. k] where we want to place i to the left.
Y[i][k] = the value x after we used items [k .. i-1] where we want
to place i to the right.
X[i][k] = X[i][k-1] - (P[k] < P[i] ? 1 : 0);
Y[i][k] = Y[i][k+1] - (P[k] < P[i] ? 1 : 0);
*/

int A[1003];
int P[1003];
int X[1003][1003], Y[1003][1003];
int dp[1003][1003];
int N;
int INF = (int) 1e9;
void solve(){
for(int i=0;i<N;++i){
P[A[i]-1] = i;
}
for(int i=0;i<N;++i){
X[i][i] = P[i];
for(int k=i+1;k<N;++k){
X[i][k] = X[i][k-1] - (P[k] < P[i] ? 1 : 0);
}
}
for(int i=0;i<N;++i){
Y[i][i] = P[i];
for(int k=i-1;k>=0;--k){
Y[i][k] = Y[i][k+1] - (P[k] < P[i] ? 1 : 0);
}
}
for(int i=0;i<N;++i){
dp[i][i] = P[i]+1;
}
for(int k=1;k<N;++k){
for(int i=0;i+k<N;++i){
int j=i+k;
int n=k+1;
dp[i][j] = min(dp[i+1][j] + (X[i][j]+1)*n, dp[i][j-1] + (Y[j][i]+1)*n);
}
}
printf("%d\n", dp[0][N-1]);
}

int main(){
int tc;
cin>>tc;
while(tc--){
scanf("%d", &N);
for(int i=0;i<N;++i){
scanf("%d", &A[i]);
}
solve();
}
return 0;
}