Code is working fine in my system but coursera autograder is giving me unknown signal

Question

Task -- The goal in this code problem is to implement the binary search algorithm.

Input Format -- The first line of the input contains an integer n and a sequence a0 < a1 < ... < an−1 of n pairwise distinct positive integers in increasing order. The next line contains an integer k and k positive integers b0,b1,...,bk−1.

Constraints -- 1 ≤ n,k ≤ 10^4; 1 ≤ a[i] ≤ 10^9 for all 0 ≤ i < n; 1 ≤ b[]j ≤ 10^9 for all 0 ≤ j < k;

Output Format -- For all i from 0 to k−1, output an index 0 ≤ j ≤ n−1 such that aj = bi or −1 if there is no such index.

I am using code blocks with c++11 compiler. I have already tried stress testing and got correct results in my system. But coursera autograder is giving me unknown signal 11. In some problems it gives unknown signal 8. Can anyone tell me the possible reason behind this.

int binary_search(const vector<long long> &a, long long x) {
  size_t left = 0, right = (size_t)a.size()-1;
  size_t mid = 0;
  while(left<=right){
    mid = (left+right)/2;
    if(x < a[mid]){
        right = mid-1;
    }
    else if(x > a[mid]){
        left = mid+1;
    }
    else return mid;
  }
  return -1;
}
int main() {
  size_t n;
  std::cin >> n;
  vector<long long> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  size_t m;
  std::cin >> m;
  vector<long long> b(m);
  for (size_t i = 0; i < m; ++i) {
    std::cin >> b[i];
  }
  for (size_t i = 0; i < m; ++i) {
    //replace with the call to binary_search when implemented
    std::cout << binary_search(a, b[i]) << ' ';
  }
}

Actual result that i got in autograder.

Failed case #4/36: unknown signal 11 (Time used: 0.00/1.00, memory used: 40071168/536870912.)

Not related I guess, but why are you using *long long* for values less than 109? — Damien, Jun 06 '19 at 07:44
Even 10⁹ will fit in plain old `int` (it is running on at least 32-bit platform). 2¹⁰ ≅ 10³, so 10⁹ ≅ 2³⁰ and `int` on 32-or-more-bit platform can hold -2³¹ … 2³¹-1. — Jan Hudec, Jun 06 '19 at 08:30
@JuniverHazoic **Algorithmic Toolbox by University of California San Diego & National Research University Higher School of Economics** — Prakirti Lakhotiya, Jun 06 '19 at 08:40
Prakirti, it is a violation of Coursera's Honor Code to post your solutions publicly. Please redact out some parts of your code. — Artur Riazanov, May 17 '20 at 16:11

Max Langhof · Accepted Answer · 2019-06-06T08:39:20.440

4

If the vector has e.g. size 2, then you initialize left = 0, right = 1 and mid = 0. left <= right so you calculate mid = 0 and check if x < a[0]. If that happens, you now set right = -1. In unsigned arithmetic, that is a really large number. Your loop continues because 0 <= really large number, you calculate mid = half of really large number and access the vector there. That's UB and gets your program killed.

Switching to signed types means right = -1 is indeed smaller than left = 0 and terminates the loop.

edited Jun 06 '19 at 08:39

answered Jun 06 '19 at 08:32

Max Langhof

23,383
5
39
72

2

Actually, that happens if `x < a[0]` for any size of the vector, because `right` will be decreasing until it gets to this. – Jan Hudec Jun 06 '19 at 08:40

score 2 · Answer 2 · answered Jun 06 '19 at 07:39

2

Don't know about Coursera test cases, but your code will definitely fail with two edge cases:

1) empty input vector a -> you'll get underflow in line right = (size_t)a.size()-1;. In other words, right will become a large positive value, you'll enter in the loop and try to retrieve a[mid] where mid will be some large positive index. Of course, trying to get this from an empty array would result with an error.

2) left+right too large -> overflow -> bug found in many binary search implementations, even in books :) Use instead mid = (right - left) / 2 + left;

answered Jun 06 '19 at 07:39

Miljen Mikic

14,765
8
58
66

In **Constaints** paragraph, OP provides some information on the test cases – Damien Jun 06 '19 at 07:42
@Damien you are right, those two edge cases shouldn't occur in this test suite then. – Miljen Mikic Jun 06 '19 at 07:46
In input format, it is already mentioned `1 <= n,k <= 10^4`. So I don't think this may be the problem, but 2nd one sounds correct. – Prakirti Lakhotiya Jun 06 '19 at 07:46
2

@PrakirtiLakhotiya Please correct your question, put `10^4` instead of `104`, and `10^9` instead of `109`. – Miljen Mikic Jun 06 '19 at 07:50
@MiljenMikic I have tried both the possible changes that you have suggested. Still getting same error. Maybe there are some memory leaks or something which i am not able to figure out. – Prakirti Lakhotiya Jun 06 '19 at 08:01
@PrakirtiLakhotiya The code you show has no memory leaks. – Max Langhof Jun 06 '19 at 08:13

score 0 · Answer 3 · answered Jun 06 '19 at 08:19

0

By changing all size_t to long, it works correctly. The unknown signal 11 means segmentation fault, i.e. something is wrong with memory access. So changing all size_t to long increase the range of vector and hence letting in fit more values which fixes the memory access problem.

answered Jun 06 '19 at 08:19

Prakirti Lakhotiya

35
7

cppreference: *std::size_t can store the maximum size of a theoretically possible object of any type (including array).* I don't understand what happens! – Damien Jun 06 '19 at 08:25
1

@Damien With this added information the reason is pretty clear: Some `size_t` value is supposed to be negative at some point (but instead is a huge positive value due to unsigned wraparound). There are only two places in the program where that can happen. – Max Langhof Jun 06 '19 at 08:34
@MaxLanghof Clear indeed now. Good answer also. I remenber now a recommendation of Bjarne Stroustrup that unsigned int should be avoided when operations are performed on it. – Damien Jun 06 '19 at 09:43

Code is working fine in my system but coursera autograder is giving me unknown signal

3 Answers3