This program passed my university's grader (all test cases) but segfaults in my pc

Question

This program is doing binary search in an int array (Kseek) using limits (low,up). Please ignore some instructions that seem to be weird, I have not finished all that must be done.

The strange thing is that my code runs perfectly in my university grader but segfaults for large test cases in my pc. I cannot understand where the mistake is, for inputs that have N>4000 elements it crashes.

I do not use any pointers or any memory allocation, I thought that scanf might segfault and tried to change some attributes but it still crashes.

Is it possible that gcc has "memory allocation boundaries" during compilation, and then when I am trying to run the program it cannot allocate the size of memory that I need??

If you have time to check my code please do, there might be a mistake that I cannot spot.

Thanks in advance!

   #include <stdio.h>  


int main()  
{  
    int N, K, up, low, pos, flag=1 ;  
    scanf("%d %d\n", &N, &K);  
    int s[N], f[N], i=0;  
    while( scanf("%d %d\n", &s[i], &f[i]) != EOF)  { i++; }  
    i=0;  
    up=f[0];  
    low=s[0];  
    while(i < N )  
        {  
        if ( f[i] > up) up=f[i];  
        if ( s[i] < low) low=s[i];  
        i++;  
    }  
    int Kseek[up];  
    i=0;  
    while( flag )  
    {  
        pos = ( low + up ) / 2;  
        i=0;  
        Kseek[pos]=0;  
        while ( i < N)  
        {  
            if ( pos >=  f[i] )  
                        {  
                                Kseek[pos]=f[i]-s[i]+1+Kseek[pos];  
                        }  
                        else if ( pos >= s[i] && pos <f[i])  
                        {  
                                Kseek[pos]=pos-s[i]+1+Kseek[pos];  
                        }  
                        i++;  
                }  
        if ( Kseek[pos] == K ) flag=0;  
        else if ( Kseek[pos] > K )  
        {  
            i=0;  
            Kseek[pos-1]=0;  
            while ( i < N)  
                        {  
                             if ( (pos-1) >=  f[i] )  
                             {  
                                     Kseek[pos-1]=f[i]-s[i]+1+Kseek[pos-1];  
                             }  
                             else if ( (pos-1) >= s[i] && (pos-1) <f[i])  
                             {  
                                     Kseek[pos-1]=(pos-1)-s[i]+1+Kseek[pos-1];  
                             }  
                             i++;  
                    }  
            if ( Kseek[pos] > K && Kseek[pos-1] < K) flag=0;  
            else if ( Kseek[pos-1] == K ) {  pos-=1; flag=0; }  
            up = pos - 1;   

        }  
        else if ( Kseek[pos] < K)  
        {  
            i=0;  
            Kseek[pos+1]=0;       
            while ( i < N)  
                        {  
                             if ( (pos+1) >=  f[i] )  
                             {  
                                     Kseek[pos+1]=f[i]-s[i]+1+Kseek[pos+1];  
                             }  
                             else if ( (pos+1) >= s[i] && (pos+1) <f[i])  
                             {  
                                     Kseek[pos+1]=(pos+1)-s[i]+1+Kseek[pos+1];  
                             }  
                             i++;  
                }  
                if ( (Kseek[pos+1] > K && Kseek[pos] < K) || Kseek[pos+1] == K) {  flag=0; pos+=1; }  
            low = pos + 1;  



                }  


    }         
    printf("%d\n", pos);  
    return 0;  

}

Input files look always like this. Entries vary from 10 to 50000:

First row is always K and N and next are s[i], f[i] for the next N lines.

I'm having a hard time trying to understand what this binary search is searching for? — Anonymous, Nov 17 '14 at 16:00
It is searching for the number K. Either K == Kseek[pos] either Kseek[pos] > K > Kseek[pos+1]. The exercise is called Chocolate Factory, well, in a factory there are N sources of chocolate and one big tank. You are searching for the moment that the tank has exactly K litres of chocolate in it. Every source starts pouring chocolate at time si and stops at time fi (both integers). My objective is to find that time (pos) quick, so the algorithm i have written is using binary search with complexity Θ(nlogn). The boundaries are the first moment that one source starts pouring (low) and the last — ncppd, Nov 17 '14 at 16:12
Need to post sample input as that triggered failure, but was not expected to. This code readily fails with input like "1 1" "1 2" "3 4" "5 6" EOF as `while( scanf(...` stops at EOF rather than at `N`. — chux - Reinstate Monica, Nov 17 '14 at 16:17
which is "up". I start looking in the middle of "time" so pos = ( up + low )/2, and then modify the upper and low boundaries just by finding if Kseek[pos] > K or Kseek[pos] < K. In logn searches that time is found. Also consider that there may be a "changing point" ( the tank has less than K litres in one point and exactly afterwards it has more) where Kseek[pos] < K and Kseek[pos+1] > K. So breaking point is (pos+1). Sorry for my bad English. — ncppd, Nov 17 '14 at 16:20
No. The test cases always have elements. The first two are K and N, and the next N lines in the file are s[i] f[i]. For example, here the sources are N=200 and K=50536 (tank size) Next line is s[0]=369 f[0]=732, s[1]=595 f[1]=644 and so on (200 50536) (369 732) (595 644) (460 500)....... — ncppd, Nov 17 '14 at 16:23
`int Kseek[up]` should be `int Kseek[up+1]`. Consider "1 1" "1 1". — chux - Reinstate Monica, Nov 17 '14 at 16:30
It was one of the first things I tried to change but still, segfault. — ncppd, Nov 17 '14 at 16:33
@Anonymous VLA (variable length array) functionality has been available as an extension since the early 90s and was standardized in c99 and expanded upon in c11. — Vality, Nov 17 '14 at 16:34
Certainly some assignment is using an out-of-range index as in `Kseek[pos - 1]` and others. Add a test before each assignment to verify a legal index. Could also be a bad index with a read. — chux - Reinstate Monica, Nov 17 '14 at 16:36
Area _all_ value pairs like "411 949"` such that `s[i]` <= `f[i]`? Any negative values? any values > `INT_MAX`? Can you get code to fail will a small number of inputs, something like 5 rather than 200? — chux - Reinstate Monica, Nov 17 '14 at 16:39
I tried it, it still segfaults. I also put test points with printf from the start of the program, but there is no output. Only segmentation fault. Even before declarations! — ncppd, Nov 17 '14 at 16:44
Always { s[i] <= f[i] } ! No, there are no negative values, s[i] and f[i] are time variables. — ncppd, Nov 17 '14 at 16:45

score 1 · Accepted Answer · edited May 23 '17 at 10:26

I think it is something really trivial. Compiled your code with GCC and default options then dumped a.exe info with dumpbin from VC:

OPTIONAL HEADER VALUES
             10B magic # (PE32)
            2.23 linker version
            2E00 size of code
            4800 size of initialized data
             200 size of uninitialized data
            1570 entry point (00401570)
            1000 base of code
            4000 base of data
          400000 image base (00400000 to 0041BFFF)
            1000 section alignment
             200 file alignment
            4.00 operating system version
            1.00 image version
            4.00 subsystem version
               0 Win32 version
           1C000 size of image
             400 size of headers
           183F2 checksum
               3 subsystem (Windows CUI)
               0 DLL characteristics
>>        200000 size of stack reserve
>>          1000 size of stack commit
          100000 size of heap reserve
            1000 size of heap commit
               0 loader flags
              10 number of directories

Arn't the two things too small to keep your s[] and f[] on stack? I'd suggest recompiling with: gcc -Wl,--stack, ... Increase Stack Size on Windows (GCC)

I made also another, in-source mod: simply change VLA to fixed size ones (big enough) - no more stack overflows:

         1000000 size of stack reserve
            1000 size of stack commit

OK, my final update to this problem would be to ensure that enough of input data are passed in. You simpli ignore such case when EOF comes before all f[] and s[] values are scanfed. My suggestion is to change reading while() to for().

int i=0;  
for (i=0; i<N; i++) 
    scanf("%d %d\n", &s[i], &f[i]);

Thanks very much for your answer! I am using Ubuntu, are the gcc flags the same as in Windows? — ncppd, Nov 17 '14 at 18:29

This program passed my university's grader (all test cases) but segfaults in my pc

1 Answers1