10324 - Zeros and Ones

[Joybo]

That's my code, but why I got wa?
[c]
#include <stdio.h>

#define swap(a,b) {long t; t=a;a=b;b=t; }
char s[1000002];
void main(void){
long times,len;
long n,start,end,i,j;
char c;

for(times=1;;times++){
gets(s);
len=strlen(s);
s[0]-='0';
for(i=1;i<len;i++) s=s-'0'+s[i-1];

printf("Case %ld:\n",times);
scanf("%ld",&n);
for(i=0;i<n;i++){
scanf("%ld%ld",&start,&end);
if(start>end) swap(start,end);

if(start==end) printf("Yes\n");
else{
if(s[end]==s[start] || s[end]-s[start]==end-start) printf("Yes\n");
else printf("No\n");
}
}
c=getchar();
if(c==-1) break;
}
}
[/c]

[babor]

It may be for negative co-ordinate .

[Joybo]

It may be for negative co-ordinate .

I found some bug, thx for you.

[rulio]

Here is my code for 10324, whih gives me WA...
Ok, this is definitively not the easiest approach to the problem, but I am looking for a memory-effective solution.

It worked with every input I created... but still WA...
Do you have any ideas/sample inputs guys?

[c]
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>


/*#define VISUAL*/



unsigned char line[125001]; /* is equal to 1,000,000/8 */
unsigned long timesaving[12000]; /*12,000 * 13 > 125,000 */
unsigned long length; /* length of input*/
unsigned long ii,jj; /* ii is min, jj is max*/
unsigned char ref; /*is either equal to 0 or 1, depending on value at min(ii,jj) */
#ifdef VISUAL
FILE * fp;

#endif

/****************************/
/****** Prototypes ******/
void processinput();
unsigned char precheck();


/****************************/
/****** Main ************/
int main(void)
{
unsigned long indice,indicej,indiceref; /*which octet?*/
unsigned short position,positionj; /*which bit in that octet?*/
unsigned long cas,nbcas;
unsigned long roundnb=0;
char tmpline[100];
unsigned char tmp;
unsigned char mask;
unsigned char okuntilhere;
unsigned long k;
#ifdef VISUAL
if (!(fp = fopen("in2.txt","r")) ) {printf("ouvezrture pb");exit(0);};
#endif



while(1)
{
processinput(); /*this will fill up line and length*/
k=0;
/* while (timesaving[k]!=-1)
printf("tsav[%d]=%d\n",k,timesaving[k++]);*/

roundnb++;
if (roundnb != 1)
printf("\n");
printf("Case %ld:",roundnb);
gets(tmpline);
sscanf(tmpline,"%ld",&nbcas);
for (cas=0; cas<nbcas ; cas++)
{
gets(tmpline);
sscanf(tmpline,"%ld %ld",&ii,&jj);
if (ii>jj)
{k=ii;ii=jj;jj=k;}
okuntilhere = 1;
position = ii % 8;
indice= ii / 8;
positionj = jj % 8;
indicej= jj / 8;
tmp = line[indice] << (position);
ref = tmp >> 7;
/*3 possible cass: ii and jj are in the same octet or next or not */
if (jj > length-1) /* max(i,j) is outside the field */
okuntilhere=0;

/* - case 1? special Treatement */
else if (indice == indicej)
{
mask = 0xFF;
mask = mask >> (position + 7 - positionj) ;
mask = mask << (7 - positionj);
if (ref == 0)
{
tmp= line[indice] & mask;
}
else
{
mask = ~mask ;
tmp = ~( line[indice] | mask);
}

if (tmp)
okuntilhere=0;
if (ii==jj)
okuntilhere=1;

}

else
{
/* Try to speed up the search.... This is telling if there is a chance or not to find a constant string between start to end*/
if (indicej - indice >=13)
okuntilhere = precheck();
if (okuntilhere)
{
if (ref ==0)
{
tmp = tmp >> (position);
mask=0;
}
else
{
mask= 0xFF;
mask = mask << (7-position);
tmp = line[indice] | mask;
mask= 0xFF;
}
if (mask ^ tmp)
okuntilhere=0;
else
{
/*procede next*/
indiceref=indice;

indice ++;
while ((indice != indicej) && (okuntilhere))
{

if (mask ^ line[indice])
okuntilhere =0;
else
indice ++;

if (indice >indiceref + 15) /*then , if there is no record of changes, that s ok!*/
{
/* printf("check final (pos=%ld)\n", 8*indice);*/
okuntilhere=precheck();break;}

}
/*last octet handler*/
if (okuntilhere)
{
if (ref ==0)
{
tmp = line[indicej] >> (7 - positionj);
tmp= tmp << (7 - positionj);
mask=0;
}
else
{
mask= 0xFF;
mask = mask >> (positionj+1);
tmp = line[indicej] | mask;
mask= 0xFF;
}
if (mask ^ tmp)
okuntilhere=0;
}
}
}/*if ok untilhere apres precheck*/
} /*si pas cas 1*/

if (okuntilhere)
printf("\nYes");
else
printf("\nNo");
} /*end of the case*/
}/*while 1*/
}



void processinput()
{
char tmp[2]="x\0";
unsigned char atmp;
short i=7;
unsigned long j=0;
unsigned long k=0,lastj=0;
unsigned short change=0;
unsigned char reff=0;


tmp[0]=getc(stdin);
line[0]=0;
if (tmp[0]=='1')
reff=1;

if ((tmp[0]==EOF) ||(tmp[0] == 13)||(tmp[0] == 10)||(tmp[0] == '\n'))
exit(1);
while (tmp[0]== '1' || tmp[0]=='0')
{
if (tmp[0]=='1')
atmp=1;
else
atmp=0;

if (atmp ^ reff) /* a change occured*/
{
reff = reff ^ 0x01;
if ( (j - lastj) >= 13 ) /* ino changes during the last 13 octets 13*8 bits*/
{
lastj=j;
timesaving[k++] = j*8 + 7-i;
}
}
line[j] += (atmp << i);
i--;
if (i < 0 )
{
i=7;
j++;
line[j]=0;
}
tmp[0]=getc(stdin);
}
#ifdef trace
printf("ajoute 0x%X\n",line[j]);
#endif
timesaving[k] = -1;
length=(j+1)*8 - i -1;
}



unsigned char precheck()

{
unsigned int k=0;

while ( (timesaving[k] < ii) && (timesaving[k] != -1) ) k++;
/* Then we are sure a changement occured somewhere between ii and jj*/
if ((timesaving[k]!= -1) && (timesaving[k] < jj))
{
/* printf("impossible"); */
return 0;
}
return 1;
}

[/c]

[kiha]

I hate to put wrong codes here, but I've read all topics about 10324 and I haven't found a solution. So, if anybody could ... :>
I tested it on all cases I can think of, and it works [as usual :/]

[pascal]program miazio;

{}

procedure change (var a, b:longint);
var c:longint;
begin c:=a; a:=b; b:=c; end;

{}

var
t:array [0..200000] of longint;
siz, i, j, k, l, kejs:longint;
zn, zm:char;
g:boolean;

{}

begin

zn:=';';
kejs:=0;
t [0]:=0;

while (not eof) and (ord (zn) <> 13) do
begin

i:=0;
if (eoln) or (eof) then exit;
read (zm);
inc (kejs);

while not eoln do
begin

read (zn);
inc (i);

if zn = zm then
t :=t + 1 else
t :=0;

zm:=zn;

end;

siz:=i;
readln (j);
writeln ('Case ', kejs, ':');

for i:=1 to j do
begin

readln (k, l);
if l < k then change (k, l);

g:=false;

if k = l then g:=true;
if t [l] >= l - k then g:=true;
if l > siz then g:=false;

if g then writeln ('Yes') else
writeln ('No');

end;

end

end.[/pascal]

Thanks in advance,
with regards

[toren]

I've noticed that many people have been concerned with this problem,
so I thought I'd contribute with a (big) hint on avoiding TLE:

DON'T STORE THE BINARY STRING, YOU DON'T NEED TO!

Let's say that you would like to compress the binary string -
what is the essential information that you need in order to
retain the original string from the compressed one? You need
the the first character and a sequence of increasing numbers that
corresponds to positions in the original string where a change of
character takes place (i.e. bit flip) (i.e. for each number k in the
constructed sequence, a change takes place at pos k, that is, bit
at pos k-1 != bit at pos k)

Example: Take the following string on 10 characters with positions 0..9
1000110011
0123456789

Here you store 1 as first character, and numbers 1,4,6,8 because
at bit flip takes place at those positions. This and the total string length
would be sufficient for decompressing. Here you only need the changing positions.

So now you are ready to attack the
queries in the form of pairs (start,end), meaning you have to check
the substring ranging from position start to end, inclusive.( Remember
to make start<=end, but this should be obvious.) Simply test if there is
a number n in the sequence such that start < n <= end, implying a
change in that substring. This can be done by doing a binary-search-like
algorithm: find the lowest number n that is greater than start.
If n > end then no changes occur in that substring so output "Yes", else "No".

Also beware of base cases such as if start==end, or if no changing-positions occur
(the whole string is 1's or 0's) or the last changing position is a position that is less or equal to start.

Good luck!

[Jewel of DIU]

Hi I dont know why my program got WA.
Would you plz check my code?
[c]
\#### CUT AFTER AC ####/

Adrian ur right
[/c]
Hurry plz...

[UFP2161]

Relevant portion bolded:

Given a string of 0's and 1's up to 1000000 characters long and indices i and j, you are to answer a question whether all characters between position min(i,j) and position max(i,j) (inclusive) are the same.

[Jewel of DIU]

Suppose i=5,j=2
So,
min(i,j)=2
max(i,j)=5

min < range < [ max ( inclusive) ]
2 < range <= 5
Am I Wrong ?

[c]
if(strt>end)
{
temp=strt;
strt=end;
end=temp; /* max */
strt++; /* min */
/* "min<" min++ */
}

if(str[strt]==str[end]) printf("Yes\n");
/*min < range < [ max ( inclusive) ] */
[/c]

[UFP2161]

You're only checking the boundaries (str[strt] == str[end]), not the numbers in BETWEEN.

[Adrian Kuegel]

if(str[strt]==str[end])

I think you wanted to write: change[strt] == change[end].
And the inclusive is meant on both sides, so min(i,j) is included and max(i,j) is included.

[Jewel of DIU]

Thank You Adrian.
I thought inclusive is only for max.
I wanna use change[strt] == change[end]
for only check the change of bit .

[Morning]

anything wrong with my code?pliz help
[cpp]
#include <iostream.h>
#include <string.h>
//using namespace std;
int sol(char diff[1000001],int count,int a,int b)
{
if (b >= count) return 0;
for (int i = 0;i < count;i++)
{
if (diff > a && diff <= b)
{
return 0;
}
if (diff > b) break;
}
return 1;
}
int main()
{
char data[1000001];
char diff[1000001];
int n,a,b,count,len,temp,numOfCase = 1;;
while (cin >> data)
{
cout << "Case " << numOfCase << ':' << endl;
count = 0;
len = strlen(data);
for (temp = 1;temp < len;temp++)
{
if (data[temp] != data[temp - 1])
{
diff[count++] = temp;
}
}
cin >> n;
while (n--)
{
cin >> a >> b;
if (sol(diff,count,a,b)) cout << "Yes" << endl;
else cout << "No" << endl;
}
numOfCase++;
}
return 0;
}
[/cpp]

[sidky]

Think of this case

Code: Select all

1111111111
1
0 9

Your program produces "No". It should be "Yes"

[late_nighter]

This is my Code :

Code: Select all

[cpp]

#include <iostream>

using namespace std;

int main (){

char str ,ch;
int  countArr [1000001];
int len;
int n;
int a,b;
int min , max;

int count = 0 ;
int casCount = 1;
while (1)
{
count = 0;
while(1)
{
cin.unsetf(ios::skipws);
cin >> ch;
cin.setf(ios::skipws);
if(  ch=='\n' )
break;

if (count == 0)
{
countArr[count] = ch-'0';
}else{
countArr[count] = countArr[count-1] + ch  - '0';
}
count++;
}
cin >> n;

if (count == 0)
return 0;

if( !cin.good() )
return 0;
cout <<"Case "<<casCount++<<":"<<endl;
//cout<<"n "<<n<<endl;
while (n--)
{
//cout << "N == " << n << endl;
cin >> a >> b;
//cout << a << " " << b << endl;
//cout<<a<<" "<<b<<" a b "<<endl;
a > b ? min = b , max = a : min = a , max = b;

if (max >= count || min < 0  || max <0)
{
cout <<"No" <<endl;
continue;
}

//cout << countArr[max] - countArr [min] <<endl;
if ((min >=1 && countArr[max] == countArr[min-1]) || (min ==0 && (countArr[max] == max+1 || countArr[max] == 0)))
cout << "Yes" << endl;
else if (countArr[max] - countArr[min-1] == max - min + 1)
cout << "Yes" <<endl;
else 
cout <<"No"<<endl;
}
cin.unsetf(ios::skipws);
cin >> ch;
cin.setf(ios::skipws);

}

return 0;
}

[/cpp]

This is my code to solve the problem . But it is giving Wrong answer.
I have checked all possible inputs possible by me .