## 10324 - Zeros and Ones

All about problems in Volume CIII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

### 10324

the following code of 10324 fetches me TLE . i used a very simple brute force algorithm. pliz tell me any other good algorithm , if is there?,. here is my code for 10324.
Code: Select all
`#include<stdio.h>#include<string.h>#define max(a,b) ((a)>(b)? (a): (b))#define min(a,b) ((a)>(b)? (b):(a))int CheckTheInformation(char input[],long int x , long int y){   long int i ;//long long int(used while sending to the judge )    int count;      count=input[x];   for(i=x+1;i<=y;i++){         if(input[i]==count)         continue;      else         return 0;               }   return 1;}int main(){   char input[1000002];   char xtra[50];   int cases,flag,count;   long int i , j;//long long int(used while sending to the judge )    cases=1;            while(gets(input)){               if(strcmp(input," ")==0 || strcmp(input,"\n")==0)         break;                        gets(xtra);      sscanf(xtra,"%d",&count);            printf("Case %d:\n",cases);                  while(count>0)      {         gets(xtra);         sscanf(xtra,"%ld %ld",&i,&j);//long long int          flag=CheckTheInformation(input,min(i,j),max(i,j));         if(flag==0){            printf("No\n");         }         else            printf("Yes\n");         count--;            }      cases++;      }             return 0;}`

on the other hand my code for 10340 fetches me WA . the algorithm of mine is very simple , i cant find any mistakes in the code . pliz help .
here is the code for 10340
[c]
#include<stdio.h>
#include<string.h>

int CheckForSubSequence(char in1[],char in2[]){

int i , c , flag,j;

if(strlen(in1) > strlen(in2)){

return 1;

}

else if(strlen(in1)==strlen(in2)){

return strcmp(in1,in2);
}
else{

for(i=0,c=0;in1[i]!='\0';i++){

flag=1;
for(j=c;in2[j]!='\0';j++){

if(in1[i]==in2[j]){
c=j;
flag=0;
break;
}

}

if(flag==1)
return 1;
else
continue;

}

return 0;

}

}

int main(){

char input[10000];
char in1[1000],in2[1000];
int Flag;

while(gets(input)){

sscanf(input,"%s %s",in1,in2);
Flag=CheckForSubSequence(in1,in2);

if(Flag==0){
printf("Yes\n");
}
else
printf("No\n");
}

return 0;
}[/c]

pliz help me
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

You cant avoid TLE if you use such search. Try using better search method. Remember that, you only have to consider whether the digits between ith and jth are the same, u dont have to know, whether they are zero or one.
sidky
New poster

Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe

for p10340 (All in All):
1. buffers are too small... take something upto 1000000 (that's what i took, lesser might work. but never with 1000 at least!)
2. still another mistake is in your checking function. try to find it... for this you must fail for input...
Code: Select all
`abbbbbbc abcccccccccccccccccc`

where your prog outs "Yes"... and should be "No"
you'll know why...
Istiaque Ahmed [the LA-Z-BOy]

the LA-Z-BOy
Learning poster

Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm

### hey man got 10340 aC

hey man so care less of me about 10340 (all in all ). i got it right , there was a mistake in the check function . i should initialize c with -1 . and instead of making j =c i should have made j=c+1.some how got it right .
and about 10324 i am trying a new algorithm for searching . special thanx to laz boy
Bye
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

Experienced poster

Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET

### 10324 WA

Hi everyone,
i really dunno what
"There's a difference between knowing the path, and walking the path."

Trickster
New poster

Posts: 6
Joined: Sat Sep 20, 2003 6:31 am
Location: Recife, Brazil

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[i]=s[i]-'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]
Joybo
New poster

Posts: 4
Joined: Tue Sep 23, 2003 12:05 pm

It may be for negative co-ordinate .
babor

babor
New poster

Posts: 16
Joined: Sat Jun 07, 2003 4:23 pm

babor wrote:It may be for negative co-ordinate .

I found some bug, thx for you.
Joybo
New poster

Posts: 4
Joined: Tue Sep 23, 2003 12:05 pm

### 10324

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 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 = mask >> (position + 7 - positionj) ;
mask = mask << (7 - positionj);
if (ref == 0)
{
tmp= line[indice] & mask;
}
else
{
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);
}
else
{
tmp = line[indice] | mask;
}
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);
}
else
{
tmp = line[indicej] | mask;
}
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]
rulio
New poster

Posts: 4
Joined: Sun Oct 12, 2003 4:20 am

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;
inc (kejs);

while not eoln do
begin

inc (i);

if zn = zm then
t [i]:=t [i - 1] + 1 else
t [i]:=0;

zm:=zn;

end;

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

for i:=1 to j do
begin

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]

with regards
kiha
kiha
New poster

Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

### 10324 (Zeroes and ones) - Solution

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!
toren
New poster

Posts: 5
Joined: Thu Aug 21, 2003 3:39 pm
Location: Bergen, Norway

### 10324 Wa. Help plz

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

[/c]
Hurry plz...
Last edited by Jewel of DIU on Tue May 25, 2004 8:33 pm, edited 2 times in total.
Hate WA
Visit phpBB!
Jewel of DIU
New poster

Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh

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.

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

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]
Hate WA
Visit phpBB!
Jewel of DIU
New poster

Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh

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

UFP2161
A great helper

Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm

PreviousNext