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(nn) although it might look O(n^3) in the first llok, but there are O(nn) 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 (KK) 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(NNK*logK)