### PROBLEM LINK:

**Editorialist:** Karan Aggarwal

### DIFFICULTY:

MEDIUM

### PREREQUISITES:

LIS, Dynamic Programming

### PROBLEM:

Problem : Given N distinct permutations (P1……Pn) of first K natural numbers, make a arrangement A, such that each element of A is one of the permutation Pi in the input. Each permutation Pi in the input occurs at least once in the arrangement.

And the sum of E(Ai, Ai+1) is minimized. and A first increases lexicographically and then decreases lexicographically.

Condtraints : 1<=N<=1000 and 1<=K<=100.

### EXPLANATION:

Let us assume that we have sorted the given K permutations. And for eahc pair i,j we have calculated the edit distance between Pi and Pj.

Now a thing to notice is that Edit[i][j] + Edit[j][k] <= Edit[i][k], for any triplet (i,j,k). Using this we can say that in the optimal arrangement, any Pi, will be present only once.

We can compute the answer using DP. DP[i][j] be the minimum cost to make a arrangement of the Pn……Pi, such that one end end of the arrangement, Pi is there and on the other end, Pj. where j>=i.

So DP[n][n] = 0; DP[n][i-1] = Edit[n-1][n].

DP[i][j] = Edit[i-1][i] + DP[i-1][j] if(j<i-1)

else

for all k = i-2 to n min( DP[i-1][k] + Edit[k][i] ).

Now this is O(n*n) although it might look O(n^3) in the first llok, but there are O(n*n) states ,and each can be computed in O(1), except some O(N) states which require O(N) time to compute.

Final ans is for(k = 2 to n) min(DP[1][k]).

Now one task that remains is generating the Edit[][] matrix and sorting the initial permutations in the input.

For each Edit[i][j], we need to calculate the edit distance between Pi and Pj. This is order (K*K) typically using the standard DP method for edit distance. But since its only insert and delete and both are permutation, Edit Distance =2*(K-LCS(Pi, Pj)), and LCS of 2 permutation can be reduced to finding the LIS of a permutation. Which can be done in O(K * logK)

**Complexity** : **O(N NK*logK)**