You are not logged in. Please login at www.codechef.com to post your questions!

×

Help me to debug the catch

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.

asked 13 Aug '14, 11:23

maheiitr's gravatar image

5★maheiitr
2.5k162324
accept rate: 25%

edited 13 Aug '14, 12:54

same problem i also face on spoj

(13 Aug '14, 11:42) maheiitr5★

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 :)

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

answered 14 Aug '14, 15:08

gdisastery1's gravatar image

4★gdisastery1
1.9k41317
accept rate: 11%

edited 14 Aug '14, 15:09

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

(14 Aug '14, 15:36) maheiitr5★

RA[] value goes upto 300 not 10^5

(14 Aug '14, 15:38) maheiitr5★
1

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.

(14 Aug '14, 15:47) gdisastery14★

oh thanx buddy for pointing out my mistake

(14 Aug '14, 22:24) maheiitr5★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,343
×1,382

question asked: 13 Aug '14, 11:23

question was seen: 757 times

last updated: 14 Aug '14, 22:24