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

Vector vs Array
Автор iamujj15, история, 2 года назад, По-английски

In the AtCoder Beginner Contest 271, I made two submissions for Problem D.

Submission 1, which is an AC.

Submission 2, which is a WA.

In Submission 1, I declared dp as int dp[101][10001]; globally, and used memset(dp, -1, sizeof(dp)); inside main function. In Submission 2, I declared dp as vector<vector<int>> dp(101, vector<int>(10001, -1)); inside main function, and passed it in function 'f' by reference.

I'm clueless about what is causing this WA in Submission 2, when the logic remains same. Could someone please help me with this.

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

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

Since logic the same, and you've got another verdict, I'd assume that you somewhere went out-of-bounds.

Static allocated int dp[101][10001] lies lineary in memory, so dp[0][10001] is dp[1][0]. In vector dp[0][10001] is just garbage. And I saw, that you never check whether sum < 0 and access to dp[i][sum].

Try to use at function instead of [] in vectored solution (at will throw exception if out-of-bounds happens).

→ Ответить
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As pointed out by balalaika, you are indeed going out of bound.

I added assert(i>=0 && i<=100 && sum>=0 && sum<=10000); in your submission wherever you accessed dp array and both submissions are giving Runtime Error.

RE submission with vector RE submission with array

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

Vector is not giving any runtime error when we go out of bounds, neither is the array giving runtime error.

This kind of mistake can be very hard to debug. Can someone suggest some advice for easily finding out if there are out-of-bound errors?

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

    As balalaika already pointed out, you can use the at function on a vector and then it will give RE. This can be helpful for detecting out-of-bounds errors on a secret testcase.

    However, a C array has no builtin out-of-bounds check. So you won't see an RE verdict on a secret testcase.

    If the error already happens on public testcase, you can see it if you compile your code with flags like -fsanitize=undefined,address and -D_GLIBCXX_DEBUG. This will also show you the error if you use a C array or a vector with [].

    → Ответить