SIGSEGV in BEARSEG LTIME47

general
1

I tried to attempt the problem BEARSEG for 50 pts, but got SIGSEGV in the second sub-task. It would be a great help if somebody could pin-point where exactly was the SIGSEGV error occuring. Thank you.

problem

SIGSEGV solution: solution

edit:I know why SIGSEGV occurs, I just want to know where is it occurring in my code.

1 Like
2

SIGSEV basically is an error related to memory(array index goes out of bounds).

To prevent you can use STL map instead of an array for hashing.

map acts on key:value as mp[key]=value.

1 Like
3

I too got SIGSEGV in 3rd subtask

4

yes,I used STL but still array size is too large

5

Seems like your code fails on the line op[k++]=(ps[j]-ps[i-1])%p; OR op[k++]=ps[j]%p; .
Your generate() function is creating n*(n-1)/2 values at kth positions.
subtask 1. 1 ≤ N ≤ 100 passes because of the above condition while the second subtask 1 ≤ N ≤ 1000 fails because of the array limit set to 10005. Try changing your approach.

2 Likes
6

Hey @qruiger_116 In problem statement N size could be as large as 10^5 but your arr size is at max 10005

this line causing SIGSEGV

#define lim 10005

change it to #define lim 100005

2 Likes
7

@adhish_kapoor Please read what I’ve asked, thank you for suggesting how to avoid SIGSEGV in the future but I want to know why did I get it in the first place?

8

Please read the problem statement,
for Subtask#2
1 ≤ N ≤ 1000
I was aiming to clear only the first two subtasks.

9

I am using prefix sum to solve the problem. The same solution is mentioned in the editorial for subtask#2 . Can you shed some more light on n*(n-1)/2 ?
https://www.codechef.com/viewsolution/13411653
In this submitted solution the lim was set to 100005 but still I got SIGSEGV

10

@qruiger_116

Please note that your lim is always 10005…but size of array where sum of all subarrays is to be stored can be greater than 10005.

For example:- if 3 elements are there there are 6 subarrays possible.

So,for 1000 it will be obviously greater than 1005.

Hope this clears your doubt.

2 Likes
11

Hey @qruiger_116 your code fails on the line op[k++]=(ps[j]-ps[i-1])%p; OR op[k++]=ps[j]%p;

see https://www.codechef.com/viewsolution/13413175

lim changed to 1000000 because we get (n)*(n-1)/2 segments

2 Likes
12

@srikanth_16

Exactly,I have also mentioned this thing below.

13

How did you conclude that this particular line op[k++]=(ps[j]-ps[i-1])%p; was causing SIGSEGV?

14

see in your code there are two nested loops in generate() function and k gets incremented at each iteration so k will be as big as 10^6 for worst case input. we need adjust array size accordingly…

2 Likes
15

On increasing value of lim, your code passed another test case here

The error is in your generate(). The value of k heavily overshoots the allowed limit.

For n=5, your k went upto 16. Others were right when they pointed k being the root of your problems dear.

1 Like
16

Many Thanks. That cleared my doubt!

1 Like
17

Hey, sure it can be solved using prefix sum method. Also refer to this question. https://www.hackerrank.com/challenges/maximum-subarray-sum This question is similar to the LTIME47 question. Hope this link helps. Also, prefix sum array requires only O(n) memory. Refer to this solution and try solving this question by yourself. https://www.hackerrank.com/challenges/maximum-subarray-sum/submissions/code/39930434

2 Likes
18

hey … you can probably use these properties to avoid this SISGEV
(a+b)%c=(a%c+b%c)%c
and (a-b)%c=(a%c-b%c+c)%c

1 Like
19

@marshal_roxx Thanks for the tips but the SIGSEGV in my code was due to the overflow in array and not due to overflow in datatype.