YMSeah's blog

By YMSeah, history, 3 months ago, In English

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. Here are nawa's codes and his fix using a similar change: runtime error 129082770 vs accepted 129084946.

I am not a native C++ user and I cannot figure out what went wrong. I will be grateful if anyone can shed some light on what may have caused this error.

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YMSeah (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks man, I really appreciate it.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by YMSeah (previous revision, new revision, compare).