Segmentation error! Plz help

[Knightrider29]

Link to the problem: http://www.codechef.com/problems/LECANDY

I was just desperate to use a recursive function though I've solved the problem already using a simple for loop instead of defining a function.
However plz tell me what's the (segmentation) error in this?

#include <iostream>
using namespace std;

void ans(long long c, int a[], int n)
{
    if(c<0 && n==0) cout<<"No"<<endl;
    if(c>0 && n==0) cout<<"Yes"<<endl;
    else {ans(c-a[n-1], a, n-1);}}

int main()
{
    int T; cin>>T;
    while(T--)
    {
        int n;
        long long c;
        cin>>n>>c; int a[n]; 
        for(int i=0; i<n; i++) {cin>>a[i];}
        ans(c, a, n);
     }
    system("pause");
    return 0;
}

[Smac89]

One of the bad habits people pick from competitive programming is taking too many shortcuts and hoping the compiler will fix stuff for them and this leads to unpredictable/unreadable code. The answer to your problem is that you have not allocated memory for your array. Just because you read n and then declare a as having size n doesn't mean the array actually has that size.

To fix it:
int *a = new int[n];

In most situations, people who are keen on speed will decide to sacrifice memory in order to avoid having to allocate more memory at runtime and the way to do that is to declare your array on the stack with a constant size (preferably the maximum size the tests will ever require).

int a[101];

[Knightrider29]

Just because you read n and then declare a as having size n doesn't mean the array actually has that size. 

Can you please explain more about it?

[Knightrider29]

Also how about this code?

#include <iostream>
using namespace std;

void ans(long long c, int *a, int n)
{
    if(c<0 && n==0 ) cout<<"No"<<endl;
    if(c>0 && n==0) cout<<"Yes"<<endl;
    else {ans(c-a[n-1], a, n-1);}}




int main()
{
    int T; cin>>T;
    while(T--)
    {
        int n;
        long long c;
        cin>>n>>c; int* a; 
        for(int i=0; i<n; i++) {cin>>a[i];}
        ans(c, a, n);
        }
    system("pause");
    return 0;
}

[Smac89]

Just because you read n and then declare a as having size n doesn't mean the array actually has that size.

It simply means that doing
int a[n] doesn't create an array of size n unless n is a constant. Just as I did in my later example, int a[101] works because 101 is a constant.

As for your second code, line 20 should be:

cin >> n >> c;
int* a = new int[n]; 

[Knightrider29]

Yes, you said that it doesn't create an array but why not?

And regarding my second question, why can't I just write

 int* a 

The code you've given is absolutely fine with me, but I just have a small doubt on the above one!

Ps: Thanks for the help! (:

[Aaron Vienneau]

Static arrays are allocated on the stack and the size of the array must be known at compile time; that's why constants are the only acceptable parameter when creating an array like:

int myArray[5];

Dynamic arrays are allocated on the heap and the size of the array can be deferred to compile time. The new operator can allocate and return the address of a memory block in real-time and assign it to a suitable pointer. So statements like the following, do just that:

int size;
std::cin >> size;
int* myArray = new int[size];

The fact that your program compiled at all, with code like:

int size;
std::cin >> size;
int myArray[size];

is an anomaly to me, because it directly violates the syntax for static arrays, as the parameter size needs to be known at compile time for the stack to allocate enough space for the array. It probably works because the compiler is optimizing it to its dynamic counter-part.

You can't write int* a because that only allocates enough memory for a pointer-to-an-int, but NOT enough memory for an array of integers of an unknown size.

You may want to study up on Static Vs. Dynamic Arrays; Not to be dismissive, but there are hundreds of articles which probably explain this a lot better than me :)

[Knightrider29]

^awesome! Ty Aaron! :)

Just a last doubt: Though int* a allocates memory for a pointer-to-an-int, I can use a+index (a[index]) to travel across the array right?

[Smac89]

Knightrider29 wrote:

Yes, you said that it doesn't create an array but why not?

It won't create an array of size `n` is what I mean. There are 2 ways to create an array, allocate memory for an array on the stack i.e. the size of the array is known at compile time or create the array on the heap, the size of the array is only known at runtime.

In your case, `n` is not a constant, so the compiler cannot deduce what the size of the array is, which means that the array you have at runtime does not have the size you think it does. The size of the array in that case is undefined i.e. one cannot say for sure that the size of the array is `n`. The compiler might decide to initialize it to some value, but there is no guarantee what that size will be, why? Because the value of `n` is not known until the program is running and the user types a value in.

And regarding my second question, why can't I just write

int* a

You can't just write int *a because that declares a pointer to a block of unknown memory. A pointer references a block of memory on the heap. This means that declaring a pointer without assigning it to reference a part of memory is like declaring an array without a constant size or through the use of dynamic allocation. The pointer will simply point to whatever memory block the compiler decides which means that if you use that pointer as an array, the result will be another segmentation fault.

The problems you have mentioned seem to have a common theme which I think should be evident to you by now. Memory does not magically appear out of no where. When you are programming in c/c++, memory management is key and knowing what part of memory belongs to your program is even more important if you want to avoid the OS yelling at you.

[Knightrider29]

Thanks a lot! (:
Any good online resources you can suggest regarding this topic?

[Aaron Vienneau]

Though int* a allocates memory for a pointer-to-an-int, I can use a+index (a[index]) to travel across the array right?

Not quite. Not to beat a dead horse, but int* a only allocates enough space for a pointer to a potential array. It's up to the new operator, in this instance, to create space for the array and assign the address back to the pointer a.

Conceptually, you can think of it like:

int* a; creates a pointer:

[a]--------->

a = new int[5] allocates space on the heap for 5 ints and assigns it back to a:

[a]-------->[int][int][int][int][int]

So if you try to use a+index (a[index]) on a before you use new to allocate the array, you'll end up traversing memory that you did not allocate and most likely corrupt your program.

[Aaron Vienneau]

Resource: http://www.cplusplus.com/doc/tutorial/dynamic/

[ne555]

> The answer to your problem is that you have not allocated memory for your array.
> Just because you read n and then declare a as having size n
> doesn't mean the array actually has that size.
variable length arrays are not allowed in c++ (they are in c) so basically, your code does not compile.
It works for you because your compiler violates the standard and implements an extension that allows you to do that

However, the extension probably works in the way that you intended. int array[size]; does create an array of size integers.


About your issue, you are missing the c==0 and n==0 base case.