Блог пользователя bearzx

Автор bearzx, 13 лет назад, По-английски

Yesterday when I was attending the CodeForces#100, I met a werid problem.


It was Problem A, I wrote my code, submitted, and passed the pretest, as usual. After the system test, I found that my code failed at test 9, it is:

Input: 2 1000 500
Output: NO
Answer: YES
status no. : 1011828

However, when I tested the data on my PC, I noticed that I' ve passed the test. My classmates told me that it might be the reason of O2 optimization of g++, because I don' t add that option on my PC, while CodeForces do. And Later on I submitted again with the MS Visual C++, this time my code was accepted(see status no. : 1010135), interesting, huh?

And something more interesting, if I add some "cout" before a statement(for debugging), I' ll pass the test in custom test:

See the status no. : 1011863
In this situation, I just add an cout << "" before I make my desicion.

And if I remove the cout << "":

I think this kind of results might have something with the O2 optimization, as the optimization may reduce the orders when it is compiling the source code.
  • Проголосовать: нравится
  • +15
  • Проголосовать: не нравится

»
13 лет назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

EDIT: It appears that the problem probably actually has something to do with floating point precision: did you try adding an eps of 1e-8 when you compare doubles?

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    I think the problem is due to the O2 optimization, the accepted and wrong answer codes are the 99.9% same except ONE line contaning  ' cout << ""  '. At the same time , if you submit the wrong answer code in MS C++, it can get Accepted. Although different compilers have something different, floating numbers should also follow ISO standard.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Well, to avoid such problems regardless of what system you're on, you should add an epsilon to your floating point comparisons. You shouldn't assume anything about the compiler's optimizations: there's no way to control what is optimized away.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        However, output a empty string can affect floating point variables value ?
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится +3 Проголосовать: не нравится
          It might be because, without the printing, the compiler can optimize away the local variable, thus changing the floating point rounding.
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится
            But you cannot predict what O2 optimation will do, so you cannot avoid this kind of problem before you see the results
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Therefore, the problem is still caused by O2 optimization.

            O2 optimization has pros and cons. It can make your code run faster, at the same time  it also don't run as your willing sometimes. That is why so many online-judges and ACM/ICPC onsite contests disable the O2 optimization.
»
13 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится
e-maxx, come!
  • »
    »
    13 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +20 Проголосовать: не нравится

    Unfortunately, IMO there's nothing to report :)

    One should never compare precise double values, because there's no guarantee that compiler produced exactly the code we wrote.

    Another instructive example is the following. You wrote DP (which computed, for example, maximum of some double function) and want to restore, at which value did the maximum achieved.

    for (int i=0; i<x; ++i)
       dp = max (dp, value (i));
    for (int i=0; i<x; ++i)
       if (dp == value (i))
          sel = i;
    

    That's totally wrong! Due to some complex optimizations and, as a result, changing of double values, assignment "sel = i" could occur  never.

    That's not a bug because compilers are given freedom with operating with floating-point expressions, and it usually a very bad idea to compare doubles without epsilon.

»
13 лет назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится