iamujj15's blog

Vector vs Array
By iamujj15, history, 2 years ago, In English

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.

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

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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).

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

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

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

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?

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

    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 [].

    → Reply