Hello everyone! I know that the editorial has been released but ,after several attempts, I don’t understand it.
In my solution, I created a tree using an array that shows whether there is a connection of node p and q. My question or problem that I have is how do I find the minimum cost? I tried inserting the possible combination inside an array but it gives SIGSEGV. So do I test it one by one and find the minimum cost or is there a simple solution?
hey, let me explain you my [solution][1]. its a simple dynamic programming problem first you have to create a matrix let say MAT[M][M] which stores all possible transformation of characters which is easily calculate using ALL PAIR SHORTEST PATH ALGORITHM (FLOYD WARSHALL ). now you have matrix which tells all possible conversion of one letter to another. suppose if MAT[x][y]==1 i.e, x is transformable to y, and if MAT[x][y]=infinite you cannot transform x to y.
Now we calculate the ans lets take a solution array sol[M] which stores the solution of our problem. since M<=200, for every element in a given array A, we can replace every letter by 1 to M and the permutation in which no. of changed letters is minimum is our final ans.we can only form valid permutation by using MAT[][]. since total no. of permutation is very large O(m^n) so we cannot generate all permutation of the given array.
so we write dynamic programming solution,the problem ask for calculating minimum no. of inversion,for this we write O(n*m) solution.start from last element of the array A,suppose first you have a single element (forget about all other element before last element) now single element is always sorted. now start filling the values of sol[] for last element, sol[i]=min(sol[i+1],MAT[curr][i]); curr stores the a[last] and mat[curr][i] shows weather we can change curr to i where i is between 1 to M.
now for each element which is before last element we can calculate result by sol[j]=min(sol[j]+MAT[curr][j],sol[j+1]; if MAT[curr][i]==1 else sol[j]=min(infinite,sol[j+1]); after doing this for all element we get our ans at sol[0]. try out few example you got what this expression says, for better understanding read my code and print values of sol[] using print functions which i explicitly defined for checking sol[] values.
[1]: http://www.codechef.com/viewsolution/6732317 “solution”