## 10252 - Common Permutation

Moderator: Board moderators

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Nope. If the solution is 'ab' then of course 'ba' is a solution, too. right?
Ami ekhono shopno dekhi...
HomePage

jackpigman
New poster
Posts: 8
Joined: Fri Jan 04, 2008 5:57 pm
I've got all the test cases I could find right but still get's Wa....
Here's my code.

Code: Select all

``````removed after AC
``````
Last edited by jackpigman on Thu Mar 20, 2008 9:48 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
There can be multiple cases. Your code works for only one case.

jackpigman
New poster
Posts: 8
Joined: Fri Jan 04, 2008 5:57 pm
I changed my code, but got a RTE

Code: Select all

``````removed after AC
``````
Last edited by jackpigman on Thu Mar 20, 2008 9:49 pm, edited 1 time in total.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
when length of a = 1000, and strlen(a) = 1000 then you can't access a[strlen(a)] ie a[1000], coz your size of array is 1000 so that you can access 0 to 999. try increasing size by 1 ie set the max size to 1001.

jackpigman
New poster
Posts: 8
Joined: Fri Jan 04, 2008 5:57 pm
Thanks a lot emotional blind!!
finally got an AC

palash
New poster
Posts: 4
Joined: Wed Apr 16, 2008 8:49 pm

### Re: 10252 - Common Permutation

pls help WA. I didn't find my bug in my code.every time i got WA here is my code

Code: Select all

``````At last Acc
``````

maruf
New poster
Posts: 17
Joined: Sat May 24, 2008 6:00 pm

### Re: 10252 - Common Permutation

Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of
what is meant hear by "permutation" && "subsequence"??
i am totally in dark
lives for eternity......

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 10252 - Common Permutation

Subsequence: Suppose you are given two strings A and B. B will be said the subsequence of A, if you can make B from A by deleting some (or none) characters.
Permutation: Suppose you are given two strings A and B. B will be said the permutation of A, if you can make B from A by re-arranging some (or none) characters.

So, 'abc' is a subsequence of 'adbfc' and 'aabc' is a permutation of 'caba'.
Ami ekhono shopno dekhi...
HomePage

Galileo
New poster
Posts: 3
Joined: Tue Jul 15, 2008 9:30 am

### Re: 10252 - Common Permutation

Can someone tell me what is the output for?
aAaAAa
aaaaaa

Galileo
New poster
Posts: 3
Joined: Tue Jul 15, 2008 9:30 am

### WA Plz help

nothing

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA

### Re: 10252 - Common Permutation

Hi, I just got AC without caring about such cases with uppercases like aaAAAaaa or whatever and there is no such thing. And yes, LCD can be used, I used it but I gonna change it for the simpler alg now!!

I read too many posters for nothing

wsb7metal
New poster
Posts: 1
Joined: Mon Mar 30, 2009 3:03 am

### Re: 10252 - Common Permutation

I got AC!
I read just letters a..z and <space>
And ignore the last output, I dont know why, but work. =/

banglacity
New poster
Posts: 1
Joined: Thu Jun 25, 2009 5:37 am

### Re: 10252 - Common Permutation

After suffering a lot, finally i got Ac

The only problem is- take input by gets() rather than scanf()

Hope it will work !

amishera
New poster
Posts: 38
Joined: Sat Dec 27, 2008 10:42 pm

### Re: 10252 - Common Permutation

My problem is rather simple. I used the print_LCS from the cormen book:

Code: Select all

``````PRINT-LCS(b, X, i, j )
1 if i = 0 or j = 0
2 then return
3 if b[i, j ] = “&”
4 then PRINT-LCS(b, X, i ? 1, j ? 1)
5 print xi
6 elseif b[i, j ] = “?”
7 then PRINT-LCS(b, X, i ? 1, j )
8 else PRINT-LCS(b, X, i, j ? 1)``````
and implemented in 2 ways:

recursive:

Code: Select all

``````void print(char a[], int i, int j)
{
if (i == 0 || j == 0)
{
return;
}
if (op[i][j] == 3)
{
print(a, i-1,j-1);
printf("%c", a[i-1]);
}
else if (op[i][j] == 1)
{
print(a, i-1,j);
}
else
{
print(a, i,j-1);
}
}``````
and iterative:

Code: Select all

``````void print(char a[], int i, int j, int len)
{
char pr[MAX];
int k = len-1;

while ((i != 0) && (j != 0))
{
if (op[i][j] == 3)
{
i--,j--;
pr[k] = a[i];
k--;
}
else if (op[i][j] == 1)
{
i--;
}
else
{
j--;
}
}

pr[len] = '\0';
printf("%s", pr);
}``````
The recursive is giving AC, but iterative is giving WA. While calling I pass the same parameters and for len pass the maximum length. The test cases passes for both implementations. Isn't this peculiar that it still gives WA for iterative one?