peltorator's blog

Help Needed: Confusing C++ behavior on CodeForces
By peltorator, 6 weeks ago, In English

Codeforces Global Round 28 just finished, and I had a heartbreaking moment. Three minutes before the end of the contest, I finished writing code for problem G, submitted it, and got RE1. I didn't have enough time to figure out what the problem was. However, after the contest, I was able to understand what causes this behavior but I still can't figure out WHY this happens so maybe some C++ experts among you can help me :)

Submission for reference: 297344731. I have a structure for modular arithmetics template<int mod> struct ModularInt. Inside it, it has a static vector of some modular inverses: static vector<ModularInt<mod>> invs; that is then initialized after the end of the structure: template<int mod> vector<ModularInt<mod>> ModularInt<mod>::invs{ModularInt<mod>{0}, ModularInt<mod>{1}};. I then use this vector of inverses in the modular inverse function:

inline ModularInt<mod> inv() const {
    assert(value != 0);
    int ans = 1;
    int curval = value;
    while (curval >= invs.size()) {
        int tmp = mod / curval;
        ans = 1LL * ans * (mod - tmp) % mod;
        curval = mod - tmp * curval;
    }
    return invs[curval] * ans;
}

For some reason on codeforces, this function causes division by zero error on line 6. It happens because invs.size() is equal to zero which clearly cannot be the case because vector invs is initialized with two elements. This error happens if I use the inverse operation to declare some global values. However, if I move these computations inside the main function, this problem disappears, and the submission gets AC (see 297350557). On my computer, I cannot replicate this problem. Could somebody please help me to understand why this is happening and how to fix it?

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

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

truly, a soul-crushing moment

→ Reply
»
6 weeks ago, # |
  Vote: I like it +26 Vote: I do not like it

I replicated this problem on my device, the division by zero occurs at line 274, during initialization of global variable facts.

This probably has something to do with the order in which compiler initializes static variables, you might wanna look into this.

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks! But here everything happens in one file. And the initialization of invs preceds the initialization of facts. That is what confuses me.

    → Reply
»
6 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

According to cppreference, the initialization of such [class template] static variables [that aren't explicitly specialized] is indeterminately sequenced with respect to all other dynamic initialization. Unluckily, your ModularInt<mod>::invs is of such static variables.

To solve this, you can either initialize Factorial in main function as you do, or explicitly specify ModularInt<mod> as 297355433.

→ Reply