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

Local Compiler Issue
Автор KitasCraft, история, 7 месяцев назад, По-английски

Hi there. So I was (and still am) trying to code a solution for 1954D - Colored Balls. One of the main implementation here is the knapsack DP, but somehow there was an issue on the variables. So I went to retype just the knapsack code and debug it like the following:

#include <bits/stdc++.h>

using namespace std;

long long dp[5000];
int a[5000];

int main() {
    int n;
    cin >> n;
    for (int i=0;i<n;i++) {
        cin >> a[i];
        for (int j=5000-a[i];j>=0;j--) dp[j+a[i]]=(dp[j+a[i]]+dp[j])%998244353;
    }
    for (int i=0;i<n;i++) cout << a[i] << ' ';
    cout << endl;
}

So, I was testing this input for this code:

3
1 1 2

and in my local VS Code g++17 compiler it results in this:

301989885 0 2

while in Codeforces g++17, it results in this:

1 1 2

Does anyone know why this happened? If so, please let me know :>

Edit: So apparently, the local compiler produce the correct output if I change 5000 to 5001 or 4999. Now I'm more tempted to know on why 5000 specifically fails.

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by KitasCraft (previous revision, new revision, compare).

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

Your first access of the dp array is an out of bounds access, using the index 5000. This is just undefined behaviour — the only correct fix is to ensure that all your array accesses are within the array bounds.

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

    but why did it change the value of $$$a[i]$$$ itself tho? if it's the $$$dp$$$ itself that messed up then I can understand why, but this happened on the array $$$a$$$, which makes it even more confusing.

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

      Undefined behaviour (UB) means the behaviour is quite literally undefined. One possible thing that the compiler could have done was to think of the element dp[5000] as a[0], because the arrays dp and a might be contiguous in memory. However, this is not something you can rely on, and you must always take into account that the compiler doesn't have any restrictions on what it can do once it sees UB.

      In fact, UB is present in order to let the compiler optimize things better. For example, if you enforce that there is some out-of-bounds deduction at run-time, it is impossible to optimize other types of code (that are not necessarily UB). Similarly, if you enforce something like signed integer overflow being defined behaviour, the compiler is unable to do optimizations like changing things like a * 2 / 2 to a and so on, which make mathematical sense. More detail: if the overflow behaviour is undefined, then when a * 2 overflows, the compiler says nothing, and it might as well do this transformation. Meanwhile, if you had wrapping behaviour, it would enforce this multiplication (or perhaps an overflow check), which makes the general case slower. So you get better optimization/codegen but the onus of writing correct code that respects the standard is on you.

      → Ответить