-1

This is the problem from online hackerrank online platform. Nikita and the Game

I coded this and my solution passes only the given testcases, it is giving segmentation fault for other testcases on submit.
I compared my approach with editorial solutions, and one of the solution uses same approach as mine(the binary search approach to find the index at which we'll be able to split the array).

But i can't figure out why is it giving the segmentation fault.

#include <bits/stdc++.h>
#define lld long long

using namespace std;


lld isPossible(vector<lld>&pre_sum, lld start, lld end){
    
    lld low = start-1;
    lld high = end;
    
    while(start<=end){
        lld mid = (start+end)/2;
        lld left_sum = pre_sum[mid] - pre_sum[low];
        lld right_sum = pre_sum[high]- pre_sum[mid];
        
        if(left_sum == right_sum) return mid;
        if(left_sum < right_sum) start = mid+1;
        if(left_sum > right_sum) end = mid-1;
    }
    return -1;
}

lld calcAns(vector<lld>&pre_sum, lld start, lld end){
    //cout<<start<<" "<<end<<"\n";
    lld idx = isPossible(pre_sum, start, end);
    //cout<<idx<<"\n";
    if(idx == -1) return 0;
    return 1 + max(calcAns(pre_sum, start, idx), calcAns(pre_sum, idx+1, end));
    
}
/*
 * Complete the arraySplitting function below.
 */
lld arraySplitting(vector<lld> arr) {
    
    vector<lld> pre_sum(arr.size() + 1);
    pre_sum[0] = 0;
    
    for(lld i=0; i<arr.size(); i++){
        pre_sum[i+1] = pre_sum[i] + arr[i]; 
    }
    
    lld ans = calcAns(pre_sum, 1, pre_sum.size()-1);
    //cout<<ans<<"\n";
    return ans;
}

int main()
{

    lld t;
    cin >> t;

    for (lld t_itr = 0; t_itr < t; t_itr++) {
        lld arr_count;
        cin >> arr_count;

        vector<lld> arr(arr_count);

        for (lld arr_itr = 0; arr_itr < arr_count; arr_itr++) {
            lld arr_item;
            cin>>arr_item;
            arr[arr_itr] = arr_item;
        }

        lld result = arraySplitting(arr);

        cout << result << "\n";
    }

    return 0;
}

Explanation of code:

isPossible function finds the index at which the sum of the left part [start....mid] of the array is equal to the right part [mid+1.....end].

calcAns calculates the no of possible such indexes in a way that once it will finds such index, it will ignore one part and finds in other part if any such possible. It will calculate maximum no. of such possible splittings.

arraySplitting just calculates the prefix sum array pre_sum and is one size more than the actual array, i.e first index have sum zero, so that it will ease calculations later while calculating sums between a range. It calls calcAns function for further processing.

EDIT: i want to learn debugging cases without actually having to use debugger as testcases are not downloadable during a contest submission. so i want to learn what thing's am i missing which causes segmentation faults as i started training myself for programming contests. If someone can predict on seeing the code that these type of tescases is possible where my code probably can give segmentation fault, will be helpful. This is what i'm actually looking for, otherwise it is not any benefit that i debug large testcases by using gdb on setting breakpoints after the contest.

user13145713
  • 109
  • 8
  • Even if you use competition or online judge sites as recreation and not for learning, please don't incorporate the bad habits so common on such sites into your code. Habits, good and bad, tend to stick, so it's better to use good habits whenever possible. – Some programmer dude Sep 09 '20 at 10:28
  • Recommended reading: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice – Stef Sep 09 '20 at 10:45
  • Do you know which test cases your code is segfaulting on? More importantly, do you know on which line of the code the segfault happens? Can you add `std::cout << "We're here in the code" << std::endl` statements in your code and execute it to find out where it segfaults? – Stef Sep 09 '20 at 10:48
  • 1
    Segfaults happen most often when you try to dereference a pointer with `*` or `[]` while pointing to something you don't own. For instance, `pre_sum[mid]` could result in a segfault if `mid` is not a number between `0` (included) and the length of the array (excluded). In your code, I notice the very suspicious assignment `low = start-1;`, followed a few lines later by `pre_sum[low]`. What is the logic of `low = start-1`? Why start at `start-1` rather than at `start`? If `start` is ever 0, this could be your segfault. – Stef Sep 09 '20 at 10:52
  • 1
    I strongly suggest adding `std::cout << "values: " << low << ',' << start << ',' << mid << ',' << end << std::endl;` at the beginning of the while loop, so you can know the values of your variables just before the segfault. – Stef Sep 09 '20 at 10:55
  • @Stef `start` always start from 1, `low = start-1` will help in computing sum including `start` index, that's why i've added first element in the pre_sum vector to be 0 – user13145713 Sep 09 '20 at 12:26
  • @Someprogrammerdude like what habits..? are u talking about `using namespace std;` – user13145713 Sep 09 '20 at 12:28
  • Not only [`using namespace std;`](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice), but also things like [`#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) and `#define lld long long`. The time limits are for the running of the code, not for the writing of the code (and considering the `#include` not the compile time either). – Some programmer dude Sep 09 '20 at 12:36
  • You mention (and the code indicates) binary search. But that requires that the data you search is *ordered*. Is the data you search through ordered? – Some programmer dude Sep 09 '20 at 13:39
  • 1
    @Someprogrammerdude yes, indeed the data is ordered as i'm applying binary search on prefix sum which will always be in increasing order as the elements are always positive. – user13145713 Sep 09 '20 at 16:18

1 Answers1

0

The first step to fixing the issue is to determine where the segfault is occurring.

You can debug the program using gdb, step, set breakpoints etc.

Also add debug-couts as suggested in the comments.

You could add defensive checks to the methods, e.g. compare the indices low, mid, high against the size of the vector. It's also possible that the vector capacity setting could cause an out-of-memory exception so you should add try-except handlers around the code as well.

Alternatively you can use a library that catches the segfault and provides a stack trace so you can see where the segfault originates, e.g. https://github.com/certik/stacktrace

Also see related questions such as how to debug c++ runtime errors

Den-Jason
  • 2,395
  • 1
  • 22
  • 17