Legend_11's blog

Error on vector initialization
By Legend_11, history, 8 months ago, In English

Hello Codeforces, I came across an interesting error while solving this problem : https://codeforces.net/contest/1950/problem/G which I am not able to understand as to why this is happening?

https://codeforces.net/contest/1950/submission/255101098 (This solution did not get accepted but gave runtime error) https://codeforces.net/contest/1950/submission/255101528 (This solution got accepted)

Note there is very little difference between the two

In the first solution I have initialized vector as : vector<vector<int>>dp(n,vector<int>((1<<n),-1));

In the second solution I have initialized vector as : vector<vector<int>>dp((1<<n),vector<int>(n,-1));

I really don't understand what is causing this error. Any help would be appreciated. Thank you !

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

»
8 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it 
The two declarations you've provided represent two different ways of organizing a 2D array.

vector<vector<int>> dp(n, vector<int>((1 << n), -1));

In this declaration:

dp is a 2D vector with n rows.
Each row is a vector of integers initialized to -1.
Each row has 1 << n columns, i.e., 2 raised to the power of n.
This structure is suitable for problems where you want to store information for each combination of n elements. For example, if you're solving a problem related to subsets of n elements, you can use this structure to store information about each subset.

vector<vector<int>> dp((1 << n), vector<int>(n, -1));

In this declaration:

dp is a 2D vector with 1 << n rows.
Each row is a vector of integers initialized to -1.
Each row has n columns.
This structure is suitable for problems where you want to store information for each element in a set of size 1 << n. For example, if you're solving a problem related to permutations or combinations of n elements, you can use this structure to store information about each individual permutation or combination.

In summary, the difference lies in the organization of rows and columns. The first declaration organizes the data by subsets, while the second organizes it by permutations/combinations. Which one to use depends on the specific problem you're trying to solve.

Array access out of bounds: If your code tries to access elements beyond the allocated memory bounds of the array, it can lead to undefined behavior or a segmentation fault. This is more likely to happen if you mistakenly access elements outside the valid range of indices.

even GPT knows about it

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

    Why would it give out of bounds error? Please see the code properly

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

vector<vector>dp(n,vector(**(**1<<n,-1**)**)); remove those brackets

→ Reply
»
8 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Actually, like what the above commenter has said, you declare the vector in the first sol as vector<vector<int>>dp(n,vector<int>((1<<n,-1)));, instead of vector<vector<int>>dp(n,vector<int>((1<<n),-1));. While the difference here is subtle, it is still a fatal error, as you have accidentally declared vector<int>((1<<n,-1)); which makes the compiler very confused and essentially terminate themselves. Why? Because the first argument you put is not an integer (in fact, it is not any STL data structure at all).

Moral of the story: watch out for bracket placement, as they are the reason some codes basically gives WA or RTE.

→ Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 12   Vote: I like it +8 Vote: I do not like it

    There is nothing confusing compiler. This line is valid and compiled. The only issue is that (1 << n, -1) is evaluated as two expressions separated by comma, from left to right (check out comma operator). Then the result of the first expression 1 << n is discarded since it's not used. The result of the second expression is used which is -1 so this means vector is initialized with size of -1. There is noting wrong to create a vector with size -1 actually you can see it's complied successfully. But obviously accessing a negative size vector throws run time exception.

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

      well, the more i know i suppose, thx m8 <3

      → Reply