10340 - All in All

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

roaraujo
New poster
Posts: 7
Joined: Wed May 26, 2004 2:43 pm

10340 WA

Post by roaraujo »

Why WA in 10340?!

My code:

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

int main()
{
char s1[10002], s2[10002];
int size_s1, size_s2, cont, i;

while(scanf("%s %s", s1, s2) != EOF){
size_s1 = strlen(s1);
size_s2 = strlen(s2);
cont=0;
for(i=0; i < size_s2; ++i){
if(cont < size_s1)
if(s2 == s1[cont]){
cont++;
}
}
if(cont == size_s1)
printf("Yes\n");
else
printf("No\n");
}

return 0;
}
[/c]

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by Jewel of DIU »

use 1000000 as array size.
Hate WA
Visit phpBB!

roaraujo
New poster
Posts: 7
Joined: Wed May 26, 2004 2:43 pm

Post by roaraujo »

Thank you my friend! Acc! :D

midra
Experienced poster
Posts: 119
Joined: Fri Feb 13, 2004 7:20 am
Contact:

10340(ALL in ALL) WA.

Post by midra »

This seems to be an easy problem but I can't figure out why my code doesn't work
maybe there is some special case that I haven't think it.
here is my code:

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

int main()
{
char s[150],t[150];
int i,j;
int temp;
while(scanf("%s %s",&s,&t)!=EOF)
{
temp=0;
j=0;
for(i=0;i<=strlen(s)-1;i++)
for (;j<=strlen(t)-1;j++)
if (s==t[j])
{
temp++;
break;
}
if (temp==strlen(s))
printf("Yes\n");
else
printf("No\n");
}
return 0;
}[/c]

thx for reading!

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10340 - WA. Help me!

Post by medv »

I read a lot about 10340, written in this forum
I use char of 1000000, I use long.
My program is clear. But I can't find a mistake
Help me, please!
I do not want to use two char arrays of size 1000000,
I use only one. So I use getchar().
I use scanf("\n") to pass eoln symbol. It works right.

Help! Why WA????

#include <stdio.h>
char line[1000000];

int main(void)
{
long i,len;
char c;
while (!feof(stdin))
{
len = 0;
while ((c = getchar())!= ' ') line[len++] = c;
i = 0;
while ((c = getchar())!= '\n')
if (c == line[i]) i++;
if (i == len) printf("Yes\n");
else printf("No\n");
scanf("\n");
}
return 0;
}

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Try the input
ab ab
a ab

Your output is
Yes
No

Try the two test cases in this order! I think you can guess what is wrong.

birdegg
New poster
Posts: 6
Joined: Wed Jan 05, 2005 10:42 pm

10340 -All in All -WA always.

Post by birdegg »

I don't understand why i got WA
can somebody give me a set of inputs..?
thanks a lot

Code: Select all

#include <stdio.h>
#include <string.h>
#define MAX 50000

int main(){
	char s[MAX],t[MAX];
	unsigned long i,j,lens,lent;

	while(scanf("%s %s",s,t)==2){
                         .......
	}
		
}
Last edited by birdegg on Thu Jan 06, 2005 8:55 am, edited 1 time in total.

neowarez
New poster
Posts: 14
Joined: Tue May 06, 2003 11:04 pm
Location: Portugal
Contact:

Your code is OK

Post by neowarez »

Your code is OK..

The problem its your array size .. put one more zero on MAX.
Neo

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

ARAY SIZE

Post by Rocky »

YES YOUR CODE IS OK BUT FOR THE ARRAY SIZE....
I GET ACC BY 100000 SIZE OF ARRAY TRY IT

GOOD LUCK

birdegg
New poster
Posts: 6
Joined: Wed Jan 05, 2005 10:42 pm

Post by birdegg »

YA...! I got AC now.
thanks for your help :D

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

I am just wondering what is the best
algorithm for solving this problem.

I do the following:

1) I take the two strings and name them strX and strY.
Let's denote their lengths by LenX and LenY respectively.

2) I calculate the length N of the
Longest Common Subsequence ( LCS ) of strX and strY.

3) Then I check if N is equal to the length of the first
string strX. If so, I print "Yes", otherwise I print "No".

Roughly speaking the algorithm I've implemented for finding the
length of the LCS of strX and strY uses O(LenX+LenY) memory and
spends O(LenX*LenY) running time. Here LenX and LenY and the lengths
of strX and strY respectively.

Can the running time complexity be improved ?
Memory concerns me less for the moment.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Apparently my algorithm does too much.

For that problem I saw a lot of people getting ACC with
running time under 0.010 sec.
My running time is about 0.500 sec. :)

So apparently there's some much more efficient algotihm
for solving this one. Any hints about it ?

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho »

Apparently my algorithm does too much.

For that problem I saw a lot of people getting ACC with
running time under 0.010 sec.
My running time is about 0.500 sec. :)

So apparently there's some much more efficient algotihm
for solving this one. Any hints about it ?

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

Post by Larry »

Note that only 0's and 1's appear, so you can preprocess the array for queries in some way..

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

Sedefcho wrote:Apparently my algorithm does too much.
I think so, too. Note that you only need to find the presence of a subsequence not the length of the LCS. My [len (X) * len (Y)] brute force solution times 0.008 sec.
You should never take more than you give in the circle of life.

Post Reply

Return to “Volume 103 (10300-10399)”