10252 - Common Permutation

Moderator: Board moderators

Nope. If the solution is 'ab' then of course 'ba' is a solution, too. right?
Ami ekhono shopno dekhi...
HomePage
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 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.
jackpigman
New poster

Posts: 8
Joined: Fri Jan 04, 2008 5:57 pm

There can be multiple cases. Your code works for only one case.
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 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.
jackpigman
New poster

Posts: 8
Joined: Fri Jan 04, 2008 5:57 pm

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.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

Thanks a lot emotional blind!!
finally got an AC
jackpigman
New poster

Posts: 8
Joined: Fri Jan 04, 2008 5:57 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`
palash
New poster

Posts: 4
Joined: Wed Apr 16, 2008 8:49 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......
maruf
New poster

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

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
Jan
Guru

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

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
Galileo
New poster

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

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
ExUCI
New poster

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

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. =/
wsb7metal
New poster

Posts: 1
Joined: Mon Mar 30, 2009 3:03 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 !
banglacity
New poster

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

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 = 02 then return3 if b[i, j ] = “&”4 then PRINT-LCS(b, X, i − 1, j − 1)5 print xi6 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?
amishera
New poster

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

PreviousNext