DaiDaiBear's blog

Metaphysics? Strange thing in Mo's algorithm
By DaiDaiBear, history, 7 years ago, In English

There is a quite strange thing when I try to solve 940F - Machine Learning, which is I submit a dozens of solutions and all of them get Runtime Error on test 46. But finally I create a new array and do not use it anywhere except give it some value in the beginning, and the solution got Accepted.

Details can be found by the difference between 35980539 and 35980530. The name of the unused array is dk, and initialized in the 4th line in solve() function, and not anywhere else appears.

Does anyone know the reason why this happens? It really confused me and spend a lot of time on finding the error. Any comments will be helpful, thanks in advance!

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

Comments Comments (10)
| Write comment?
»
7 years ago, # |
  Vote: I like it +36 Vote: I do not like it

maybe undefined behavior?

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

    I think so as well, but why the other solution always got accepted? It's very strange.

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

You could go out of range of some array. When the memory you accessed is not yours, it causes segmentation fault, otherwise you just access the memory belonging to another variable of your program (which is still undefined behaviour).

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +38 Vote: I do not like it

Note the "Diagnostics" section in your RTE submission (scroll to the very bottom of testing protocol and take a look at the last test):

Diagnostics detected issues [cpp.clang++-diagnose]: p71.cpp:52:5: runtime error: index -1 out of bounds for type 'int [200010]'
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior p71.cpp:52:5 in

So, you access element -1 at line s2[s1[a[p]]]++;, which invokes undefined behavior. It crashes your program in the first submission, but with the second one you got lucky for whatever reason (after all, the behavior is undefined, not "guaranteed to crash").

You can read more here.

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

    Thanks very much, I got what you mean and the link. It is still very strange why submission 35980539 succeed. And I checked the program again and again, still think that the undefined behavior should not happen... Because every time you want to remove a element at position p by del(p), the element at this position must have been added by add(p), is there any special case?

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

      Consider ranges [3,5] and [9,12]. After [3,5] you will move the left pointer to 9 while deleting elements 3-8. But you haven't added elements 6-8.

      One way to fix this is to always expand the range first and then contract it.

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

        That's really helpful! And finally figure out the logic mistake, thanks very much!

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

    The second submission worked fine as the index -1 of s2 maps to an entry of the array dk. In the first submission, that memory area appears to be out of bounds for the program and hence it crashes.

    Here is a submission I made which illustrates the point: 35989171

    I believe the compiler sets some extra space for the array dk as a part of compiler optimizations.

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

      Yeah, it is quite possible, the access the s2 is out of range, but that range is still usable by the problem and can be accessed through s2[-1], and finally all things went well. Thanks very much for explanation!

      → Reply