I ran into a runtime error when trying to solve [problem:1514D] 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 ([submission: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 ([submission: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 [user:nawa,2023-12-11]'s codes and his fix using a similar change: runtime error [submission:129082770] vs accepted [submission: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.
↵
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 ([submission: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 ([submission: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 [user:nawa,2023-12-11]'s codes and his fix using a similar change: runtime error [submission:129082770] vs accepted [submission: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.
