## 10324 - Zeros and Ones

Moderator: Board moderators

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 17
Joined: Wed Feb 01, 2006 8:27 pm

### thanks

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
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
well, your code ... try to broken it down in some functions...

It is so dificult to read

beloni
Learning poster
Posts: 66
Joined: Thu Jan 05, 2006 1:41 pm
Location: Pelotas, RS, Brazil
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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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, a, ..., 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
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 + a + ... + 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
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany

### Re: 10324 Help me ! or i will DIE

Why I got TLE?? #include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char c;
int m;
int main()
{
int n,a,b,i,ii=0;
while(scanf("%s",c)!=EOF)
{
ii++;
cout<<"Case "<<ii<<':'<<endl;
m=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
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany

### Re: 10324 Help me ! or i will DIE

At least I got Accepted! Here is my code:

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
char c;
int m;
int main()
{
int n,a,b,i,ii=0,k;
while(scanf("%s",c)!=EOF)
{
ii++;
cout<<"Case "<<ii<<':'<<endl;
m=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
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
no one should post his ACCEPTED code here.
its very much spoiling.

S.M.Abdullah
New poster
Posts: 1
Joined: Sun Jul 09, 2006 8:29 am

### 10324

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;
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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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.
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

linux
Learning poster
Posts: 56
Joined: Sat Jul 01, 2006 12:21 pm
Location: CA-95054
Contact:

### Suggestion.

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!
Solving for fun..

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

### 10324

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

Code: Select all

``````#include<stdio.h>
#include<string.h>
main()
{
char  str1;
char  str2;
int Case,m,n,i,c;
Case=0;
while(scanf("%s",str1)==1)
{
str2=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;
}
``````
Last edited by newton on Thu Oct 05, 2006 8:49 am, edited 3 times in total.

nnicool
New poster
Posts: 3
Joined: Wed Aug 30, 2006 8:53 am

### 10324

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;
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;
G = (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
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
"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;

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am