10324 - Zeros and Ones

[ABDULLAH]

I've got TLE from the judge, but I tested the program at home O.K.

Why I am getting TLE :

1. because of my program does not terminate

OR

2. because of my program cannot process the numerous test cases in time.

Please give me a suggestion, Here is my Code:

Code: Select all

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

void main()
{
char c[1000001],last,ch;

unsigned long i,j,n,temp;

int cas=0,flag,casflag,newline,k=0;;

while(1)
{

while(1)
{
if(scanf("%c",&ch)==EOF)goto exit;

if(ch=='\n')
{
if(newline==2)goto exit;
else if(newline!=1){ newline++; c[k]='\0'; k=0; break; }
newline++;
}

else { newline=0; c[k]=ch; k++; }
}

if(!strlen(c))break;

scanf("%lu",&n);
casflag=1;
cas++;

while(n)
{
scanf("%lu %lu",&i,&j);

if(i>j){ temp=i; i=j; j=temp; }

if(casflag==1)printf("Case %d:\n",cas);
casflag=0;

flag=0;
last=c[i];

for(temp=i;temp<=j;temp++)if(c[temp]!=last){ flag=1;break; }

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

n--;
}

}
exit:
}

Waiting for a reply

Thank you![/quote]

[totster]

Your code takes too long to run. Each query of (i,j) takes max(i,j)-min(i,j) time which is potentially 1000000 each. Consider some sort of memoization to reduce your query time.

[sumankar]

Hi Abdullah,

I had not solved 10324 before.Only after coming across this post I tried it out, with the naivest solution that laziness permitted.Strangely it was within the time limit.

1. I did not go through your code, but a quick glance tells me you are using too many conditions which eats up time.Do away with them.

A hint:You should have heard about the following -
[c]
#include <string.h>
void *memchr(const void *s, int c, size_t n);
[/c]
Try to use it judiciously.My code is only 24 lines long

2. Do not use labels with names that clash with function names as you have done (exit), it really obscures your code at times.And is not a good coding style.

Regards,
Suman.

[akiha]

I try to sove it
and give a exactly correct answer but get time limit exceed

i know what's wrong with my program
As i learn C for only 2 weeks and only learn programming for 3months

my library of synatx is very week
the only method i know how to solve it is to loop the char one by one by conditional loop
this must cause time limit exceed as it possible try 1000000 case!

but in fact i dont know how to use other method

does anyone can give me some homepage about more intensive knowledge about C and also some idea about it

I have dual with it for 2 days....>_<

[..]

i know what's wrong with my program
As i learn C for only 2 weeks and only learn programming for 3months

does anyone can give me some homepage about more intensive knowledge about C and also some idea about it

Your problem is you don't have idea on algorithm, not you don't know syntax of C, don't mix these 2 things together. There will not exist some "advanced syntax" which can help you kill the problem.

I don't think "learn programming for 3 months only" is an excuse, many of your classmates also in the same status as you. It is the problem if you try to think or not. If you get the correct algorithm, I promise you can code it with your "libray of syntax".

A basic idea to solve the problem, is to do some pre-processing after you read the long string. The pre-processing can help you to solve each query in O(1) time. If you still want more hints, use the "search' function above, you will find many thread talking about this problem directly.

However, I suggest you think you about yourself first. The preprocessing isn't so complicate.......

By the way, don't say this:

I have dual with it for 2 days....>_<

I know you still have few more days

[ibrahim]

I solve this problem with 0.141 seconds . Anyone can tell me, how can it possible to solve this with 0.033 seconds.

[Ivor]

Without assembler, in pure C, with serious IO and data representation optimizations. No more than that. (And I won't tell what exactly.) It took me a while to come to this solution. I picked this problem up not so long ago after not touching it for at least 1.5 years. Before that my time was about 0.080.

I.

[ibrahim]

Without assembler, in pure C, with serious IO and data representation optimizations.
I.

Please write details. Because I am very beginer.

Ibrahim

[typezero]

Hi,

I can't figure out why I get runtime error :/ can anyone give me a hint?

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>

using namespace std;
	
int main()
{
	string input;
	vector <unsigned long int> sum;
	unsigned long int i,j,number,tempint,x;
	unsigned long int case_number = 1;
	char caracter;
	bool firstime = true;
	
	sum.reserve(1000001);
	
	while(!feof(stdin))
	{
		if(!firstime)
			getchar();
		else
			firstime = false;
		
		if((caracter = getchar()) == '\n')
			return 0;
			
	  input.push_back(caracter);
		sum[0] = caracter - 48;
		x = 1;
		
		while((caracter = getchar()) != '\n')
		{
			input.push_back(caracter);
			sum[x] = caracter - 48 + sum[x-1];
			x++;
		}
		
		cin >> number;
		
		cout << "Case " << case_number++ << ":" << endl;		
				
		for(x = 0; x < number; x++)
		{
			cin >> i >> j;
			
			if(i > input.size() || j > input.size())
				cout << "No" << endl;
			else
			{
				if(i > j)
				{
					tempint = j;
					j = i;
					i = j;
				}
				
				if(input.at(i) == '0')
					if(sum[i] == sum[j])
						cout << "Yes" << endl;
					else
						cout << "No" << endl;
				else
					if(sum[j]-sum[i] == j-i)
						cout << "Yes" << endl;
					else
						cout << "No" << endl;
			}
		}
		
		input.erase(input.begin(),input.end());
	}
	
	return 0;
}

[Raj Ariyan]

Hi Ibrahim,

Think abt it....

Suppose one input will be:-
10111001
make a array in such a way(its upto u to implement) such that it holds :-
12333445 << your array for those input

Now if u ask for
1 3 --> then just check arr[1]==arr[3] if true then print yes else no

Do u get any idea ?

[ibrahim]

Do u get any idea ?

Thanks for your answere.

I use this process. But it takes 0.141
Any body, want to say some thing???

Ibrahim

[Rocky]

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

#define max 1000000

int main(void)
{
char input[max],c;
int i,j,i_j,caseno,t_c,t1,t2,not=0,test,temp;
caseno=0;

while(scanf("%s",input)!=EOF)
{
temp = strlen(input);
if(temp==0)
break;
caseno++;
scanf("%d",&test);
printf("Case %d:\n",caseno);
for(t_c=1;t_c<=test;t_c++)
{
scanf("%d%d%c",&i,&j,&c);
not=0;

t1= (i>j)?i:j;
t2= (i<j)?i:j;

if(t2>temp)
{
printf("No\n");
continue;
}

for(i_j=t1;i_j<t2;i_j++)
{
if(input[i_j]!=input[i_j+1])
{
not=1;
break;
}
}

if(not) printf("No\n");
else printf("Yes\n");
}
}
return 0;
}

Can Any Body Help Me?

Thank's IN Advance
Rocky

[shamim]

int i,j,i_j,caseno,t_c,t1,t2,not=0,test,temp;

you are using a variable name not, change it to a different name. not is actually an operator. e.g if (not i), meaning if ( !i)

[Rocky]

I Change It And Got TLE Why???
What Is The Efeicient Way To Solve It.
Need Help.

Thank's in Advance
Rocky

[Rocky]

Yehaa.

Got It.I Got Acc At Last.Thank's To Shamim
Shamim Can i Get Your Email Adress.

Thank's
Rocky