10252 - Common Permutation

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by Jan » Sat Oct 20, 2007 10:27 pm

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

Post by jackpigman » Wed Mar 19, 2008 10:04 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
Thanks for your help :D
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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Mar 20, 2008 12:22 am

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

Post by jackpigman » Thu Mar 20, 2008 6:21 pm

I changed my code, but got a RTE :cry: :cry: :cry:
Please help me.......

Code: Select all

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

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Thu Mar 20, 2008 7:19 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.

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

Post by jackpigman » Thu Mar 20, 2008 9:50 pm

Thanks a lot emotional blind!!
finally got an AC :D :D :D :D

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

Re: 10252 - Common Permutation

Post by palash » Mon Jun 16, 2008 9:09 pm

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

Post by maruf » Mon Jun 30, 2008 12:07 pm

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 :cry:
please help :oops:
lives for eternity......

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

Re: 10252 - Common Permutation

Post by Jan » Mon Jun 30, 2008 4:46 pm

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

Post by Galileo » Wed Jul 16, 2008 1:33 pm

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

Post by Galileo » Thu Jul 17, 2008 8:23 am

nothing

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

Re: 10252 - Common Permutation

Post by ExUCI » Wed Dec 31, 2008 5:01 am

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 :evil:
Remove your code after AC :)

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

Re: 10252 - Common Permutation

Post by wsb7metal » Mon Mar 30, 2009 3:06 am

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

Post by banglacity » Thu Jun 25, 2009 5:43 am

After suffering a lot, finally i got Ac :D

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

Post by amishera » Wed May 12, 2010 1:33 am

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?

Post Reply

Return to “Volume 102 (10200-10299)”