## 10252 - Common Permutation

Moderator: Board moderators

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

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 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.
[/code]
koodeGuru
New poster

Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

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

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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.
IIUC GOLD
New poster

Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm

### 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
kiddi
New poster

Posts: 2
Joined: Thu Apr 22, 2004 6:53 pm

### 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.........
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........
Ferdous
New poster

Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm

### 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
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.
Last edited by koodeGuru on Fri Apr 30, 2004 6:37 pm, edited 1 time in total.
koodeGuru
New poster

Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

[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."
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.
koodeGuru
New poster

Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

### 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`
koodeGuru
New poster

Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

### 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.
koodeGuru
New poster

Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

### 10252 TLE

Last edited by midra on Fri May 14, 2004 3:52 am, edited 1 time in total.
midra
Experienced poster

Posts: 119
Joined: Fri Feb 13, 2004 7:20 am

### Hi

What when input is:
Code: Select all
`guessthenextlineI know youhate this :-)`

hth
Suman
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

Sorry, but I don't understand what you mean...
if you can explain me a little more I will appreciate very much
bye!
midra
Experienced poster

Posts: 119
Joined: Fri Feb 13, 2004 7:20 am

### 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 !!!!
sumankar
A great helper

Posts: 288
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

PreviousNext