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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Mon Mar 06, 2006 6:16 pm

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
Location: Dhaka,Bangladesh

thanks

Post by sv90 » Tue Mar 07, 2006 11:04 am

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

Post by beloni » Tue Mar 07, 2006 1:50 pm

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

Post by beloni » Tue Mar 07, 2006 2:18 pm

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:

Post by mf » Tue Mar 07, 2006 4:01 pm

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
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany

Re: 10324 Help me ! or i will DIE

Post by Stummer » Sat Jul 01, 2006 12:55 pm

Why I got TLE?? :cry:


#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
New poster
Posts: 12
Joined: Sat Jul 01, 2006 12:16 pm
Location: Munich, Germany

Re: 10324 Help me ! or i will DIE

Post by Stummer » Sat Jul 01, 2006 12:59 pm

At least I got Accepted! :wink: 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;
}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sun Jul 02, 2006 9:08 pm

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

Post by S.M.Abdullah » Sun Jul 09, 2006 8:44 am

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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia

Post by Joseph Kurniawan » Sun Jul 09, 2006 10:04 am

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.

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

Suggestion.

Post by linux » Sun Jul 09, 2006 11:54 am

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..

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

10324

Post by newton » Thu Sep 07, 2006 6:16 am

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;
}
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

Post by nnicool » Fri Sep 08, 2006 7:09 pm

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 ...

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Thu Sep 21, 2006 5:06 pm

"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
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Sun Oct 01, 2006 4:58 pm

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.

Post Reply

Return to “Volume 103 (10300-10399)”