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

Error on vector initialization
Автор Legend_11, история, 8 месяцев назад, По-английски

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 !

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

»
8 месяцев назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится 
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

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

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

→ Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 месяцев назад, # ^ |
    ← Rev. 12   Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    → Ответить