10324 - Zeros and Ones

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

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

Post by Professor_Of_Love » Wed Apr 02, 2003 8:32 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:

Post by turuthok » Wed Apr 02, 2003 8:55 pm

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
Location: Dhaka, Bangladesh

Thanks, turuthok!

Post by Professor_Of_Love » Thu Apr 03, 2003 8:41 am

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

Post by ACoimbra » Thu Apr 10, 2003 2:32 pm

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

Post by junjieliang » Thu Apr 10, 2003 3:23 pm

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);

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Apr 10, 2003 7:46 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
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
New poster
Posts: 14
Joined: Thu Apr 10, 2003 1:59 pm
Location: Coimbra, Portugal
Contact:

delphi mode

Post by ACoimbra » Sat Jun 14, 2003 12:53 pm

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

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

Post by raymond85 » Tue Jul 01, 2003 9:15 pm

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

Post by ACoimbra » Tue Jul 01, 2003 9:20 pm

Isn't that too much slow? :o

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

Re: hmn

Post by raymond85 » Wed Jul 02, 2003 11:25 am

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.

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

10324

Post by Riyad » Sun Oct 12, 2003 1:37 pm

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

Post by sidky » Mon Oct 13, 2003 8:20 am

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.

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Post by the LA-Z-BOy » Mon Oct 13, 2003 11:06 am

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]

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

hey man got 10340 aC

Post by Riyad » Mon Oct 13, 2003 4:00 pm

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
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

User avatar
Trickster
New poster
Posts: 6
Joined: Sat Sep 20, 2003 6:31 am
Location: Recife, Brazil

10324 WA

Post by Trickster » Tue Oct 14, 2003 6:02 am

Hi everyone,
i really dunno what
"There's a difference between knowing the path, and walking the path."

Post Reply

Return to “Volume 103 (10300-10399)”