-1

I am solving the variable-sized array problem on hackerrank (https://www.hackerrank.com/challenges/variable-sized-arrays/problem)

I thought of this solution:

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    int n ,q, k, i, j, a[10000][10000];
    cin>>n;

    cin>>q;
    for (int w = 0; w<n; w++)
    {
        cin>>k;
        for (int x=0; x<k; x++)
        {
            cin>>a[w][x];
        }
    }
    for(int e=0; e<q; e++)
    {
        cin>>i>>j;
        cout <<a[i][j]<<"\n";
    }

    
        return 0;
}

It is working for 3 cases but for others, it is giving "Segmentation fault" error. I can't think of anything wrong with this code. How do I solve this?

Deepanshu Baisoya
  • 1
  • 2
    `a[10000][10000];` KABOOOOOM! Stack Overflow. – user4581301 Sep 17 '20 at 03:55
  • 1
    Since you aren't going to be able to get enough RAM for the naive approach you're trying here, I tried to look at the question brief at the link to see what this program is supposed to do so I can make a pitch for alternatives. It wants me to log in. That makes the link worthless and without it the question incomplete. I recommend summarizing the the challenge requirements here. – user4581301 Sep 17 '20 at 04:21
  • Learn what you can from the duplicate @phuclv pitched, but you're going to need more than that. If you move `a` off the stack or dynamically allocate, you'll still need at least 20 GB RAM to get a 100000 x 100000 element array (and that's assuming the smallest legal `int` of 16 bits, so you probably need probably 40 or 80 GB). There's going to be some sneaky trick that will greatly reduce the memory requirement. – user4581301 Sep 17 '20 at 04:26
  • The whole point of the hackerrank question is to see if you know how to create a variable sized array, but instead your code creates a fixed-size array of 10000 x 10000. – PaulMcKenzie Sep 17 '20 at 06:15
  • Hackerrank explicitly talks about variable length containers and also links to the documentation of such a std container. As they already mention such a container you should consider using that one. – t.niese Sep 17 '20 at 06:40

2 Answers2

0

A possible reason for segmentation fault maybe because of the fact that it is trying to access the memory location that is out of bounds.

The array that you have declared has a capacity of 10^4 but in the question it is mentioned that it can easily go up to 10^5. Thus in the last few cases where you are getting a segmentation fault, it's possibly trying to access the index greater than 10^4.

A quick fix would be to make your array sufficiently large.

Tanishq Vyas
  • 1,422
  • 1
  • 12
  • 25
  • Still won't work. The array would have to be 40-80 GB and it's extremely unlikely that HackerRank will provide that much memory. There will be a sneaky trick you can use to greatly reduce the memory requirement. – user4581301 Sep 17 '20 at 04:33
0

The constraints given on the question are

1 ≤ n ≤ 10^5 
1 ≤ q ≤ 10^5

You have declared your array a[10000][10000] which is 10^4. So when in your for loops, cin>>a[w][x] the range for w is till n, and n can be greater then 10000 which is not allocated to a[] .

Dharman
  • 30,962
  • 25
  • 85
  • 135
Mohit Sharma
  • 338
  • 2
  • 13
  • Still won't work. – user4581301 Sep 17 '20 at 04:01
  • @user4581301 Please elaborate where else there might be a segmentation fault in this code? The question was solving the segfault not the Hackerrank problem. – Mohit Sharma Sep 17 '20 at 04:03
  • Throwing 40-80 GB on the stack is a non-starter, and odds are really really good that HackerRank won't give you that much RAM even if you made it global or dynamically allocated. There's a sneaky trick that you and the asker (and me) have missed to eliminate the need for the array in the first place – user4581301 Sep 17 '20 at 04:14
  • Creating an array of pointers to integer arrays , hence the variable length arrays. Then keep assigned new arrays with new, while not dereferencing old ones. So in that sense, you will get variable size arrays. If there is some other trick, which I am still overlooking, would love to know more about. – Mohit Sharma Sep 17 '20 at 04:25
  • The challenge description is walled off from me so I can't help much, but maybe the problem can be processed in stages or with a sparse array. I suspect the goal is no array at all. – user4581301 Sep 17 '20 at 04:30
  • 1
    @MohitSharma -- `std::vector>` is all that's needed. No need for `new[]` whatsoever. – PaulMcKenzie Sep 17 '20 at 06:31