Page 4 of 11
Posted: Mon Oct 20, 2003 6:53 am
by 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.
10252
Posted: Thu Oct 23, 2003 6:15 pm
by 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
Posted: Wed Oct 29, 2003 7:59 am
by 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!! 
I still confused with...
Posted: Sat Jan 10, 2004 10:32 am
by 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?"
Read conditional
Posted: Sat Jan 10, 2004 11:48 am
by pavelph
Given two strings of lowercase letters ...
Hope it helps you
Posted: Sat Jan 10, 2004 1:09 pm
by 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.
10252
Posted: Mon Feb 02, 2004 10:14 am
by 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:
Posted: Mon Feb 02, 2004 5:20 pm
by titid_gede
hmmm... looking at your code, what is your output for :
-titid-
Posted: Tue Feb 03, 2004 9:13 am
by WR
Thanks a lot
while (1)
so messed up10252
Posted: Tue Apr 20, 2004 6:53 am
by 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
Posted: Tue Apr 20, 2004 7:30 am
by Larry
ab ba
Posted: Tue Apr 20, 2004 5:43 pm
by 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.
lower/upper
Posted: Tue Apr 20, 2004 7:01 pm
by 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?
this is too confusing an irritating
Posted: Tue Apr 20, 2004 7:12 pm
by koodeGuru
Each individual has his own opinions. I need some good advice here. Thanks.
some problems
Posted: Tue Apr 20, 2004 7:26 pm
by koodeGuru
