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

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

Post by Adrian Kuegel » Sun Jul 07, 2002 11:12 am

Don't use strlen in a for loop, like here:
for(y=0;y<strlen(buffer);y++)

make it:
len = strlen(buffer)
for (y=0;y<len;y++)

KE4MTG
New poster
Posts: 15
Joined: Sat Jul 06, 2002 3:31 am
Location: Florida, USA
Contact:

10324

Post by KE4MTG » Sun Jul 07, 2002 6:53 pm

Hi, I'm getting this RE message
Your program has died with signal 11 (SIGSEGV). Meaning:

Invalid memory reference

Before crash, it ran during 0.170 seconds
This sucks. One thing I can say is that when I run on my comp using Microsoft Visual C++, and I try to type in a huge string of 0's and 1's i can only input 253 digits and then it stops taking in digits. It just stops and I don't know why. O yea and my code is kinda weird. Here is my code:
[cpp]#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void subprocess(int *buffer, int p, char dir, int & count, int pos1, int pos2,int length)
{
if(p < length)
{ if(int(buffer[p]) <= pos2 && int(buffer[p]) >= pos1)
count++;
else
dir = '\0';

if(dir == 'u')
{ p+=1;
subprocess(buffer,p,dir,count,pos1,pos2,length);
}
else if(dir == 'd')
{ p-=1;
subprocess(buffer,p,dir,count,pos1,pos2,length);
}
}
}


void process(int* buffer, int length, int pos1, int pos2, int & temp, int stringlength)
{ int start=0, n = int(length/2), end = length-1, count = 0;
if(pos1 > pos2)
{ temp = pos2;
pos2 = pos1;
pos1 = temp;
}
while(n < length)
{ if(start==end)
break;
if(int(buffer[n]) <= pos2 && int(buffer[n]) >= pos1)
{ int p = n;
char up = 'u',down = 'd';
subprocess(buffer,p,up,count,pos1,pos2,length);
subprocess(buffer,p,down,count,pos1,pos2,length);
count--;
break;
}
else if(int(buffer[n]) > pos2)
{ end = n;
if(int((start+n)/2) == n)
break;
n = int((start+n)/2);
}
else if(int(buffer[n]) < pos1)
{ start= n;
if(int((end+n)/2)==n)
break;
n = int((end+n)/2);
}
}
int difference = pos2-pos1+1;
if((count == 0 || count == difference)&& pos2 < stringlength)
printf("Yes\n");
else
printf("No\n");
}

int main()
{
for(int i=1;; i++)
{ int * buffer,d(0);
char c;
buffer=(int *)malloc(sizeof(int)*1000000);
if (buffer==NULL) exit (1);
int a;
for(a=0 ; (c=getchar())!='\n' ;a++)
{ if(c==EOF)
exit(0);
else
{ if(c=='0')
{ buffer[d] = a;
d++;
}
}
}
int stringlength = a,length = d,num,x, y,temp;
printf("Case %d:\n",i);
scanf("%d",&num);
for(int i = 0; i < num; i++)
{ scanf("%d",&x);
scanf("%d",&y);
if(x >= stringlength || y >= stringlength)
printf("No\n");
else
process(buffer,length,x,y,temp,stringlength);
}
free(buffer);
getchar();
}

return 0;
}[/cpp]


Now I'm just a high school student, so If my code is really bad please tell me because I would not know better. Basically what it does is that it takes in the positions of zeroes in an array. Then it searches the array for a position that contains a position of a zero within the input positions. Once it finds it uses a recursive function to search up and down from that spot in that array. It counts the times it finds valid positions of zeroes. If it the count is 0 or the difference between the two input positions then that means that they are all 1's or 0's, respectively.

I tried this program before and it gave me a TLE so I had to go back to the drawing board to make a less time consuming program.

Anyway if you have any suggestions on how to fix my RE problem please give them to me =). Thank you very much.

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Sun Jul 07, 2002 7:13 pm

I have not taken a in-depth look at your algo, but the first thing come to my attention is the use of recursion. RE will be caused is there's stack overflow, i.e. when the number of times recursion is called is too much.

For the input problem you mentioned, you can write the input data in a file and then feed the input data file to run the program, e.g.

p10324 < 10324.in, where 10324.in is the input file.

In the input file, there's no limit on your text length~ :D

KE4MTG
New poster
Posts: 15
Joined: Sat Jul 06, 2002 3:31 am
Location: Florida, USA
Contact:

Post by KE4MTG » Sun Jul 07, 2002 7:52 pm

That input file thing.....I thought when submitting to the judge you could not create an outside file. Or do you mean just do it for means of fixing the program?

10153EN
Experienced poster
Posts: 148
Joined: Sun Jan 06, 2002 2:00 am
Location: Hong Kong
Contact:

Post by 10153EN » Sun Jul 07, 2002 7:56 pm

No, the judge will also feed the inputs from the files~

KE4MTG
New poster
Posts: 15
Joined: Sat Jul 06, 2002 3:31 am
Location: Florida, USA
Contact:

Post by KE4MTG » Sun Jul 07, 2002 7:58 pm

For the recursion issue, what is the limit on the number of times?? the most my function could recurse is about 20 times. Argh, I forget what kind of sort is similar. Let's see if I can explain it.

Assume the array is sorted.
An array of 1,000,000 (say for 1,000,000 zeroes) it finds the middle position, 500,000. if the value in that position is bigger it adds 250,000 -> so it checks position 750,000. However if the value is smaller it subtracts 250,000-> checking the position of 250,000 and so on and so on... SO the max for 1,000,000 positions is about 20. I don't see how that can cause an RE.... But maybe i'm wrong =) hehe.

KE4MTG
New poster
Posts: 15
Joined: Sat Jul 06, 2002 3:31 am
Location: Florida, USA
Contact:

Post by KE4MTG » Sun Jul 07, 2002 8:00 pm

errrrr. i'm not getting it, do you have an example program that uses that what you're talking about??? sorry for troubling you.

KE4MTG
New poster
Posts: 15
Joined: Sat Jul 06, 2002 3:31 am
Location: Florida, USA
Contact:

Post by KE4MTG » Sun Jul 07, 2002 8:01 pm

O wait i see what you're saying about the recursion thing.... nevermind, so recursion is bad?? that means i need to change it?

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl » Mon Jul 08, 2002 5:25 pm

I've found the bug and fix it. And I got accepted. Thanks

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10324

Post by Larry » Wed Jul 10, 2002 12:32 am

[java] String input;
int l = 1;
while ( ( input = ReadLn( 255 ) ) != null ){
if ( input.equals( "" ) ) break;
String ans = input;

System.out.println( "Case " + ( l++ ) + ":" );
input = ReadLn( 255 );
int a = Integer.parseInt( input );
for ( int i = 0; i < a; i++ ){
StringTokenizer st = new StringTokenizer( input = ReadLn( 255 ) );

int b = Integer.parseInt( st.nextToken() );
int c = Integer.parseInt( st.nextToken() );

if ( b > c ){
b ^= c;
c ^= b;
b ^= c;
}
if ( ans.substring( b, c + 1 ).indexOf( ( ans.charAt( b ) == '0' ) ? '1' : '0' ) != -1 ){
System.out.println( "No" );
}
else System.out.println( "Yes" );
}
}
[/java]

I don't know why it gets WA, because it works on all the test cases, and it seems to make sense logically. Did I make another silly mistake? Thanks in advance.

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Wed Jul 10, 2002 1:38 am

Don't know to much about Java, but if ReadLn(255) means that at most 255 characters can be read, then read the problem description regarding the maximal line length :)

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar » Wed Jul 10, 2002 4:37 am

I think that xenon is right . The problem description says that the line could be 1000000 characters so you have to fix this.

I also program in java because of problems like this and others where the line lenght is not specified i made a better ReadLn.

I post it here if you want to use it,

[java]
/* ReadLn that doesnt require the max line length */

static String ReadLn (){
StringBuffer s = new StringBuffer("");
int car = -1;

try{
do{
car = System.in.read();
if ((car < 0) || (car == '\n')){
break;
}
else{
s.append((char) car);
}
} while(car > 0);
}
catch (IOException e){
return (null);
}

if (car < 0){
return null;
}else{
return s.toString();
}
}
[/java]
Hope can help.



PS: Whats the point of this part of the code. Explain please. Are u swaping? How do u acomplish this without an auxiliar variiable


if ( b > c ){
b ^= c;
c ^= b;
b ^= c;
}
[/quote][/code]

xenon
Learning poster
Posts: 100
Joined: Fri May 24, 2002 10:35 am
Location: Scheveningen, Holland

Post by xenon » Wed Jul 10, 2002 9:51 am

He, he... it's an old assembly programmers trick to swap two registers without the use of a third. It's based on the equalities b^b==0, b^0==b. Work it out in terms of old_b and old_c to see that it works! It's quite fascinating if you see it the first time 8)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Jul 10, 2002 12:25 pm

Thanks, I changed it to a million and it worked perfectly.

I suppose I just got too used to using ReadLn(255) :D

LawrenceT
New poster
Posts: 14
Joined: Sun Feb 24, 2002 2:00 am
Location: Singapore
Contact:

Post by LawrenceT » Mon Jul 15, 2002 5:19 pm

this problem requires a solution that takes linear time (ie. no nested loops, no recursion needed)

Post Reply

Return to “Volume 103 (10300-10399)”