Bappy's Blog

As n<=16, the problem can be solved with bitmask DP with 2 states. State-1 is for the row(Boy). State-2 is now which column(Girl) is free with bitmasking. Go row by row. For every row(Boy), check the all available columns(Girl) one by one and calculate the best result. When all the girls have been taken, then the process will be terminated. Think before you code -_- Happy Coding -_-

There're two segments in the solution of this problem. 1. To calculate the length of the shortest string you have to calculate the LCS of two given strings. 2. To calculate the total number of unique strings, you've to follow several steps. i. First of all, it'll be a three states DP. State-1 for the current position of the generating string. State-2 for the current position of the given string-1. State-3 for the current position of the given string-2. ii. If(s1[pos1] == s2[pos2]) then you've to take one way Funtion(pos+1,pos1+1,pos2+1) iii. If(s1[pos1] != s2[pos2]) then you've to take possible two way Funtion(pos+1,pos1+1,pos2)+Function(pos+1,pos1,pos2+1). iv. Now, If any of the given string is completely taken, then you've to add the remaining characters of the other string manually. Check, is the current length of generating string is equal to the previously calculated unique string length or not? If yes, that means you've successfully g