10252  Common Permutation
Moderator: Board moderators

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
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=n1;
while(low<=high){
mid=(low+high)/2;
if(x<p[mid])
high=mid1;
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
Riyad
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=n1;
while(low<=high){
mid=(low+high)/2;
if(x<p[mid])
high=mid1;
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
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

 Experienced poster
 Posts: 136
 Joined: Tue Apr 01, 2003 6:59 am
 Location: Jakarta, Indonesia
Hello Riyad,
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!!
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.
I still confused with...
if
aaA
AAa
returns
aaa or aa (case sensitive, one a and one A)
"Is this problem is casesensitive when compare two strings?"
aaA
AAa
returns
aaa or aa (case sensitive, one a and one A)
"Is this problem is casesensitive when compare two strings?"
A farmer learns more from a bad harvest than a good one.

 Learning poster
 Posts: 57
 Joined: Wed Dec 10, 2003 7:32 pm
 Location: Russia, SaintPetersburg
Read conditional
Hope it helps youGiven two strings of lowercase letters ...

 Learning poster
 Posts: 54
 Joined: Sun Oct 28, 2001 2:00 am
 Location: Bangladesh
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.
sample input:
sample output:
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;
}
Code: Select all
pretty
women
walking
down
the
street
ab
ba
abc
acd
down
won
prettywoman
walkingdown
inging
singing
abc
efg
ghi
a
a
Code: Select all
e
nw
et
ab
ac
now
anow
ggiinn
a

 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 :
titid
Code: Select all
z
z
Kalo mau kaya, buat apa sekolah?
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.
Thankz in advance.

Boooooo to OJ for java
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.
Thankz in advance.

Boooooo to OJ for java

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
Code: Select all
ab
ba
Code: Select all
ab
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.
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.
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
this is too confusing an irritating
Each individual has his own opinions. I need some good advice here. Thanks.
some problems
If no characters are entered my program just exits.Is that ok??