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 »

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 »

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 »

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 »

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.

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

Post by emotional blind »

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 »

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 »

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 »

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 »

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 »

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 »

nothing

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

Re: 10252 - Common Permutation

Post by ExUCI »

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 »

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 »

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 »

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)”