SO (pun intended) I want to solve this question from HackerEarth: https://www.hackerearth.com/practice/data-structures/arrays/multi-dimensional/practice-problems/algorithm/the-wealthy-landlord/
This is my code:
#include <stdio.h>
#define ll long long
int main () {
ll int N;
scanf("%d", &N);
ll int i, j, a, b;
ll int TOTAL;
typedef struct {
ll int flag;
ll int count;
// int fc[N]; // farmer cost OR cost for farmer i
ll int *fc;
} land;
// check whether all of them have been
// initialised to 0
// printf("%d ", arr[2][2].count);
// yes
land arr[1000][1000];
for(i=0; i<1000; i++) {
for(j=0; j<1000; j++) {
arr[i][j].fc = (ll int *)calloc(N, sizeof(ll int));
}
}
ll int x1, y1, x2, y2, c;
ll int ta, tb; // temp a // temp b
for(i=0; i<N; i++) {
scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &c);
// the array index starts from 0
// so to match the inputs to the correct indices
// the inputs must be reduced by one
for(a=x1; a<=x2; a++) {
for (b=y1; b<=y2; b++) {
ta = a-1;
tb = b-1;
arr[ta][tb].count++;
if(arr[ta][tb].count >= 2)
arr[ta][tb].flag = 1;
arr[ta][tb].fc[i] = c;
}
}
}
ll int k;
for(i=0; i<1000; i++) {
for(j=0; j<1000; j++) {
if (arr[i][j].flag == 1) {
for(k=0; k<N; k++)
TOTAL += arr[i][j].fc[k];
}
}
}
printf("%lld", TOTAL);
return 0;
}
RESULT: Runtime Error (SIGSEGV)
Compilation Log: Compiled Successfully
Execution Log: Execution failed.
Segmentation Fault : This occurs because of an out-of-scope array index that is causing a buffer overflow, an incorrectly initialized pointer, etc. A signal is generated when a program either tries to read or write outside the memory that is allocated for it or to write memory that can only be read. For example, you are accessing a[-1] in a language that does not support negative indices for an array.
I've edited this code multiple times and fixed various issues by looking at various SO questions. Now it is so close to working, but it just makes a straight face and says segmentation fault. The worst kind of fault that gives you little to no hints on how it should be fixed. I am out of ideas!
ALSO - There probably is a better method to solve this problem which does not involve arrays inside a 2-D array of structures, but I would love to learn how to fix this segmentation fault.
Your line: land arr[1000][1000]; declares arr as an automatic variable, which means that space is allocated to it from the stack. Put simply, this stack is memory assigned for local use when a function is called (and main is really just a function called by the operating system when you run the program).
Typically, the amount of space available on the stack is limited - typically 16 - 64 kilobytes. However, your arr variable (assuming 8 bytes for a long long int and 8 bytes for a pointer) will require more than 24 megabytes. This is almost certainly what is causing your "Stack Overflow!"
A 'quick fix' to this problem is to declare the variable static. This means that space is allocated at compile time (or, more likely, at link time) and is 'locked' into memory while the program is running. (You may notice that the size of your executable file increases by 24 MB after you do this - depending on your platform!)
Here is a slightly modified version of your code, with this correction, along with a couple of other suggested improvements (all marked with the "///" comment delimiter:
#include <stdio.h>
#include <stdlib.h>
#define ll long long
int main() {
ll int N;
scanf("%lld", &N); /// The plain "%d" format expects an "int" argument - use "%lld" for "long long int"
ll int i, j, a, b;
ll int TOTAL = 0; /// If you don't INITIALIZE "TOTAL" it could start off with ANY value whatsoever!
typedef struct {
ll int flag;
ll int count;
// int fc[N]; // farmer cost OR cost for farmer i
ll int* fc;
} land;
// check whether all of them have been
// initialised to 0
// printf("%d ", arr[2][2].count);
// yes
static land arr[1000][1000]; /// Without "static" this array (~ 24 Megabytes) will overflow the stack!
for (i = 0; i < 1000; i++) {
for (j = 0; j < 1000; j++) {
arr[i][j].fc = (ll int*)calloc(N, sizeof(ll int));
}
}
ll int x1, y1, x2, y2, c;
ll int ta, tb; // temp a // temp b
for (i = 0; i < N; i++) {
scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &c);
// the array index starts from 0
// so to match the inputs to the correct indices
// the inputs must be reduced by one
for (a = x1; a <= x2; a++) {
for (b = y1; b <= y2; b++) {
ta = a - 1;
tb = b - 1;
arr[ta][tb].count++;
if (arr[ta][tb].count >= 2)
arr[ta][tb].flag = 1;
arr[ta][tb].fc[i] = c;
}
}
}
ll int k;
for (i = 0; i < 1000; i++) {
for (j = 0; j < 1000; j++) {
if (arr[i][j].flag == 1) {
for (k = 0; k < N; k++)
TOTAL += arr[i][j].fc[k];
}
}
}
printf("%lld", TOTAL);
return 0;
}
Feel free to ask for further clarification and/or explanation.