Page 4 of 12

Posted: Wed Apr 02, 2003 8:32 pm
by 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.

Posted: Wed Apr 02, 2003 8:55 pm
by 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-

Thanks, turuthok!

Posted: Thu Apr 03, 2003 8:41 am
by Professor_Of_Love
turuthok, thanks. I have started thinking in your way... Thanks again!

define the size

Posted: Thu Apr 10, 2003 2:32 pm
by 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 ;)

Posted: Thu Apr 10, 2003 3:23 pm
by 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);

Posted: Thu Apr 10, 2003 7:46 pm
by 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.

delphi mode

Posted: Sat Jun 14, 2003 12:53 pm
by ACoimbra
you can activate delphi mode, so you will have strings with dynamic size :roll:

Posted: Tue Jul 01, 2003 9:15 pm
by raymond85
simply use ansistring instead of string...
it gives u a string with dynamic size

var
s : ansistring;

hmn

Posted: Tue Jul 01, 2003 9:20 pm
by ACoimbra
Isn't that too much slow? :o

Re: hmn

Posted: Wed Jul 02, 2003 11:25 am
by raymond85
ACoimbra wrote:Isn't that too much slow? :o
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.

10324

Posted: Sun Oct 12, 2003 1:37 pm
by 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

Posted: Mon Oct 13, 2003 8:20 am
by 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.

Posted: Mon Oct 13, 2003 11:06 am
by 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... ;)

hey man got 10340 aC

Posted: Mon Oct 13, 2003 4:00 pm
by 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 :wink:
Bye
Riyad

10324 WA

Posted: Tue Oct 14, 2003 6:02 am
by Trickster
Hi everyone,
i really dunno what