INVESORT  Inversion Sort
You have just bought an old fashioned jukebox that can hold 10 music albums. Albums
are mantained as a sequence, each album represented by a unique lowercase letter between
“a” and “j”, inclusive. The jukebox allows you to select a subsequence of contiguous
albums and a mechanical arm inverts that part of the sequence. For instance, if the
current sequence is “abcdefghij” and you select the subsequence “bcd”, the result of
the inversion would be “adcbefghij”. Soon you notice that it is possible to get the
albums into any desired order using simply inversions. However, you are interested in
doing so with the minimum number of operations.
Given the current order and a desired order of the 10 music albums, find the minimum
number of inversion operations needed to obtain the desired order.
Input
The input contains several test cases, each one described in a single line. The line contains
two strings C and D separated by a single space, representing the current and desired
orders of the music albums, respectively. Each of the strings has exactly 10 characters
and contains the characters of “abcdefghij” in some order. The last line of the input
contains two asterisks (“*”) separated by a single space and should not be processed as
a test case.
Output
For each test case output a single line with an integer representing the minimum number
of inversions needed to transform the current order given by C, into the desired order
given by D.
Example
Input:
abcdefghij adcbefghij
abcdefghij abcdefghij
bcdaefghji beagfcdhji
* *
Output: 1
0
2
hide comments
vishalcc:
20210403 13:56:56
Meet in the middle will work 

chuchuchan:
20210402 19:28:34
wow Last edit: 20210402 19:29:10 

potter2506:
20210208 19:01:51
where can i find editorial for this problem ??


shiddeshu:
20190505 13:18:02
Please give some hints on this problem. Shall we use graph bfs search to solve this. Please guide me I am a newbie 

sajal2419:
20160526 19:25:27
can some one give me some case ?? 

ButaBil:
20120809 15:48:15
There is around 900 tests 

ymGXX:
20101127 03:53:39
How many test cases are there? Last edit: 20101127 03:53:57 

যোবায়ের:
20100901 00:28:16
1. b(cdae)fghji


Anirban Saha:
20100901 00:28:16
can someone please explain test case 3? 
Added by:  Pablo Ariel Heiber 
Date:  20100824 
Time limit:  89.26s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS OBJC PERL6 VB.NET 
Resource:  FCEyN UBA ICPC Selection 2009 