10252  Common Permutation
Moderator: Board moderators

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
1. read the first phrase of the problem description again. You missed, that the permutation of x could be different when trying to check for subsequence of first string or 2nd string.
2. you can be sure, that there are only lowercase letters in each line of input.
3. there may be blank lines; handle them as test cases
so output for
ab
<the line before indicates a blank line>
is a blank line.
2. you can be sure, that there are only lowercase letters in each line of input.
3. there may be blank lines; handle them as test cases
so output for
ab
<the line before indicates a blank line>
is a blank line.
so x can be sequence or subsequence
Code: Select all
read the first phrase of the problem description again. You missed, that the permutation of x could be different when trying to check for subsequence of first string or 2nd string.
So that means any permutation of x can either be subsequence of string1 or string2 or strings themselves(I mean string one string2).
ab
ba
x=ab >>string1 but not subsequence of string1.
abc
ba
x=ab>>subsequence of string 1 but a different combination of string2.
Thanks in advance.
[/code]

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
I think the problem description is clear in this point.
But I try to formulate it in another way:
The conditions on x that it is a valid solution are:
find one permutation of x that is subsequence of first string
and
find one (perhaps different) permutation of x that is subsequence of second string.
and
x should have maximum length and all characters should be sorted in lexicographic order.
But I try to formulate it in another way:
The conditions on x that it is a valid solution are:
find one permutation of x that is subsequence of first string
and
find one (perhaps different) permutation of x that is subsequence of second string.
and
x should have maximum length and all characters should be sorted in lexicographic order.
This problem can be solved very easily with the frequency caluculation of each character. Suppose, the input strings are:
bbaccbacd
abbcdbaae
For the first string the frequency distribution is:
a 2
b 3
c 3
d 1
And for the second string the frequency distribution is:
a 3
b 3
c 1
d 1
e 1
Calculate the minimum(common) frequeny for each character.
a 2
b 3
c 1
d 1
And if u start from 'a' and end at 'z' then u will get the first alphabetiacal order automatiocally. So for the above input strings the output will be:
aabbbcd
Hope this will help to understand and solve the problem.
bbaccbacd
abbcdbaae
For the first string the frequency distribution is:
a 2
b 3
c 3
d 1
And for the second string the frequency distribution is:
a 3
b 3
c 1
d 1
e 1
Calculate the minimum(common) frequeny for each character.
a 2
b 3
c 1
d 1
And if u start from 'a' and end at 'z' then u will get the first alphabetiacal order automatiocally. So for the above input strings the output will be:
aabbbcd
Hope this will help to understand and solve the problem.
Are there any test cases which I can use
hello I've read every post there is about this program, and tried all the test cases but I still seem to get WA..... do you know of any special cases which I have to test....
for the test case :
pretty
women
walking
down
the
street
abc
acd
pretty woman
Walking down
inGing
singing
e
a
ab
bbaccbacd
abbcdbaae
i get :
e
nw
et
ac
anow
ggiinn
<blank line>
<blank line>
aabbbcd
for the test case :
pretty
women
walking
down
the
street
abc
acd
pretty woman
Walking down
inGing
singing
e
a
ab
bbaccbacd
abbcdbaae
i get :
e
nw
et
ac
anow
ggiinn
<blank line>
<blank line>
aabbbcd
10252 (Common Permutation)...PE ??
I can't figure out why my code received PE. Can anyone help me in finding out my fault? Here's my code:
deleted later.........
deleted later.........
Last edited by Ferdous on Wed Apr 28, 2004 2:35 pm, edited 1 time in total.
I am destined to live on this cruel world........
10252 again with java code
After going through all discusions still I am getting WA for this problem.
Can someone tell me whats wrong with my code
I know it looks much more complicated than the problem. But excuse me I am just a beginner.Thanks.
Can someone tell me whats wrong with my code
Code: Select all
Code has been removed. Thanks to Adrian.
Last edited by koodeGuru on Fri Apr 30, 2004 6:37 pm, edited 1 time in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
i c
Adrian thanks a lot for your patience. But I also see that my program does'nt check for special characters. Is is realy necessary to perform error checking when the problem doesnt specificaly ask for it.
I will try your suggestion and submit once again. Thanks.
I will try your suggestion and submit once again. Thanks.
thanks a lot
Yeha you pointed out the root error. Thanks a lot. It got accepted. Now I have gained some confidence.
Code: Select all
Perseverence is everything
run time
Actualy i dont know what exactly that means. Is it the time my program stays in physical memory while it is executed? The runtime for my solution was 8.45 sec. Too bad. How do I become efficient? Can someone shed some light on this. Thanks in advance.
Hi
What when input is:
hth
Suman
Code: Select all
guessthenextline
I know you
hate this :)
Suman
Hi
From what it seems you did not try out the i/p
I posted.
Well scanf("%s ... is not sufficient
it breaks on encountering whitespace, can't catch empty lines,
and so on and so forth.
I had the same TLE thing, I changed my code which had scanf to a manual
readline procedure, which is trivial to implement in C.
Should you need more help PM me, I wonder whether such trivialities
like readline code should be posted here !!!!
I posted.
Well scanf("%s ... is not sufficient
it breaks on encountering whitespace, can't catch empty lines,
and so on and so forth.
I had the same TLE thing, I changed my code which had scanf to a manual
readline procedure, which is trivial to implement in C.
Should you need more help PM me, I wonder whether such trivialities
like readline code should be posted here !!!!