Nth SHORTEST SUPER SEQUENCE

general
, ,
1

PLEASE SOMEONE HELP ME INORDER TO SOLVE THIS

Nth Shortest Super Sequence

Time out : 4 Sec

Memory Limit : 64MB

A shortest common supersequence of two strings is defined as the shortest possible string containing both strings as subsequences
(See Notes below for a rigorous definition of a supersequence). There can be more than one shortest supersequence for two strings.
For example the strings “ABC” and “ACB” have “ABCB” and “ACBC” as shortest supersequences (both have a length
of 4 characters and contain both the strings as subsequence). Now if you sort them lexicographically
then “ABCB” comes before “ACBC”.
Given two strings S1 and S2 and a number n, your task is to find the nth shortest supersequence of these two strings (1 based index).

Input Format:
The first line contains one integer t, the number of testcases. (1 <= t <= 200)
This will be followed by t test cases, each containing 3 lines.

  • The first line of each test case gives the first string S1
  • The second line gives the second string S2
  • The third line will give the number n (1 based index)

Constraints:

  • The Strings S1 and S2 will contain only uppercase and lowercase english letters only.
  • Length of the strings S1 and S2 will be between 1 and 1000.
  • n will fit into a 32 bit signed integer.

Output Format:
For each test case print the nth shortest supersequence on a separate line. If the total number of shortest supersequences is less than n then print “NO ANSWER” (without quotes).

Sample Input:

3
ABC
ACB
2
ABC
ACB
3
AAA
aaa
20

Sample Output:

ACBC
NO ANSWER
aaaAAA

Notes:

  • In lexicographical ordering, uppercase letters come before lowercase letters (The order - from low to high - is A to Z followed by a to z).
  • Consider two strings A and B of length n and m respectively. We can denote the ith character of
    the strings by A[i] or B[i] respectively.Now consider S be the supersequence of A and B. Then we should be able to
    list n indices X1to Xn such that the indices are in strictly increasing order
    (X123…n) and S[Xi] = A[i] for all i from 1 to n. Similarly we should be able to list m indices Y1to Ym such that the indices are in strictly increasing order(Y123…m) and S[Yi] = B[i]
    for all i from 1 to m. A shortest supersequence is a supersequence of minimum length.
2

This is very standard problem for dynamic programming and you will encounter similar problems on every step.

Clarification: if we denote some string as S (or S1, S2 …) than S’ is string S without first letter. S[i] is i-th letter of string S and S[i…] is string which we recieve, if we erase first i-1 letters. First letter is on position 0.

Now, how you can obtain some shortest supersequence of strings S1 and S2? If they start with same letter, we must use this letter (otherwise, we don’t get the shortest supersequence) and we need to construct supersequence of S1’ and S2’ (we already use first letter). If first letters aren’t equal, than we can use first letter from S1 and add supersequence from S1’ and S2, or first letter from S2 and supersequence from S1 and S2’.

Now denote f(i, j) as number of shortest supersequences created from S1[i…] and S2[j…]. If n is bigger than f(0, 0) than you should print NO ANSWER, because you don’t have enough supersequences.

How to compute f(i, j)? We can use simple dynamic programming. If S1[i…] and S2[j]… are empty strings, than f(i, j) = 1, because only empty string is valid shortest supersequence. In other case, S1[i…] or S2[j…] contains some letters. If S1[i] and S2[j] are equal, than f(i, j) = f(i+1, j+1) - each supersequence of S1[i+1] and S2[j+1…] create one supersequence of S1[i] and S[j] (just add first letter S1[i]). If they aren’t equal, than f(i, j) = f(i+1, j) + f(i, j+1). To each supersequence of S1[i+1…] and S2[j…] we can add S1[i] as first letter and obtain valid supersequence for S1[i…] and S2[j…]. Similar for S1[i…] and S2[j+1].

So function f(i, j) can be computed easily like this:

int f(i, j) {
    if(i == S1.length() and j == S2.length()) return 1;
    if(S1[i]==S2[j]) return f(i+1, j+1);
    return f(i+1, j) + f(i, j+1);
}

Again, a bit of drawing and writing some cases will help to understand it better.

Otherwise, we looking for n-th supersequence. Assume, that first letter of S1 is smaller than first letter of S2. If f(1, 0) >= n than first letter of answer is S1[0]. This is because all supersequences with first letter S1[0] are smaller than supersequences with S2[0]. And number of such supersequences is f(1, 0) which is big enough. So we can look for n-th supersequence from S1’ and S2.

But if we have f(1,0) < n than we need use bigger letter as first. So we use letter S2[0] but we already use f(1, 0) options for n. Now we look ( n-f(1, 0) )-th supersequence from S1 and S2’. And you can continue recursively. Here is simple pseudocode.

function that look for n-th supersequence from S1[i..] and S2[j..]
create_answer(n, i, j) {
    if(S1[i] == S2[j]) {print S1[i]; create_answer(n,i+1,j+1);}
    else if(S1[i]<S2[j]) {
        if(n <= f(i+1, j)) {print S1[i]; create_answer(n, i+1, j);}
        else {print S2[j]; create_answer(n-f(i+1,j), i, j+1);}
    }
    else {
        if(n <= f(i,j+1)) {print S2[j]; create_answer(n, i, j+1);}
        else {print S1[i]; create_answer(n-f(i,j+1), i+1, j);}
    }
}

I think, that this approach is not difficult to understand, but try to write it, draw a 2D table with values. For instance possibilities for aaa and AAA, or aAa and AAA should be good example.

If you have any question ask, I can try to expain it more clear.

3 Likes
3

I am not able to understand f(i,j) clearly.

Michal please clarify this a bit further.

4

OK, I edit my old answer. Hope, that help.

5

Thanks Michal.

The idea you provided is working…
But for large input as mentioned in the problem statement it does not produces the desired output…

Please check on that, I am providing the code i used to solve this problem

#include<stdio.h>
#include<string.h>
char S1[1001];
char S2[1001];
int a[1001][1001];

long long int f(int i, int j) {

if(i ==strlen(S1) || j == strlen(S2)) 
	return (a[i][j]=1);
if(S1[i]==S2[j]) 
{
   if(a[i+1][j+1]>0)
 return  (a[i][j]=a[i+1][j+1]);
   else
   return (a[i][j]= f(i+1, j+1));

}

else
{
		if(a[i+1][j]>0&&a[i][j+1]>0)
	return	a[i][j]=a[i+1][j]+a[i][j+1];
		else if(a[i+1][j]>0)
		return a[i][j]=a[i+1][j]+f(i,j+1);
		else if(a[i][j+1]>0)
	return 	a[i][j]=a[i][j+1]+f(i+1,j);
		else	
	return 	a[i][j]=f(i+1, j) + f(i, j+1);
}

}

/*
int f(int i, int j) {

if(i ==strlen(S1) || j == strlen(S2)) 
	return 1;
if(S1[i]==S2[j]) 
	return f(i+1, j+1);

return f(i+1, j) + f(i, j+1);

}
*/
void create_answer(int n, int i, int j) {

if(i<strlen(S1)&&j<strlen(S2))
if(S1[i] == S2[j]) 
{
	printf("%c",S1[i]); 
	create_answer(n,i+1,j+1);
}
else if(S1[i]<S2[j])
{	
	 
    if(n <=a[i+1][j]) 
	{
		printf("%c",S1[i]);	
		create_answer(n, i+1, j);
	}
    else 
	{
		
		printf("%c",S2[j]);
	
		create_answer(n-a[i+1][j], i, j+1);

	}
}
else 
{

    if(n <= a[i][j+1]) 
	{

		printf("%c",S2[j]); 				
		create_answer(n, i, j+1);
	}
    else 
	{
		printf("%c",S1[i]); 			
		create_answer(n-a[i][j+1], i+1, j);
	}
}

else if(i<strlen(S1))
{printf("%c",S1[i]);
create_answer(n,i+1,j+1);
}
else if(j<strlen(S2))
{printf("%c",S2[j]);
create_answer(n,i+1,j+1);
}
else
{

}

}

int main()
{
int t,i;

scanf("%d",&t);

while(t–)
{ int n=1,i=0,j=0;

scanf("%s",S1);
scanf("%s",S2);
scanf("%d",&n);


	for(i=0;i<=strlen(S1);i++)
	for(j=0;j<=strlen(S2);j++)
	a[i][j]=0;

	
	for(i=0;i<=strlen(S1);i++)
	for(j=0;j<=strlen(S2);j++)
	if(a[i][j]==0)
	f(i,j);

if(a[0][0]<n)
printf("NO ANSWER\n");
else
{create_answer(n,0,0);
printf("\n");
}

}
return 0;

}

6

oh that’s nasty :confused:

Ok suppose you had two strings S1=aa…aa and S2=AA…AA both of length 1000. Than you got 1000!/(500!)^2 possible shortest supersequences. And this number is far too big. Even for long long. So your function f will not get right numbers. But if you get number greater than 2^31 than you just need to know, that this number is too big.

So you should update your code, that when it sees number greater than 2^31 it remembers only number 2^31 (or something a bit greater). Than it should work correctly (I hope).

7

Thanks Michal…For helping me while solving this

Thanks a lot

8

In the function f(i,j), the first case,I think it should be,
if(i == S1.length() or j == S2.length()) return 1;

instead of

if(i == S1.length() and j == S2.length()) return 1;

9

Ran your algorithm, have a question regarding nth SCS problem in general.
Suppose, two strings are: abc, c
Then, will “cabc” be a shortest common supersequence as well? Your algorithm, gives that for this input:
abc
c
3

I mean, shouldn’t the length be 3 for all such supersequences? Or my interpretation is flawed? Please help :slight_smile:

10


Here is my solution. Implemented the same logic. Same problem… Wrong outputs for large test cases … implemented that overflow thing too… still Wrong o/p… please help

11

it fails for the following case :

3
abaca
bbca
1
abaca
bbca
2
abaca
bbca
3

12

Can you provide me the link for the problem.The contest in which i was trying out the problem has actually been shut off.I was getting WA and haven’t found the bug in my code yet.
Thanks.