10324 - Zeros and Ones

[mf]

Just consider the string as a sequence of numbers {a_1, a_2, ..., a_n}, and compute its partial sums: S_k=a_1+a_2+...+a_k. (trivial DP: S_0=0, S_k=S_{k-1}+a_k.)
Then all elements in range i..j are 0's if S_{i-1}=S_j.
And elements in range i..j are 1's if S_j-S_{i-1} = j-i+1.

[sv90]

but it still have problem
its output is bellow
Case 1:
No
Yes
Yes
Case 2:
Yes
Yes
Yes
Yes
Yes
Case 3:
Yes

so what should i do now

[beloni]

well, your code ... try to broken it down in some functions...

It is so dificult to read

[beloni]

thanks, but anyway I'll must to cover the array in range i..j, as well my TLE algorithm.. or no ???

int same(int start, int end, const char *str)
{
int w;

for(w = start+1; w <= end; w++)
if( str[w] != str[start] )
return 0;

return 1;
}

[mf]

No, my algorithm finds the answer by examining just two elements of array S, it doesn't need to scan the sequence.
Maybe my previous post wasn't very clear to you, so here's a pseudocode:

Code: Select all

Let a[0], a[1], ..., a[n-1] be the input sequence of 0's and 1's.
Let S be an array of size n+1, indexed from 0 to n.

S[0] = 0
for i = 1 to n do:
	S[i] = S[i-1] + a[i-1]
/* Now every S[k] is equal to the sum: S[k] = a[0] + a[1] + ... + a[k-1]. */

for each query i, j do:
	if i > j then swap(i, j)

	x = S[j+1] - S[i]
	/* Now x is equal to the sum a[i] + a[i+1] + ... + a[j]. */

	if x == 0 or x == (j-i+1) then
		print "Yes"
	else
		print "No"

[Stummer]

Why I got TLE??


#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char c[1000005];
int m[1000005];
int main()
{
int n,a,b,i,ii=0;
while(scanf("%s",c)!=EOF)
{
ii++;
cout<<"Case "<<ii<<':'<<endl;
m[0]=0;
for(i=1;i<strlen(c);i++)
{
if(c!=c[i-1]) m=m[i-1]+1;
else m=m[i-1];
}
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
if(m[a]==m) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}

[Stummer]

At least I got Accepted! Here is my code:

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char c[1000005];
int m[1000005];
int main()
{
int n,a,b,i,ii=0,k;
while(scanf("%s",c)!=EOF)
{
ii++;
cout<<"Case "<<ii<<':'<<endl;
m[0]=0;
k=strlen(c);
for(i=1;i<k;i++)
{
if(c!=c[i-1]) m=m[i-1]+1;
else m=m[i-1];
}
cin>>n;
for(i=0;i<n;i++)
{
cin>>a>>b;
if(m[a]==m) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
}
return 0;
}

[emotional blind]

no one should post his ACCEPTED code here.
its very much spoiling.

[S.M.Abdullah]

I have submitted prime cut. But the machine give me wrong answer.
What's the problem?

Code: Select all

#include<stdio.h>


int main()
{
char a[100000];
long long i,p,q,c,d,x,j,z=1,flage,temp;


while(scanf("%s",a)!=EOF)
{
if(a=="\0")
break;
   scanf("%lld",&x);
   printf("Case %lld:\n",z++);
   for(j=1;j<=x;j++)
    {
XY:
flage=1;
scanf("%lld %lld",&p,&q);
if(q<p)
{
temp=p;
p=q;
q=temp;
}
for(i=p;i<q;i++)
{
if(a[i]!=a[i+1])
{
flage=0;
printf("No\n");
j=j+1;
if(j<=x)
goto XY;
}
}
if(flage==1)
printf("Yes\n");
}
}

return 0;
}

[Joseph Kurniawan]

What problem are you working at?
Is it 10324 - Zeros and Ones?
Besides this is the forum for Volume I --> for prob 100 until 199.

[linux]

Hi, Abdullah I'll just suggest you that you should avoid using goto functions. It can cause unexpected errors along with extra raising extra complexity in code. So it's a good practice to avoid using goto.

Keep posting!

[newton]

i cant find what is the problem with my innocent code?
why wrong answer?
can anybody help me finding the problem?

Code: Select all

#include<stdio.h>
#include<string.h>
main()
{
char  str1[1000001];
char  str2[1000001];
int Case,m,n,i,c;
Case=0;
while(scanf("%s",str1)==1)
{
	str2[0]=1;
	for(i=0;str1[i];i++)
		if(str1[i]!=str1[i+1])
			str2[i+1]=str2[i]+1;
		else
			str2[i+1]=str2[i];

	printf("Case: %d\n",++Case);
	scanf("%d",&c);
	for(i=1;i<=c;i++)
		{
		scanf("%d %d",&m,&n);
		if(str2[m]==str2[n])
			printf("Yes\n");
		else
			printf("No\n");
		}
}
return 0;
}

[nnicool]

I don't know why WA..
I can't find any mistakes in my code..

-----------------------

#include <iostream>
#define swap(a,b){a^=b;b^=a;a^=b;}
using namespace std;

int main()
{
long cnt,pos,tmp,T,min,max,CASES,TOTAL,size;
char G[1000001];
char buf,ch;
CASES = 0;
while(!cin.eof())
{
if(cin.eof())
break;
cnt = pos = 0;
CASES++;
cin.getline(G,1000000);
size = strlen(G);
buf = G[0];
G[0] = (char)0;
for(tmp = 0; tmp < size-1;tmp++)
{
cnt++;

ch = G[cnt];
if(ch == buf)
G[cnt] = pos;

else
{
G[cnt] = ++pos;
buf = ch;
}
}

cin >> T;
cout << "Case " << CASES << ":" << endl;
for(cnt = 0; cnt < T;cnt++)
{
cin >> min >> max;
if ( min > max )
swap(min,max);

if(size-1 < max || min < 0)
cout << "No" << endl;
else
{
if(G[min] == G[max])
{
cout << "Yes" << endl;
}
else
cout << "No" << endl;
}
}
cin.get();
}
return 0;
}
----------------
if ther are complex test cases , plz ...

[rio]

"The input ends with an empty string that is a line containing only the new line character, this string should not be processed. The input may also with end of file. So keep check for both."

try this code.


CASES++;
cin.getline(G,1000000);
size = strlen(G);
if (size == 0) break; // i think you need this!
buf = G[0];

[daveon]

Hi,

The strings can be up to 1000000 characters long. So you need at least 1000001 sized array because you need 1 more for the null character. So just increase your array size.