OJ Board

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++)

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.

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~

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?

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

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.

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

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

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

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

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

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]

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

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

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

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