WanjiabaoCQ's blog

A……mysterious RE？
By WanjiabaoCQ, history, 11 months ago, In English

This is what happened:

I was working on a WQS-Binary Search(Alien's Trick) problem today: CF125E. It's a template with many details; I wrote a bit over 100 lines of code. However, a few Runtime Errors (RE) submissions piqued my interest.

First was this RE on test 11: link. It was submitted using C++23. Then, without changing the code itself, I just switched the language to C++17, and it became WA (Wrong Answer) on test 14. The Checker Log showed Exit code is -1073741819.

After some debugging, it became RE on test 18: link. After some investigation, I suspected the issue might be with my sorting function. I had two sorting functions. The first sorted edges by weight ascending, and if weights were equal, edges connected to node 1 would be placed first. The second function reversed that priority for equal weights.

bool cmp1(edge x,edge y){
    if(x.w==y.w) return (x.u==1 || x.v==1);
    return x.w < y.w; 
}
bool cmp2(edge x,edge y){
    if(x.w==y.w) return (y.u==1 || y.v==1);
    return x.w < y.w;
}

I recalled encountering mysterious REs twice before on a similar problem on Luogu: my submission records, scoring 30 and 40 points respectively. Back then, modifying the sort function also fixed it.

So, I made a change: I manually recorded whether an edge was connected to node 1 within the struct, like this:

struct edge{
    int u, v, w, id;
    bool is1;
};
bool cmp1(edge x, edge y){
    if(x.w == y.w) return x.is1 > y.is1;
    return x.w < y.w; 
}
bool cmp2(edge x, edge y){
    if(x.w == y.w) return x.is1 < y.is1;
    return x.w < y.w;
}

Submitting this with C++20 worked and passed. It also passed with C++17.

I feel this is an important issue for me since it's happened two days in a row. I urgently want to understand the root cause of the REs to prevent similar problems in the future. Thank you.

Translated by Deepseek.

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

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

But I can passed p5633 on Luogu with these wrong codes,it's so mysterious.

They're my wrong codes on this problem yesterday:

bool cmp1(edge x,edge y){
	if(x.w==y.w)return (x.u==1||x.v==1);
	return x.w<y.w; 
}
bool cmp2(edge x,edge y){
	if(x.w==y.w)return (x.u!=1&&x.v!=1);
	return x.w<y.w;
}

Chinglish

→ Reply
»
11 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Your original functions

bool cmp1(edge x, edge y){
    if (x.w == y.w) return (x.u == 1 || x.v == 1);
    return x.w < y.w;
}
bool cmp2(edge x, edge y){
    if (x.w == y.w) return (y.u == 1 || y.v == 1);
    return x.w < y.w;
}

do not define a strict weak ordering.

For example, suppose you have two edges a and b such that:

  • a.w == b.w
  • a.u == 1, b.u == 1

Then:

cmp(a, b) == true
cmp(b, a) == true

This violates asymmetry, which is one of the core properties of strict weak ordering.

What is a strict weak ordering?

A strict weak ordering is a binary relation $$$ \lt $$$ on a set $$$S$$$ that satisfies:

  1. Irreflexivity: For all $$$x$$$ in $$$S$$$, it is not the case that $$$x \lt x$$$.
  2. Asymmetry: For all $$$x, y$$$ in $$$S$$$, if $$$x \lt y$$$, then it is not the case that $$$y \lt x$$$.
  3. Transitivity: For all $$$x, y, z$$$ in $$$S$$$, if $$$x \lt y$$$ and $$$y \lt z$$$, then $$$x \lt z$$$.
  4. Transitivity of incomparability: For all $$$x, y, z$$$ in $$$S$$$, if $$$x$$$ is incomparable with $$$y$$$ (neither $$$x \lt y$$$ nor $$$y \lt x$$$ hold), and $$$y$$$ is incomparable with $$$z$$$, then $$$x$$$ is incomparable with $$$z$$$.

Your comparator violates asymmetry. As a result, using it in std::sort or std::stable_sort leads to undefined behavior, which can manifest as runtime errors, especially in optimized builds or different C++ standard versions.

This explains why your original code crashed in some configurations but passed in others — undefined behavior is unpredictable.

→ Reply
»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

https://mirror.codeforces.com/blog/entry/70237

→ Reply