10252 - Common Permutation

[titid_gede]

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.

[Riyad]

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
Riyad

[Joseph Kurniawan]

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

[Sanghack]

if

aaA
AAa

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

"Is this problem is case-sensitive when compare two strings?"

[pavelph]

Given two strings of lowercase letters ...

Hope it helps you

[Tahseen Mohammad]

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]

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]

hmmm... looking at your code, what is your output for :

Code: Select all

z
z

-titid-

[WR]

Thanks a lot
while (1)

[koodeGuru]

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

[Larry]

Code: Select all

ab 
ba 

Should yield:

Code: Select all

ab

[koodeGuru]

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]

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]

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

[koodeGuru]

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