Help me to debug the catch

admin
codechef

#1

for the problem http://www.codechef.com/problems/MOU1H , i designed a code based on Suffix array with LCP but i don’t know why one code http://www.codechef.com/viewsolution/4557076 is accepted and another code http://www.codechef.com/viewsolution/4557071 is gave SIGSEGV error.

In accepted code i declare extra array B[100010] at line 9 but in second code i comment this array
and in both code i don’t use this array … you can change array name at line 9 as you want but if you comment the array then its shows runtime error.

Admin please help me to finding out the catch.


#2

Hi maheiitr,
I modified the C array and resized it to 10^5, then it got AC.
http://www.codechef.com/viewsolution/4560839

- int T,x,y,n,A[100003],SA[100003],RA[100003],temp[100003],C[510];
- int B[100003];
+ int T,x,y,n,A[100003],SA[100003],RA[100003],temp[100003],C[100003];
+ 

It is because the RA[] values can be up to 10^5, but your old array was just ~500 big. In your old code, I suspect, that the C array lies just behind the B array in the memory. That’s why, if you access for example C[510], it will actually be B[0]. It is just a typical effect of the C++ language, where access out of memory is hard to catch :slight_smile:

--------C-----------------------B------------------
| ~~~~~500~~~~~~|~~~~~~~~~~~~~10^5~~~~~~~~~~~~~~~~|    
---------------------------------------------------

#3

same problem i also face on spoj


#4

but why we go beyond the bound of C array ,its mention in qn that diff b/w two adj values is [-100,100] so maximum we can use C array upto 300 but i took 510 size that’s enough for qn requirement


#5

RA[] value goes upto 300 not 10^5


#6

It goes up to 10^5 because the each of the suffixes must have a different ranking. Otherwise, how are you going to differ each entry of the suffix array? You compare with the RA[]'s, which can go up to 10^5.


#7

oh thanx buddy for pointing out my mistake