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

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 »

one of the main reason of not getting accepted is the input of blank lines...
Input file contains several lines of input. Consecutive two lines make a set of input. 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.
so the input might well look like...

Code: Select all

abc

efg


ghi
and output is obvious, three newline characters...

Code: Select all


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 a lot La-Z-Boy. I should have paid attention to that clause. I got AC (finally).

I appreciate your help.
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]

hujialie
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

Post by hujialie »

I think this problem has some mistakes in statement.

In the problem:
It says:
Each string is on a separate line and consists of at most 1000 lowercase letters
But when I used scanf("%s") to read input and just considered the lowercase letters,I got wrong answer.
Then I changed to all ASCII characters and used gets() ,eventually I got accepted.

So the statement is incorrect.
Retired from SJTU Accelerator 2004

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf »

if I have input

pretty woman
walking down

what is the output?


thanks.

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

hi, have you forgive me yet?? Please forgive me

Post by Nick »

There are blank characters in the input and also maybe uppercase letters, which to be sorted alphabetically

Read previous post about this

input

prettywoman
walkingdown
inging
singing

the output should be

anow
ggiinn
Last edited by Nick on Wed Aug 13, 2003 4:00 am, edited 1 time in total.

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

Post by Larry »

Well, it *could* be a LCS.. but that's the same as using dynamic program when greedy would do.. (overkill)...

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Why I must forgive u?

Post by b3yours3lf »

uppercase letter?
so if the output is aC what should I print?
aC or Ca ?
Last edited by b3yours3lf on Wed Aug 13, 2003 6:47 am, edited 1 time in total.

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

Post by Larry »

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.

Nick
Learning poster
Posts: 53
Joined: Sun Jan 12, 2003 4:49 am

Post by Nick »

read about the previous post by hujialie...
I was getting WA when i use ASCII comparison...and when I consider the alphabetic order i got AC

input
Ca
Ca

the output should

aC

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

Post by Larry »

I used tolower and return

Code: Select all

ac
and:

Code: Select all

aaAAaaAAAa
aaAAaaAAAa
returns:

Code: Select all

aaaaaaaaaa
and still AC.

Miguel Correia Ricardo
New poster
Posts: 9
Joined: Sat Nov 30, 2002 4:09 am
Contact:

10252 WA WHY?!

Post by Miguel Correia Ricardo »

What's wrong with my code?
It passes all the test i've seen in the bulletin board...

[cpp]
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void permutation(string& a, string& b, string& result){
for (unsigned int i = 0; i < a.length(); i++)
if ((b.find(a) != string::npos))
result +=a;

sort(result.begin(), result.end());
}

int main(){
string a;
string b;
string result;
cin.setf(ios::skipws);

while(getline(cin, a) && getline(cin, b)){
permutation(a,b, result);
cout << result << endl;
a.erase();
b.erase();
result.erase();
}

return 0;
}


[/cpp]

Thank you to all that can help me
Thanks,
Miguel Correia Ricardo
E_mail:miguel_ricardo@hotmail.com

Miguel Correia Ricardo
New poster
Posts: 9
Joined: Sat Nov 30, 2002 4:09 am
Contact:

I've donne some corrections

Post by Miguel Correia Ricardo »

Hi, i've donne some corrections, but still it gives me WA, but why...

[cpp]
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(){
string a;
string b;
string result;

cin.setf(ios::skipws);

while(cin >> a >> b){
result.resize(1000);

transform(a.begin(), a.end(), a.begin(), tolower);
transform(b.begin(), b.end(), b.begin(), tolower);
sort(a.begin(), a.end());
sort(b.begin(), b.end());

set_intersection(a.begin(), a.end(), b.begin(), b.end(), result.begin());

cout << result << endl;

a.erase();
b.erase();
result.erase();
}

return 0;
}

[/cpp]
Thanks,
Miguel Correia Ricardo
E_mail:miguel_ricardo@hotmail.com

Daredevil
New poster
Posts: 19
Joined: Tue Apr 01, 2003 7:47 am
Location: Earth

Post by Daredevil »

Mine gives WA too. Here's my code:

[c]
#include<stdio.h>
#include<string.h>
int i,min,s[30],s1[30];
char a[1002],b[1002];
void main(){
while(scanf("%s %s",&a,&b)==2){
memset(s,0,sizeof(s));
memset(s1,0,sizeof(s1));
for(i=strlen(a)-1;i>=0;i--) s[a-97]++;
for(i=strlen(b)-1;i>=0;i--) s1[b-97]++;
for(i=0;i<26;i++){
if(s&&s1){
min=s;
if(min>s1) min=s1;
while(min){
printf("%c",i+97);
min--;
}
}
}
printf("\n");
}
}
[/c]

Can anybody tell me what's wrong?
Thanx in advance!!

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan »

Yeah, I got the same problem like you. But after I change scanf("%s"); with gets();, I got AC. Apparently each string doesn't only contain lowercase letter. The problem didn't mention this!!! :evil: :evil:
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK »

Although there is a much simpler solution to this problem I also started solving it with Longest Common Subsequence algorithm. On my computer it works perfectly OK producing the write answer of tons of input. But the OJ says WA.

The simpler solution is accepted only if you process the input reading lines. It seems that the judge's input data is incorrect.

DID ANYBODY OF YOU GET ACCEPTED USING THE LCS ALGORITHM?

Post Reply

Return to “Volume 102 (10200-10299)”