pranet's blog

Resolved: 191-C Fools and Roads : a strange runtime error
By pranet, 10 years ago, In English

8840553

Could anyone please point out my error in this one? I'm getting a runtime error whenever I call the following assertion in my lca() function

int x=firstOccurance[u];
int y=firstOccurance[v];
assert(x>=0 && x<m);
assert(y>=0 && y<m);

which is weird since I specifically ensure that this is not possible by running the following in main() after generating firstOccurance[]


for(int i=1;i<=n;++i)
  {
    assert(firstOccurance[i]>=0);
    assert(firstOccurance[i]<m);
  }

and this part happens to pass the assertion tests.

I have tried many random samples with n=100000 on my system, but could not replicate this error.

Thanks

Update: Corrected thanks to catlak_profesor_mfb

Since n was 100000,I had taken a size of 500000 for my segment tree which seemed to be sufficient. Unfortunately since the segment tree was on my order[] array, which has a size of 2*n-1, 500000 wasn't sufficient after all.

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Try to use gdb or some other debugger because for example when you access out of bounds of your vectors or arrays, everything messes up. Thats why you can not be sure if you modified a variable or not. Once I had an array with 10000 element. my code was trying to access out of memory bounds. The content of some other variable was changing. I was almost driving crazy :D

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That is exactly what I'm asserting for, to prevent going out of bounds. And all my vectors and arrays seem to be sufficiently large.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dude...that comment really helped. "Accessing out of memory bounds". Found the error . Thanks a lot!

    → Reply