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

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

You have wrong understanding on the question.
For the input:

ab
ba

the output is:

ab

Actually this question can be solved easily once you udnerstand what it asks you to do.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

thank u, and sorry to disturb u.
i actually can't understand the problem.
it seems to me as a lcs prob.
i rarely put src. code in board. but sometimes when i can't get rid of a lot of wa, i become frustated and then put it.

please tell me abuot the problem and algrthm in a simpler way, please? :oops: :oops:
"Everything should be made simple, but not always simpler"

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

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

You miss the word permutation in the problem spec. That's why for the input

ab
ba

the output is

ab

because "ba" is a permutation of "ab" at all.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

[/b]thanks.
i rarely put src code.
i just want to know what will be the case if the input
abc
acd.
is it ac?
if it is then i have understood your help and the program.
thanks for help.
"Everything should be made simple, but not always simpler"

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Yes, that would be ac.

I also had this problem, I tried to solve it using LCS, and even sorted it before applying the LCS, but probably do to some quirks, gets AC, until I realize what it asks...

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam »

its not a problem of lcs.
those who think too much deeper must get wa in the problem.
but according to ..'s advice i revised the prob and got ac.
thanks ..
:P :P
"Everything should be made simple, but not always simpler"

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

10252 WA

Post by deddy one »

I got WA for 10252
could anyone tell me what's wrong with my code pls
thx in advance

[cpp] cut------



[/cpp]
Last edited by deddy one on Fri May 30, 2003 4:11 pm, edited 1 time in total.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

I experienced the same problem..

Post by Whinii F. »

from the problem statement we find:
That means in the input file line 1 and 2 is a set of input, line 3 and 4 is a set of input and so on.
The input strings include blank characters. Try using gets() instead of scanf().

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one »

thx whinii
but I still got WA though :cry:

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one »

pls help,

at least pls give me sample I/O for this problem.
:wink: :wink: :wink: :wink:

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one »

nevermind , I completely misunderstood what the problem really
wants.

got AC now.

route
New poster
Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

10252-- input problem

Post by route »

I tried to use cin.getline for input. Surprisingly, it stops after the blank lines. Why is it ?

Should I just use cin and !cnt.good to terminate the program ?

What makes difference ?

Taneem
New poster
Posts: 6
Joined: Thu Jun 05, 2003 6:26 pm
Location: Arkansas, USA

10252 - Common Permutation

Post by Taneem »

input: down
won

output: won or now ?

I am guessing it would be "now" since in the sample second test case ..

input: walking down
output: nw (and not wn)

I am just curious, for some reason I keep getting WA on this problem.
Give a man an answer, and he's satisfied today. Teach him to program, and he will be frustrated for the rest of his life. [Anonymous]

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy »

output for:

Code: Select all

down
won
is ...

Code: Select all

now
Greetings
Istiaque Ahmed [the LA-Z-BOy]

Taneem
New poster
Posts: 6
Joined: Thu Jun 05, 2003 6:26 pm
Location: Arkansas, USA

Post by Taneem »

thanks LA-Z-Boy. That's what I have too. Just cant figure out why I am not getting AC. it seems like an easy problem to me...

can u please give me some test cases?
Give a man an answer, and he's satisfied today. Teach him to program, and he will be frustrated for the rest of his life. [Anonymous]

Post Reply

Return to “Volume 102 (10200-10299)”