_jarvis_'s blog

help needed in sqrt decomposition problem
By _jarvis_, history, 10 years ago, In English

I was learning sqrt decomposition, to practise for the same i was solving http://www.spoj.com/problems/UNTITLE1/ problem on spoj, but i am continously getting SIGSEGV error for the same, i tried my level best to debug it but was unable to solve it,moreover there is no online reference for this particular problem,

i know the hopes of getting myself help is low but still if someone wanna help , here is my code http://ideone.com/jePYPu , i tried to make it as clean as possible.

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

»
10 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

It is not true that . Counter example: n = 3.

Compiling with g++ -g -fsanitize=address -fsanitize=undefined and executing with n = 3 input gives this message:

==23853==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60200000f000 at pc 0x000000401cf2 bp 0x7ffc7c7f9e70 sp 0x7ffc7c7f9e60
READ of size 8 at 0x60200000f000 thread T0
    #0 0x401cf1 in initialise() /tmp/A.cpp:99
    #1 0x401ea7 in main /tmp/A.cpp:113
    #2 0x7f4a48751740 in __libc_start_main (/usr/lib/libc.so.6+0x20740)
    #3 0x4011f8 in _start (/tmp/A+0x4011f8)
... (truncated)

Line 99 is bsum[(int)i/rootn]+=arr[j];. As n = 3, rootn = 1 and sz = bsum.size() = 2, when i reach n - 1, bsum[(int)i/rootn] will be out of bounds, causing undefined behavior.

Unfortunately even if you fix this bug you will still get TLE.

→ Reply