KrK's blog

The power of assert()
By KrK, 10 years ago, In English

Hello,

I want to share my a bit weird experience with you guys. I was solving Tavas in Kansas and had some serious problems with debugging my solution. In the end, it was clear that the idea was correct, I just needed to focus on the implementation. I rewrote a small chunk of code and was astonished by the fact that it was equivalent, but it got accepted. I tried to play with my implementations a little. And guess what? I found out that assert() on an obvious condition can make your code work!

Proof: the failed submission and the accepted submission (only with the assert added, where k should be 1).

I generally do not have great knowledge of compilators and stuff like that. But maybe someone has the idea what the hell happened? :D

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

»
10 years ago, # |
  Vote: I like it +40 Vote: I do not like it

Your code get AC with VC++ compiler. volatile int k = 0; also get AC. So problem is in G++ optimising.

→ Reply
»
10 years ago, # |
  Vote: I like it +78 Vote: I do not like it

Seems like optimization bug. It is funny that -O2 replaced with -O3 makes your code correct.

It is not the first time codeforcers found a g++ bug, try to google like "codeforces g++ bug".

It will be really good to minimize your code and to file an issue in gcc bug-tracker. Good idea is to check your code with tools like valgrind to be sure that it is not an undefined behaviour.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

fprintf(stderr, "%d", k); helps. or write something else to STDERR also helps.

link1

→ Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Can't repeat with g++ (GCC) 4.9.2 20150212 (Red Hat 4.9.2-6) and this test case.

→ Reply
»
10 years ago, # |
  Vote: I like it -83 Vote: I do not like it

Never met any bugs in VC++. What's the purpose of using G++?

→ Reply
»
10 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Damn, feel so unsecure now. IOI uses g++ and most probably with -O2. And it is at least the 2nd g++ bug found by Codeforces. :/

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    On IOI they will most likely use the Linux distribution's default GCC, which

    • Was tested to build the numerous distribution's packages
    • Carries a distribution-specific set of patches to fix known problems and regressions

    So you shouldn't worry about it too much.

    → Reply
»
10 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Added one more ticket to gcc issue-tracker: https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66096

Can someone try it on other build of g++ 4.9.2 32-bit?

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Also posted it in mingw-tdm issue tracker: http://sourceforge.net/p/tdm-gcc/bugs/264/ It has been accepted by maintainer.

    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Looks like you haven't attached the testcase to the issue.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yep. Fixed.

      I've got comment from the tdragon (tdm maintainer):

      Thanks for the report. This bug was also reported on the MinGW-w64 mailing list recently, and it seems to apply to all winpthreads-based builds. Once a fix is created, the next TDM release will certainly include it.

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +40 Vote: I do not like it

        I've just came up with smaller example on g++ 4.9.2 with tdm-gcc-32:

        #define _GLIBCXX_DEBUG
#include <set>

std::set<int> a;

int main()
{
    std::set<int> b;
    return 0;
}
        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Similar experience:

54145878 gives WA On test case 1 and just adding an assert makes it pass the first test case 54146095

→ Reply