search

stevenhalim / cpbook-code

CP4 Free Source Code Project (C++17, Java11, Python3 and OCaml)
2k stars 493 forks source link

Wrong allocation size lead to runtime error #107

Open fbrunodr opened 1 year ago

fbrunodr commented 1 year ago

https://github.com/stevenhalim/cpbook-code/blob/26fb7376417799f8b84b504d46ea7c8c0cf71c29/ch9/SparseTable.cpp#L17-L22

In line 17 we assign P2 a size of L2_n, implying we have the range [0,L2_n) available. Then we iterate i through [0,L2_n] and assign P2[i]. This leads to a problem when i = L2_n. This is a really hard to catch bug, as C++ usually allocate more size than necessary, but this very mistake has got me a runtime error in problem https://www.codechef.com/problems/TALCA?tab=statement

wqweto commented 1 year ago

Both P2 and L2 has to be bigger i.e. should be

    P2.assign(L2_n + 1, 0); 
    L2.assign((1<<L2_n) + 1, 0);

These off-by-one errors both show up when _GLIBCXX_DEBUG is defined.