Regarding CHEFSHIP - Passing by value generates SIGSEGV

In the May20 Cook contest, there was a problem on Strings (CHEFSHIP).

I am using Z-algorithm to solve this, and below are two solutions with only one diff -

Also, the SIGSEGV gets fixed if I check i+i < n and n-2*i >= 0.
Check how this SIGSEGV goes away here on code3-sigsegv-fixed.

This is weird, how can passing a string by value generate wrong z-array?

-ve index?
If z[i] >= i is True, it pretty much means that i+i<n, which also means n-2*i>0.
So, I am never actually accessing -ve index provided that my z-array is correct.

Passing by value throws SIGSEGV, and that’s why I am confused how can that return an invalid z-array

1 Like

Your code accesses the out of bound indexes in both.
https://www.codechef.com/viewsolution/33327766
Your code with debug flags crashes on submission.

I learnt what a Z array is, and z[i]\ge i implies i+i\le n. You may access the nth index. To fix that, just increase the size by 1.
https://www.codechef.com/viewsolution/33327912

3 Likes