10324 - Zeros and Ones

[Professor_Of_Love]

So, how can I avoid TLE???? I haven't start Algorithm course... so can't I solve this without using Algo??? Thanks.

[turuthok]

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-

[Professor_Of_Love]

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

[ACoimbra]

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

A string is not more than an array of char

[junjieliang]

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]

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
readln(mystring);
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]

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

[raymond85]

simply use ansistring instead of string...
it gives u a string with dynamic size

var
s : ansistring;

[ACoimbra]

Isn't that too much slow?

[raymond85]

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.

[Riyad]

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
Riyad

[sidky]

About 10324:

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]

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

[Riyad]

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
Riyad

[Trickster]

Hi everyone,
i really dunno what