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

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok »

You are calling strlen() excessively ... looks like that's what's causing TLE.

-turuthok-
The fear of the LORD is the beginning of knowledge (Proverbs 1:7).

coolbila
New poster
Posts: 8
Joined: Tue Apr 01, 2003 8:11 pm

Post by coolbila »

thx
you are right :D
the cost of strlen() is expensive
Oh my God ... Wrong Answer

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

change your array to 100000. :wink:

keya
New poster
Posts: 3
Joined: Thu Jun 12, 2003 7:27 pm

Post by keya »

WA. What's wrong with my code? :(

[cpp]#include<stdio.h>
#include<string.h>
#define N 1000

char str1[N], str2[N];
long long i,j,len1,len2,no;

void main(void)
{
while(scanf("%s%s",&str1[0],&str2[0])==2)
{
len1 = strlen(str1);
len2 = strlen(str2);
i = j = no = 0;
if(len2<len1)
no = 1;
else
{
while(i<len1)
{
while(j<len2)
{
if(str2[j]==str1)
break;
j++;
}
if(j>=len2&&i<len1)
{
no = 1;
break;
}
i++;
}
}
if(no)
printf("No\n");
else
printf("Yes\n");
}
}[/cpp]

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

input:

Code: Select all

maaf matif
maaf mataf
output:

Code: Select all

No
Yes
good luck. :)

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

10340 RTE

Post by r.z. »

why is my code resulting RTE (SISVG)?

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

void main()
{
char a[10000];
char b[10000];
int i,j;
int len;

while(scanf("%s %s",a,b)!=EOF)
{
j=0;
len=strlen(a);
for(i=0;b!='\0';i++)
{
if(j==len)
{
break;
}
if(b==a[j])
{
j++;
}
}
if(j==len)
printf("Yes\n");
else
printf("No\n");
}

}[/c]

don't know why....

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka »

Code: Select all

char [100000]

r.z.
Learning poster
Posts: 56
Joined: Thu Jun 05, 2003 1:57 pm

Post by r.z. »

thanks

I got acc :wink:

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

10340 why my code is slower

Post by Morning »

the problem is Given two strings s and t, you have to decide whether s is a subsequence of t, i.e. if you can remove characters from t such that the concatenation of the remaining characters is s.

Sample Input

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

Sample Output

Yes
No
Yes
No

my code is

[cpp]
#include "iostream.h"
#include "string.h"
int main(int argc, char* argv[])
{
long long lo,loop1,loop2,flag;
char a[100000],b[100000];
while(cin>>a>>b)
{
if(strlen(a)>strlen(b))
{
cout<<"No"<<endl;
continue;
}
lo=0;
for(loop1=0;loop1<strlen(a);loop1++)
{
flag=0;
for(loop2=lo;loop2<strlen(b);loop2++)
{
if(b[loop2]==a[loop1])
{
flag=1;
lo=loop2+1;
break;
}
}
if(flag==0)
{
cout<<"No"<<endl;
break;
}
}
if(flag==1) cout<<"Yes"<<endl;

}
return 0;
}
[/cpp]
which got TLE
and there's someone else's code which can be AC and only use 0.001 second:
[cpp]
#include<stdio.h>
#include<string.h>

void main()
{
char a[100000];
char b[100000];
int i,j;
int len;

while(scanf("%s %s",a,b)!=EOF)
{
j=0;
len=strlen(a);
for(i=0;b!='\0';i++)
{
if(j==len)
{
break;
}
if(b==a[j])
{
j++;
}
}
if(j==len)
printf("Yes\n");
else
printf("No\n");
}

}
[/cpp]

i know i used tow "for" loop but i still think my code will spend the same time,because our algorithm seems the same:(
anyone who can tell me why mine is slower?
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

Post by Morning »

Oh.i got the answer.strlen() takes my code a lot of time:)
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

dalbertom
New poster
Posts: 1
Joined: Sun Apr 04, 2004 10:26 am

Post by dalbertom »

COUT's and CIN's are slower than PRINTF's and SCANF's, too :lol:

RodrigoPereira
New poster
Posts: 2
Joined: Mon May 17, 2004 9:36 pm

10340 why RTE?

Post by RodrigoPereira »

:cry: It runs ok, but the judge returns RTE (Illegal Memory Reference). Why???

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(){
  char * s = (char *)malloc(sizeof(char));
  char * t = (char *)malloc(sizeof(char));

  int i, tam, pos;
  char c;

  while (scanf("%s %s", s, t) != EOF){
    tam = strlen(s);
    pos = 0;
    for (i=0; i<tam; i++){
      c = s[i];
      while ((t[pos])&&(t[pos] != c))
        pos++;
    }

    if (t[pos])
      printf("Yes\n");
    else
      printf("No\n");

  }
  return 0;
}

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 »

You Have to use at least char array size of 1000000.
Use long as variable instead of int

Because pointer doesn't support that size.
Then u will not got RTE.
Hate WA
Visit phpBB!

RodrigoPereira
New poster
Posts: 2
Joined: Mon May 17, 2004 9:36 pm

Post by RodrigoPereira »

Thanx a lot, JoD! No more RTE!!! :lol:

...but i got WA :cry:

...does somebody have an input/output test?????

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 »

Try this input:
abbbbc abccccccccccc
Output:
No

But Yours is Yes.
Fix this, Then u will may got AC.
For further help you can mail me with ur code at:
nazmul_acm@yahoo.com

Wish u best of luck.
Hate WA
Visit phpBB!

Post Reply

Return to “Volume 103 (10300-10399)”