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!
maybe undefined behavior?
I think so as well, but why the other solution always got accepted? It's very strange.
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).
Thanks, I see.
Note the "Diagnostics" section in your RTE submission (scroll to the very bottom of testing protocol and take a look at the last test):
So, you access element
-1at lines2[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.
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
pbydel(p), the element at this position must have been added byadd(p), is there any special case?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.
That's really helpful! And finally figure out the logic mistake, thanks very much!
The second submission worked fine as the index
-1ofs2maps to an entry of the arraydk. 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
dkas a part of compiler optimizations.Yeah, it is quite possible, the access the
s2is out of range, but that range is still usable by the problem and can be accessed throughs2[-1], and finally all things went well. Thanks very much for explanation!