10324 - Zeros and Ones

Moderator: Board moderators

Professor_Of_Love
New poster
Posts: 9
Joined: Tue Apr 01, 2003 10:03 pm
So, how can I avoid TLE???? I haven't start Algorithm course... so can't I solve this without using Algo??? Thanks.

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
I think the logic behind this problem is very very simple ... neither special algorithms nor courses required. The problem is also cleverly design to somehow drag our focus to 0-1 binary world. In fact, eventhough each digit can contain [0-9] or [a-z], the solution will still be the same ...

During the contest, I use a variable called changes that will increment each time we see a digit-change. Then, I keep that information in such a way so that for every given query I can just print "Yes" and "No" immediately ...

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

Professor_Of_Love
New poster
Posts: 9
Joined: Tue Apr 01, 2003 10:03 pm

Thanks, turuthok!

turuthok, thanks. I have started thinking in your way... Thanks again!

ACoimbra
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

define the size

Hi,
you can also set the size of the string, like
yourstring: string(10000);

A string is not more than an array of char
Last edited by ACoimbra on Thu Apr 10, 2003 3:50 pm, edited 1 time in total.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I think with GPU a string can have max length of 32767, but I'm not too sure about that with FreePascal. Declaration is done with curve brackets:

var s : string(32767);

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
With the new free pascal compiler you can use the string type ansistring that can be virtualy as long as you like.
[pascal]var
mystring:ansistring;
begin
end.[/pascal]reads until it encounters an EOLN, even if it has to read thousands or millions of characters.
You can also use the procedure setlength() to explicitly allocate memory, like:[pascal]setlength(mystring,2000000000);[/pascal]
Memory is allocated dynamically.
There are some restrictions; read the FPC documentation for details.

ACoimbra
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

delphi mode

you can activate delphi mode, so you will have strings with dynamic size

raymond85
New poster
Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong
Contact:
simply use ansistring instead of string...
it gives u a string with dynamic size

var
s : ansistring;

ACoimbra
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

hmn

Isn't that too much slow?

raymond85
New poster
Posts: 21
Joined: Tue Jul 01, 2003 9:26 am
Location: Hong Kong
Contact:

Re: hmn

ACoimbra wrote:Isn't that too much slow?
Of coz, if you are storing a long string that uses a lot memory, I think it might slow down the processing speed. By the way I think it's acceptable, I used it instead of array of character many times when doing ACM problems and got AC without much different on the processing speed.

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

10324

the following code of 10324 fetches me TLE . i used a very simple brute force algorithm. pliz tell me any other good algorithm , if is there?,. here is my code for 10324.

Code: Select all

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

#define max(a,b) ((a)>(b)? (a): (b))
#define min(a,b) ((a)>(b)? (b):(a))

int CheckTheInformation(char input[],long int x , long int y){

long int i ;//long long int(used while sending to the judge )
int count;

count=input[x];

for(i=x+1;i<=y;i++){

if(input[i]==count)
continue;
else
return 0;

}

return 1;

}

int main(){

char input[1000002];
char xtra[50];
int cases,flag,count;
long int i , j;//long long int(used while sending to the judge )

cases=1;

while(gets(input)){

if(strcmp(input," ")==0 || strcmp(input,"\n")==0)
break;

gets(xtra);
sscanf(xtra,"%d",&count);

printf("Case %d:\n",cases);

while(count>0)
{
gets(xtra);
sscanf(xtra,"%ld %ld",&i,&j);//long long int

flag=CheckTheInformation(input,min(i,j),max(i,j));

if(flag==0){
printf("No\n");
}
else
printf("Yes\n");

count--;

}

cases++;

}

return 0;
}``````

on the other hand my code for 10340 fetches me WA . the algorithm of mine is very simple , i cant find any mistakes in the code . pliz help .
here is the code for 10340
[c]
#include<stdio.h>
#include<string.h>

int CheckForSubSequence(char in1[],char in2[]){

int i , c , flag,j;

if(strlen(in1) > strlen(in2)){

return 1;

}

else if(strlen(in1)==strlen(in2)){

return strcmp(in1,in2);
}
else{

for(i=0,c=0;in1!='\0';i++){

flag=1;
for(j=c;in2[j]!='\0';j++){

if(in1==in2[j]){
c=j;
flag=0;
break;
}

}

if(flag==1)
return 1;
else
continue;

}

return 0;

}

}

int main(){

char input[10000];
char in1[1000],in2[1000];
int Flag;

while(gets(input)){

sscanf(input,"%s %s",in1,in2);
Flag=CheckForSubSequence(in1,in2);

if(Flag==0){
printf("Yes\n");
}
else
printf("No\n");
}

return 0;
}[/c]

pliz help me
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

You cant avoid TLE if you use such search. Try using better search method. Remember that, you only have to consider whether the digits between ith and jth are the same, u dont have to know, whether they are zero or one.

the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Contact:
for p10340 (All in All):
1. buffers are too small... take something upto 1000000 (that's what i took, lesser might work. but never with 1000 at least!)
2. still another mistake is in your checking function. try to find it... for this you must fail for input...

Code: Select all

``abbbbbbc abcccccccccccccccccc``
where your prog outs "Yes"... and should be "No"
you'll know why...
Istiaque Ahmed [the LA-Z-BOy]

Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

hey man got 10340 aC

hey man so care less of me about 10340 (all in all ). i got it right , there was a mistake in the check function . i should initialize c with -1 . and instead of making j =c i should have made j=c+1.some how got it right .
and about 10324 i am trying a new algorithm for searching . special thanx to laz boy
Bye