Unusual Runtime Error when performing Mo's Algorithm in C++

Правка en1, от YMSeah, 2023-12-11 04:41:17

I ran into a runtime error when trying to solve 1514D - Cut and Stick with Mo's Algorithm. Part of the problem requires one to find the counts of an element within a range if it's greater than or equal to about half the counts of elements in the range. One way to solve it is to use Mo's Algorithm to keep track of the most common element in range and its counts.

I sort the queries in the standard way where the left boundaries are grouped together in blocks of about sqrt of the number of elements. Within a "left block", the right queries are sorted in increasing order if the "left block" is an even block, otherwise it is sorted in decreasing order (so that the right points zigzag left-right-left-right through alternating blocks).

I have found that using the following within the sort criterion gives a runtime error (235446182):

if (block1 == block2) {
    // to ensure that the right portion sweeps in alternate directions between adjacent blocks
    if (block1% 2 == 0 && r < other.r) {
        return true;
    }
    if (block1 % 2 == 1 && r >= other.r) {
        return true;
    }
}

and the following does not (235448205).

if (block1 == block2) {
    // to ensure that the right portion sweeps in alternate directions between adjacent blocks
    if (block1% 2 == 0 && r < other.r) {
        return true;
    }
    // if (block1 % 2 == 1 && r >= other.r) { // This gives run time error
    if (block1 % 2 == 1 && r > other.r) {
        return true;
    }
}

I also see that I am not the only person who faced this problem and fixed it with a similar change: runtime error 129082770 vs accepted 129084946.

It will be helpful if someone can shed some light on what may cause this error. I think that it likely occurred during the sorting process, or during the handling of the queries.

Теги mos algorithm

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский YMSeah 2023-12-11 05:37:03 9
en2 Английский YMSeah 2023-12-11 04:48:12 239 (published)
en1 Английский YMSeah 2023-12-11 04:41:17 1965 Initial revision (saved to drafts)