10252 - Common Permutation

[Adrian Kuegel]

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.

[koodeGuru]

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]

[Adrian Kuegel]

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.

[IIUC GOLD]

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.

[kiddi]

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

[Ferdous]

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.........

[koodeGuru]

After going through all discusions still I am getting WA for this problem.
Can someone tell me whats wrong with my code

Code: Select all

Code has been removed. Thanks to Adrian.

I know it looks much more complicated than the problem. But excuse me I am just a beginner.Thanks.

[Adrian Kuegel]

[java]while ((s = Main.readLn(255)) != null) [/java]
Shouldn't it be Main.readLn(1010) or some other value >1000?
"Each string is on a separate line and consists of at most 1000 lowercase letters."

[koodeGuru]

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.

[koodeGuru]

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

[koodeGuru]

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.

[midra]

I have read several posts in this forum about this problem but I don't know What is wrong with my code...

[sumankar]

What when input is:

Code: Select all

guessthenextline

I know you
hate this :-)

hth
Suman

[midra]

Sorry, but I don't understand what you mean...
thanks anyway for answer me...
if you can explain me a little more I will appreciate very much
bye!

[sumankar]

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 !!!!