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

Post Reply
ABDULLAH
New poster
Posts: 1
Joined: Fri Dec 31, 2004 2:12 pm
Location: DHAKA,BANGLADESH

10324 TLE : tell me why

Post by 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 :roll:

Thank you![/quote]
IS NEWCOMER, IMPROVING EVERYDAY !

totster
New poster
Posts: 4
Joined: Sun Dec 12, 2004 12:28 pm

Re: 10324 TLE : tell me why

Post by 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
A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta
Contact:

Post by 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 :wink:

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
New poster
Posts: 7
Joined: Sat Jan 22, 2005 6:43 pm

10324

Post by 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....>_<

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Re: HELP IN 10324

Post by .. »

akiha wrote: 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:
akiha wrote: I have dual with it for 2 days....>_<
I know you still have few more days :)
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim »

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

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by 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.
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim »

Ivor wrote:Without assembler, in pure C, with serious IO and data representation optimizations.
I.
Please write details. Because I am very beginer. :D

Ibrahim

typezero
New poster
Posts: 1
Joined: Sun Mar 06, 2005 3:08 am

10324 Runtime Error

Post by 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
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

??

Post by 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 ?
Some Love Stories Live Forever ....

ibrahim
Experienced poster
Posts: 149
Joined: Mon Feb 07, 2005 10:28 pm
Location: Northern University, Bangladesh
Contact:

Post by ibrahim »

Raj Ariyan wrote: 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
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

10324 : Why Compiler Error ... Why..

Post by 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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by 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
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

Post by Rocky »

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

Thank's in Advance
Rocky

Rocky
Experienced poster
Posts: 124
Joined: Thu Oct 14, 2004 9:05 am
Contact:

ACC At Last

Post by Rocky »

Yehaa.

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

Thank's
Rocky

Post Reply

Return to “Volume 103 (10300-10399)”