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

Post Reply
Joybo
New poster
Posts: 4
Joined: Tue Sep 23, 2003 12:05 pm

Post by Joybo » Sat Nov 01, 2003 6:26 pm

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]

User avatar
babor
New poster
Posts: 16
Joined: Sat Jun 07, 2003 4:23 pm
Contact:

Post by babor » Mon Nov 03, 2003 2:30 pm

It may be for negative co-ordinate .
babor

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

Post by Joybo » Tue Nov 04, 2003 2:18 am

babor wrote:It may be for negative co-ordinate .
I found some bug, thx for you.

rulio
New poster
Posts: 4
Joined: Sun Oct 12, 2003 4:20 am

10324

Post by rulio » Sun Nov 09, 2003 2:40 am

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
New poster
Posts: 37
Joined: Sat Dec 20, 2003 10:59 pm

Post by kiha » Wed Mar 03, 2004 10:38 pm

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
kiha

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

10324 (Zeroes and ones) - Solution

Post by toren » Sat Apr 10, 2004 2:07 am

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! :D

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

10324 Wa. Help plz

Post by Jewel of DIU » Mon May 24, 2004 6:09 am

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...
Last edited by Jewel of DIU on Tue May 25, 2004 8:33 pm, edited 2 times in total.
Hate WA
Visit phpBB!

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon May 24, 2004 7:17 am

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
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by Jewel of DIU » Mon May 24, 2004 7:16 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!

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Mon May 24, 2004 9:53 pm

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

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue May 25, 2004 12:10 am

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
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by Jewel of DIU » Tue May 25, 2004 8:39 pm

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

Morning
Experienced poster
Posts: 134
Joined: Fri Aug 01, 2003 2:18 pm
Location: Shanghai China

10324 why WA?

Post by Morning » Sun Sep 19, 2004 4:43 pm

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]
"Learning without thought is useless;thought without learning is dangerous."
"Hold what you really know and tell what you do not know -this will lead to knowledge."-Confucius

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

Post by sidky » Mon Sep 20, 2004 8:23 am

Think of this case

Code: Select all

1111111111
1
0 9
Your program produces "No". It should be "Yes"

late_nighter
New poster
Posts: 4
Joined: Wed Nov 10, 2004 8:47 pm

10324 WA Help needed

Post by late_nighter » Wed Nov 10, 2004 8:53 pm

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 .

Post Reply

Return to “Volume 103 (10300-10399)”