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

Post Reply
Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Apr 21, 2004 1:44 am

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
New poster
Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

so x can be sequence or subsequence

Post by koodeGuru » Wed Apr 21, 2004 8:16 pm

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.
:wink: [/code]

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

Post by Adrian Kuegel » Wed Apr 21, 2004 8:47 pm

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
New poster
Posts: 19
Joined: Tue Jun 11, 2002 4:27 pm
Location: Bangladesh
Contact:

Post by IIUC GOLD » Thu Apr 22, 2004 3:48 pm

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
New poster
Posts: 2
Joined: Thu Apr 22, 2004 6:53 pm

Are there any test cases which I can use

Post by kiddi » Thu Apr 22, 2004 6:58 pm

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
New poster
Posts: 26
Joined: Sun Dec 14, 2003 1:17 pm
Location: Dhaka, Bangladesh
Contact:

10252 (Common Permutation)...PE ??

Post by Ferdous » Tue Apr 27, 2004 11:47 am

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

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

10252 again with java code

Post by koodeGuru » Fri Apr 30, 2004 12:18 am

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.

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

Post by Adrian Kuegel » Fri Apr 30, 2004 2:40 pm

[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
New poster
Posts: 23
Joined: Mon Apr 19, 2004 6:24 am

i c

Post by koodeGuru » Fri Apr 30, 2004 6:31 pm

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

Post by koodeGuru » Fri Apr 30, 2004 6:33 pm

Yeha you pointed out the root error. Thanks a lot. It got accepted. Now I have gained some confidence. :lol:

Code: Select all

Perseverence is everything

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

run time

Post by koodeGuru » Fri Apr 30, 2004 6:35 pm

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
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10252 TLE

Post by midra » Fri May 07, 2004 4:16 am

I have read several posts in this forum about this problem but I don't know What is wrong with my code...
Last edited by midra on Fri May 14, 2004 3:52 am, edited 1 time in total.

sumankar
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Hi

Post by sumankar » Fri May 07, 2004 6:34 am

What when input is:

Code: Select all

guessthenextline

I know you
hate this :-)
hth
Suman

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

Post by midra » Tue May 11, 2004 2:35 am

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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Hi

Post by sumankar » Tue May 11, 2004 5:37 pm

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

Post Reply

Return to “Volume 102 (10200-10299)”