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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
no, as told from previous post, this is NOT an lcs problem. btw, this problem is much much simpler than lcs
i think the chance of getting WA is very high when you use lcs algo to solve this prob.
Kalo mau kaya, buat apa sekolah?

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10252

every one said the problem 10252 is a very easy one . but i am having real trouble with that , i am having wa all the time . i visited all the topics about this prob in this board and tried to cover all the mistakes . did i miss some thing .

here is my code , plizzzzzzzzz do help me in this:

[c]#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void MyLowerFunction(char *p, char *q){

int i ;

for(i=0;p!='\0';i++){

p=tolower(p);

}

for(i=0;q!='\0';i++){

q=tolower(q);

}

}

void BubbleSort(char *p){

int i ,j,temp;
int n;

n=strlen(p);

for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
if(p>p[j]){

temp=p;
p=p[j];
p[j]=temp;
}
else
continue;

}

}

}

int BinSearch(char x , char *p, int n ){

int low,high,mid;

low=0;
high=n-1;

while(low<=high){

mid=(low+high)/2;

if(x<p[mid])
high=mid-1;
else if(x>p[mid])
low=mid+1;
else
return mid;

}
return -1;

}

void check(char *p,char *q , char *r){

int i ,index, j;

index=0;

if(strlen(p)<strlen(q)){

for(i=0;p!='\0';i++){

j=BinSearch(p[i],q,strlen(q));

if(j!=-1){

r[index++]=p[i];

}
else
continue;

}

}
else{

for(i=0;q[i]!='\0';i++){

j=BinSearch(q[i],p,strlen(p));

if(j!=-1){

r[index++]=q[i];

}
else
continue;

}

}
r[index]='\0';

}

int main(){

char input1[1001],input2[1001];
char output[1001];

while(gets(input1)){

gets(input2);

MyLowerFunction(input1,input2);

BubbleSort(input1);
BubbleSort(input2);

check(input1,input2,output);
puts(output);

}

return 0;

}[/c]

plizzzzzzzzzzz tell me , why i am having wa all the time .
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Joseph Kurniawan
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
Your algo seems very complex for this prob.
I suggest you to use this method:
1. Handle input using gets(). --> you've done this
2. Use temp1 and temp2 respectively to evaluate string1 and string2.
3. Use this function:
[c]
for(i=0, j=strlen(string1) ; i<j ;i++){
if(string1<97) string1+=32;
temp1[string1]++;
}

for(i=0, j=strlen(string2) ; i<j ;i++){
if(string2<97) string2+=32;
temp2[string2]++;
}

for(i=97;i<123;i++){
if(temp1&&temp2){
if(temp1<temp2) j=temp1[i];
else j=temp2[i];
while(j){
printf("%c",i);
j--;
}
}
}
[/c]

Hope this helps!!
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.

Sanghack
New poster
Posts: 16
Joined: Wed Jul 17, 2002 5:55 pm
Location: Seoul, Korea

I still confused with...

if

aaA
AAa

returns
aaa or aa (case sensitive, one a and one A)

"Is this problem is case-sensitive when compare two strings?"
A farmer learns more from a bad harvest than a good one.

pavelph
Learning poster
Posts: 57
Joined: Wed Dec 10, 2003 7:32 pm
Location: Russia, Saint-Petersburg

Given two strings of lowercase letters ...
Hope it helps you

Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Why is everyone making such fine input of mixing upper/lower case
character. The problem spec is clear in saying lowercase alphabet.

Hint: if you are killing yourself with LCS or can't understand the problem
Its as easy problem as counting character frequency.
Did I give away TOO MUCH.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

10252

Hi,

even after reading all posts and changing my program
accordingly I get a WA.

Stupid error somewhere - but where?

I know the program is not elegant but it should work.

May be somebody can point out the error.

Code: Select all

``````#include <stdio.h>                     /* printf */
#include <string.h>                    /* strlen */

/*******************************
* ACM Contest - Problem 10252 *
*******************************/

int min(int a, int b)
{
if (a < b)
return a;
else
return b;
}

int main(void)
{
char sta[2001], stb[2001];
int frqa[26], frqb[26];
unsigned int i, l1, l2;
int j, c;
while (1){
if (gets(sta) == NULL) goto fim;
gets(stb);
l1 = strlen(sta);
l2 = strlen(stb);
if ((l1 < 1) || (l2 < 1)){
printf("\n");
continue;
}
for (i=0;i<26;i++){frqa[i] = frqb[i] = 0;}
for (i=0;i<l1;i++){
c = sta[i] - 'a' + 1;
if ((c >= 0) && (c < 26))
frqa[c]++;
}
for (i=0;i<l2;i++){
c = stb[i] - 'a' + 1;
if ((c >= 0) && (c < 26))
frqb[c]++;
}
for (i=0;i<26;i++)
if ((frqa[i] > 0) && (frqb[i] > 0))
for (j=0;j<min(frqa[i],frqb[i]);j++)
printf("%c",i+96);
printf("\n");
}
fim:
return 0;
}``````
sample input:

Code: Select all

``````pretty
women
walking
down
the
street
ab
ba
abc
acd
down
won
prettywoman
walkingdown
inging
singing
abc

efg

ghi
a
a
``````
sample output:

Code: Select all

``````e
nw
et
ab
ac
now
anow
ggiinn

a
``````

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
hmmm... looking at your code, what is your output for :

Code: Select all

``````z
z
``````
-titid-
Kalo mau kaya, buat apa sekolah?

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am
Thanks a lot
while (1)

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

so messed up10252

This discussion totaly confuses me and OJ for java suczs
Anyhow it is'nt that bad. I am a beginner may be thats why i feel it that way.As far as prob10252 is concerned? what is the exact logic behind it?
So far what I have understood from this discussion is:

For any two given input string we are only creating a string x such that permutation of the sequence x is only a subsequence of both input strings and not the whole sequence.

Ex input:
ab
ba
acm
ocm
acacm
ococma

Ex output:

cm
accm

Am I correct in my understanding of this problem? Please someone reply.
------------------------------------------------------------------------------
Boooooo to OJ for java

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

Code: Select all

``````ab
ba ``````
Should yield:

Code: Select all

``ab``

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

ab ba

How is it possible?
ab
ba

Now from that given input we are supposed to form a string x such that a permutation of x is a subsequence of string1 and string2.Now if you say the answer is ab then I would say thats wrong according to the given specifications since ab has only two permutations an namely ab and ba which are not realy subsequences of the input string rather strings themselves. Can someone clarify? If you say ab is a subsequence of ba and ba a subseq of ab then that does not make any sense to me. Thanks in advance.

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

lower/upper

One more thing there are lot of comments concerning the format of the input. Some people say input has uppercase letters too but problem spec clearly says lower case letters only. Do I have to check for uppercase too?

Code: Select all

``````Ca
Ca
``````

Code: Select all

``````ac
``````

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

this is too confusing an irritating

Each individual has his own opinions. I need some good advice here. Thanks.

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

some problems

If no characters are entered my program just exits.Is that ok??