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
User avatar
J&Jewel
New poster
Posts: 50
Joined: Thu Jul 31, 2003 10:43 am
Location: Daffodil University,Dhaka,Bangladesh
Contact:

Post by J&Jewel » Wed Apr 27, 2005 1:29 pm

Please do not new post the same number problem....
I hate Wrong Answer!

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

10324:beggin 4 help

Post by 59557RC » Wed Apr 27, 2005 8:48 pm

ll i not b able 2 solve 10324.my code below :


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

int main(void)
{

char str[1000000],ch;
long int i,j,c,f,flag,temp,count=0,p,q;
gets(str);
while(str[0]!='\0'){
count++;
scanf("%ld",&c);



for(i=0;i<c;i++){
flag=0;
scanf("%ld %ld",&p,&q);
if(f==0){printf("Case %ld:\n",count);f=1;}
if(p>q) {temp=p;p=q;q=temp;}
ch=str[p];

for(j=p;j<=q;j++){


if(ch!=str[j]) {flag=1; printf("No\n");break;} }




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

}

gets(gets(str));
f=0;

}






return 0;
}
aaa

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

10324-pls help me

Post by 59557RC » Mon May 09, 2005 10:29 pm

can anyone pls explain me some things:

1. what does it mean by "input may be with end of file"?
2. what does gets(gets(str)) means?
3.what's wrong with my code :

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

int main(void)
{

char str[1000000],ch;
long int i,j,c,flag,temp,count=0,p,q;
gets(str);
while(str[0]!=0){
count++;
printf("Case %ld:\n",count);
scanf("%ld",&c);



for(i=0;i<c;i++){
flag=0;
scanf("%ld %ld",&p,&q);

if(p>q) {temp=p;p=q;q=temp;}

ch=str[p];

for(j=p;j<=q;j++){


if(ch!=str[j]) {flag=1; printf("No\n");break;} }




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

}

gets(gets(str));


}






return 0;
}
aaa

59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Location: bangladesh
Contact:

10324-pls help me

Post by 59557RC » Mon May 09, 2005 10:29 pm

can anyone pls explain me some things:

1. what does it mean by "input may be with end of file"?
2. what does gets(gets(str)) means?
3.what's wrong with my code :

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

int main(void)
{

char str[1000000],ch;
long int i,j,c,flag,temp,count=0,p,q;
gets(str);
while(str[0]!=0){
count++;
printf("Case %ld:\n",count);
scanf("%ld",&c);



for(i=0;i<c;i++){
flag=0;
scanf("%ld %ld",&p,&q);

if(p>q) {temp=p;p=q;q=temp;}

ch=str[p];

for(j=p;j<=q;j++){


if(ch!=str[j]) {flag=1; printf("No\n");break;} }




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

}

gets(gets(str));


}






return 0;
}
aaa

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Tue May 10, 2005 9:26 am

1. Input may be terminated by either EOF or a blank line. So you need to use something like while(cin>>str&&str!=""){/*...*/}; rather than just while(str!=""){/*...*/};
2. Basically the same thing as gets(str);gets(str);, meaning you do two gets-calls where the second overwrites the first. This is because gets(str) returns str if the call was executed successfully (otherwise a null-pointer is returned).

3. (I'll leave this one for you or someone else to figure out).

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

wrong approach..

Post by sohel » Mon May 23, 2005 12:42 pm

1] Already answered.
2] Already answered.

3] First of all don't declare huge arrays within the main function.. try to declare it gloablly or make it static.
.. second thing is that a bruteforce solution for this problem won't pass the time limit. This problem can be solved in O(n) time where n is the length of the original string and for each query O(1) should be used.

Some hints and spoilers:
suppose the string is "00011101100111000111",
try to maintain another array that will map a sequence of a particular character to one integer... and then for each query, simply check whether the lower and upper range map to the same integer..

ie. the above string would be transformed to A[11122234455666777888]
.. so if the query is (3 7) then the anwer is no because A[3] != A[7] .

Hope it helps.

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

10324

Post by mohsincsedu » Wed Oct 26, 2005 11:10 pm

I do not uderstand Why i got TLE :roll:
Plz tell me about this!!!

Here is my code:

Code: Select all

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

#define MAX 1000001
#define M 1000001

char num[MAX];


int main()
{
	int counter[M];
	long n, a, b, i, j,len,test = 1;
	char pre, post;
	//freopen("10324.in","r",stdin);
	//freopen("10324.out","w",stdout);
	while(scanf("%s",num)!=EOF)
	{
		if(num[0]=='\0')
			break;
		len = strlen(num);
		for(i = 0; i<= len;i++)
			counter[i] = 0;
		pre = num[0];
		for(i = 1;i<len;i++)
		{
			post = num[i];
			if(pre!=post)
			{
				for(j = i;j<len;j++)
					counter[j]++;
				pre = post;
			}
		}
		scanf("%ld",&n);
		printf("Case %ld:\n",test++);
		for(i = 1;i<=n;i++)
		{
			scanf("%ld %ld",&a,&b);

			if(counter[a]==counter[b])
				printf("Yes\n");
			else
				printf("No\n");
		}

	}
	return 0;
}

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

Post by Solaris » Thu Oct 27, 2005 7:11 pm

Code: Select all

for(i = 1;i<len;i++)
      {
         post = num[i];
         if(pre!=post)
         {
            for(j = i;j<len;j++)
               counter[j]++;
            pre = post;
         }
      } 
Dear Mohsin,

u r running a O(n^2) loop here. As n can be as big as 10,00,000 u should get TLE. :)

You have to think of a better algo :)
Where's the "Any" key?

mohsincsedu
Learning poster
Posts: 63
Joined: Tue Sep 20, 2005 12:31 am
Location: Dhaka
Contact:

Post by mohsincsedu » Thu Oct 27, 2005 10:29 pm

Thanks Solaris...
I got ACC........ :lol:

sv90
New poster
Posts: 17
Joined: Wed Feb 01, 2006 8:27 pm
Location: Dhaka,Bangladesh

10324 Help me ! or i will DIE

Post by sv90 » Sat Feb 04, 2006 11:56 am

THIS IS MY CODE BUT BY THIS CODE ICAN'T GET SEVERAL INPUT
SO WHAT CAN I DO NOW

i with draw my code
Last edited by sv90 on Sun Feb 05, 2006 10:37 am, edited 1 time in total.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Re: 10324 Help me ! or i will DIE

Post by mamun » Sat Feb 04, 2006 12:32 pm

sv90 wrote:BY THIS CODE ICAN'T GET SEVERAL INPUT
SO WHAT CAN I DO NOW
You can write your code so that it can read inputs until EOF. There are many posts regarding this like the sticky post of 100. Anyway here it can be

Code: Select all

while(scanf(" %s",str)!=EOF)             //str is char array
{
     // this is the beginning of each input block
     // do all the initializaion and processing here and then print output.
}
Search the forum. You'll get more help.

sv90
New poster
Posts: 17
Joined: Wed Feb 01, 2006 8:27 pm
Location: Dhaka,Bangladesh

Re: 10324 Help me ! or i will DIE

Post by sv90 » Sun Feb 05, 2006 10:36 am

sv90 wrote:thanks

sv90
New poster
Posts: 17
Joined: Wed Feb 01, 2006 8:27 pm
Location: Dhaka,Bangladesh

10324 PLEASE PLEASE Help Me "I m going tobe mad with th

Post by sv90 » Thu Feb 09, 2006 3:53 pm

This is my code but i got WA
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main()
{
unsigned long int i,m=0,a[100001],t=0,counter=0,l;
unsigned long int j,cases,z=0;
unsigned long int min,max;
char ch[100001],ctemp[1];

while((scanf("%s",&ch))!=EOF)
{
z++;
counter=0;
l=strlen(ch);
for(t=0;t<=l;t++)
{
ctemp[0]=ch[t];
i=atoi(ctemp);
if(i==m)
{
a[t]=counter;
}
else if(i!=m)
{
m=i;
counter++;
a[t]=counter;
}
}
scanf("%lu",&cases);
for(j=1;j<=cases;j++)
{
if(j==1)
{
printf("Case %lu:\n",z);
}
scanf("%lu%lu",&min,&max);
if(a[min]==a[max])
{
printf("Yes\n");
}
if(a[min]!=a[max])
{
printf("No\n");
}
}
}
return 0;
}

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Mon Mar 06, 2006 4:28 pm

This is wrong:

while((scanf("%s",&ch))!=EOF)

the name of an array is the same address of the array, so if you put &ch is an error

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil

Post by beloni » Mon Mar 06, 2006 4:35 pm

can you show me that algorithm did you used to got AC???
cause I'm with same problem... :(
and I have no idea...

Post Reply

Return to “Volume 103 (10300-10399)”