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

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

I have been solving a problem today and I discovered that this code gets WA15 while this one gets AC. The only difference is in these lines

AC:

v<int> DP(10000); int MAX = -INF, ans = 0;

WA15:

int DP[10000], MAX = -INF, ans = 0;

Furthermore, compiled with G++0x both solutions get AC which means it is a bug or at least undefined behavior.

Теги bug
  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Maybe this is because vector is initialized with zeroes by constructor, but array is not initialized by default? (that's why I use C# rater C++ :))

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    It's global array and it should be filled by zeroes.

    ADD: this got accepted :) Array size was set to 20000)

    ADD: But this one got TLE. It seems that, your N can be more than 10000.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

      Well done.

      It is really stupid that accessing vector elements out of bounds doesn't result in RE on Timus. Even assert is ineffective.

      It is also interesting what values were assigned to the elements that were out of bounds. Not zero I've checked :]

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        It is really stupid that accessing vector elements out of bounds doesn't result in RE on Timus. Even assert is ineffective.

        Both bound checks and assertions are debugging features, at least in C++. It is not stupid that debugging features are turned off on programming contest servers.

        • »
          »
          »
          »
          »
          10 лет назад, # ^ |
          Rev. 6   Проголосовать: нравится -11 Проголосовать: не нравится

          You are wrong because of many thing:

          -- The "why not" argument --

          If it is possible, without any measurable performance loss, to have debug features. Then why not? CF, TC and other online judges that respect themselves have debug features turned on. And make up you mind which is stupid (CF and TC) or Timus?:D

          In case you overly worried about performance loss due to assert and vector, one still has a possibility to comment out every assert statement and use array instead of vector. No loss here.

          -- It is misleading --

          When seeing RE as a possible verdict. It is seriously misleading see WA instead of RE. See the following verdicts on different lines on Timus:

          int A[1];
          cout << A[1234]; // no error
          cout << A[12345];// RE
          

          -- Getting not logical results --

          This blogpost exemplifies the obvious requirement: unharmful changes should not result in different results. And c'mon converting an array declared globally into vector has always been perceived, at least by me, to have no effect (excluding of course bounds checking feature).

          -- It is misleading part #2 --

          Again from blogpost. Think about what would have I thought if I had started with vector? I would have gotten AC and thought that my solution is correct and N in my code is always smaller than MAXN. During a contest, do you know what is worse than having no clue about solution? The answer is being sure about your solution because you have already coded that in the past and the solution is actually wrong. I had that experience unfortunately and believe me it is very frustrating.

          -- Purpose of the website --

          Well, OJs are not for code-generators, but rather humans who deal with very difficult problems. Besides, considering the obvious demand on OJ that it should be educational rather than misleading, we conclude that it should do everything to make algorists progress.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +14 Проголосовать: не нравится

            In C++, small errors in code can easily lead to an undefined behavior. This is a characteristic of C++ compared to many other programming languages. You should understand the programming language you chose.

            • »
              »
              »
              »
              »
              »
              »
              10 лет назад, # ^ |
              Rev. 2   Проголосовать: нравится -11 Проголосовать: не нравится

              You have not answered any of my arguments (yes, of course, you have not even read it :D. 7 minutes is not enough to read and analyze).

              BTW,

              Turning on/off debugging features is about OJ and that is what I am talking about, but you are talking about C++.

              • »
                »
                »
                »
                »
                »
                »
                »
                10 лет назад, # ^ |
                Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

                I read your comments, but I did not respond to it because your comment just confirmed that you were missing the point of my comment. If you do not like undefined behaviors (even if you deny that), use a programming language where array bound checks and other features are required in the language specification.

                Edit: This is my last comment in this thread.

          • »
            »
            »
            »
            »
            »
            10 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится

            The ideology of C++ is that (a) a programmer knows what he is doing, and that (b) you don't pay for what you don't want.

            From (a) it follows that C++ compilers will assume the programmer is correct, and optimize accordingly. If the programmer is not correct, then he is at fault and the program will behave in unpredictable ways (this is called "undefined behavior").

            From (b) it follows that C++ will not include most debugging features by default, because they come with a performance cost. If you want debugging features in C++, you should explicitly request them. Like using v.at(i) instead of v[i].

            If you don't agree with this ideology, then I suggest you to choose a different programming language that suits your requirements.

            If contest servers enabled slow debugging features by default in C++, then this would hinder people who actually write correct programs and don't want to trade the performance of their programs for more debugging. This would remove one of the benefits C++ has.

            CF, TC and other online judges that respect themselves have debug features turned on

            Do you have any specific example to confirm this?

      • »
        »
        »
        »
        10 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        You can use vector::at to get bounds checking.